# Tag Info

## Hot answers tagged modular-arithmetic

16

All of the polynomial functions, have an option Modulus which allows you to specify an integer field, like $\mathbb{Z}_5$. In particular, Factor works on your example polynomial Factor[x^2+4, Modulus -> 5] (* (1 + x) (4 + x) *) Additionally, IrreduciblePolynomialQ works to determine irreducibility of $x^2+2$, as follows IrreduciblePolynomialQ[x^2 + ...

15

The problem we encounter here is an instance of rather unexpected limitations of equation solving functionality (i.e. Modulus option in Reduce), e.g. this question : Strange behaviour of Reduce for Mod[x,1] provides another example which has been fixed in the newest version (9.0) of Mathematica. Since Modulus unexpectedly doesn't work here we can take ...

12

IntegerDigits works Try powers = IntegerDigits[204, 2] {1, 1, 0, 0, 1, 1, 0, 0} Now, if you want that formatted as a sum of powers of two, you have to hold it. For example Total@MapIndexed[#1 Defer[2]^(First@#2 - 1) &, Reverse@powers] 2^2 + 2^3 + 2^6 + 2^7 EDIT Nicer code, given that your numbers go up to 255 pow2[num_]:=Inner[#1 ...

12

This is bit faster: toPrime = 500; sums = Accumulate@FoldList[#1 #2 &, 1, Range[2, Prime@toPrime - 1]]; primes = Prime[Range[toPrime]]; Mod[sums[[primes - 1]], primes] Precompute factorial sums and primes. Mod is fast on lists.

10

Working with LinearSolve we encounter some inconsistency of the related option Modulus -> z if z is not prime. Nonetheless we could do this Mod[ LinearSolve[ {{1, 1, 1}, {4, 2, 1}, {9, 3, 1}}, {31, 3, 11}], 54] {18, 26, 41} Unfortunately we can get only one solution unlike when working with Solve. These posts describe another problems or bugs ...

10

It's meant to be done divide-and-conquer style. Here is one way to go about that. listMod[n_, {val_}] := {Mod[n, val]} listMod[n_, vals : {_, __}] := With[{len = Length[vals], rem = Mod[n, Times @@ vals]}, Join[listMod[rem, Take[vals, Floor[len/2]]], listMod[rem, Drop[vals, Floor[len/2]]]] ] Your example: n = 31415926535; primeslist = ...

10

Solve with Modulus We can use Solve with domain specification like i.e. Integers, or with e.g. integers modulo 5, then instead of specifying the domain one uses Modulus : Solve[x^2 + 4 == 0, x, Modulus -> 5] {{x -> 1}, {x -> 4}} Times @@ ( x - Last @@@ %) Expand[ %, Modulus -> 5] (-4 + x) (-1 + x) 4 + x^2 For an integer $n$, ...

9

addmod = Mod[Plus[##],2]& ## is a Sequence of all the arguments given to addmod.

8

If you want to solve an equation over integer rings $\mathbb{Z}_n$ you should specify them with Modulus e.g. Column[Solve[x^3 == 0, x, Modulus -> #] & /@ Range[2, 9]] Edit Since there was no further example of any expression to simplify over a finite ring let's define e.g. a polynomial which cannot be factorized over rationals (as Mathematica ...

7

For moduli that are square-free one can use Chinese remaindering on the coefficient lists to get a result valid for the moduli product. cfs[p1_, p2_, x_, p_] := Reverse[CoefficientList[PolynomialGCD[p1, p2, Modulus -> p], x, 1 + Min[Exponent[p1, x], Exponent[p2, x]]]] FromDigits[ ChineseRemainder[ Transpose[{cfs[f[x], g[x], x, 7], cfs[f[x], ...

7

You have several options, either directly implementing incr incr[digs_, base_] := Module[{carry = 1, ndigs = digs, k = 1, nd}, While[k <= Length[digs], {carry, nd} = QuotientRemainder[Part[ndigs, k] + carry, Part[base, k]]; Part[ndigs, k] = nd; If[carry == 0, Break[]]; k++; ]; ndigs ] Or implementing FromMultpleBase and ...

6

The difference between $2^n$ and $n^2$ is that $2^n$ is not a function $\bmod 10$ -- that is, $2^{n+10}$ is not congruent to $2^n\bmod 10$. Further $2^n$ is only eventually periodic $\bmod 10^k$, $k \geq 2$. For instance $2^1$ is not congruent to any other $2^n \bmod 100$. On the other hand, polynomial functions are all functions $\bmod\, m$ : f[n+m] is ...

6

This isn't directly an answer, and I'll delete it if it is off target. But you might want to use some non-System context functionality for taking polynomial-mod-2 products. Specifically this works with integer lists of coefficients. I'll show an example below. In[1110]:= SeedRandom[1111]; vals = RandomInteger[2^8 - 1, 2] intlists = ...

5

Use a Gröbner basis. The idea is to set up an equation for this multiplicative inverse, in a ring where both $x^{11}-1$ and $32$ are zero (that is, $\mathbf Z[x]/(32,x^{11}-1)$). Then unravel that equation using GroebnerBasis to get the variable representing this reciprocal to f in terms of x: f = -1 + x + x^2 - x^4 + x^6 + x^9 - x^10; defpoly = x^11 - 1; ...

5

For the example problem I get about a factor of 4 speedup over PowerMod by memoizing Mont. This of course means that Mont should not contain any global variables so I rewrote the code slightly: MontExp[b_, e_, n_] := Module[ {RLength, R, RM1, RInverse, NPrime, M, Result}, RLength = BitLength[n]; R = 2^RLength; RM1 = R - 1; RInverse = PowerMod[R, -1, ...

5

Let's see some beautiful answers pop up. For now, a not too sleek one to break the ice fix[l_, base_] := Module[{take = 0}, Rest@FoldList[ QuotientRemainder[#2[[1]] + take, #2[[2]]] /. {q_, r_} :> (take = q; r) &, 0, Transpose@{l, base}]] inc[{f_, rest___}, base_] := fix[{f + 1, rest}, base] So NestList[inc[#, {10, 5, 3}] &, ...

4

Based on Rojo's answer: add[base_][l_, x_] := FoldList[QuotientRemainder @@ ({1, 0} # + #2) &, x, {l, base}\[Transpose]][[2 ;;, 2]] NestList[add[{10, 5, 3}][#, 1] &, {8, 3, 1}, 15] {{8, 3, 1}, {9, 3, 1}, {0, 4, 1}, {1, 4, 1}, {2, 4, 1}, {3, 4, 1}, {4, 4, 1}, {5, 4, 1}, {6, 4, 1}} Alternate formulation: base /: base[l_, blst_] + x_Integer ...

4

There is an option Modulus in certain algebraic functions (Solve, LinearSolve, Det,Factor etc.) to specify that integers are to be treated modulo an integer n. Consider e.g. m0 = {{4, 6, 6}, {6, 3, 2}, {1, 4, 4}}; b0 = {4, 2, 1}; then LinearSolve[ m0, b0, Modulus -> 2] {1, 0, 0} You can work with LinearSolve specifying only the first variable, ...

4

As it turns out, there's an (undocumented) function eminently suitable for the task: poly = -1 + x + x^2 - x^4 + x^6 + x^9 - x^10; PolynomialMod[AlgebraPolynomialPowerMod`PolynomialPowerMod[poly, -1, x, x^11 - 1], 32] 5 + 9 x + 6 x^2 + 16 x^3 + 4 x^4 + 15 x^5 + 16 x^6 + 22 x^7 + 20 x^8 + 18 x^9 + 30 x^10 Check the result: ...

3

V = {{176}, {648}}; MatrixForm[Mod[V, 26]]

3

One way to approach this is to use the Null space of the matrix a, which is a basis for all elements x such that a.x=0. For the OPs problem, this can be done by first finding the null space: a = {{2, 1, 6}, {1, 3, 1}}; n = First[NullSpace[a, Modulus -> 7]] {5, 5, 1} Now, observe that a.x=0 is true exactly when a.(c*x)=0, so it is possible to list all ...

3

@cartonn's clock: Dynamic[Thread[Mod[{Clock[{8, 17, 1}, 5], Clock[{3, 7, 1}, 25], Clock[{1, 3, 1}, 75]}, {10, 5, 3}]]] :)

2

I may be missing the point here, but I think in this case functional programming may drag efficiency down... incr[list_, {a_, b_, c_}, n_ : 1] := With[ {check = {Mod[#[[1]], a] , Mod[#[[2]], b] + Quotient[ #[[1]],a], Mod[#[[3]], c] + Quotient[#[[2]],b]} &}, NestList[check[{#[[1]] + 1, #[[2]], #[[3]]}] &, list, n]] Quotient ...

2

Daniel Lichtblau answered this question in the comments The short answer is no. The longer answer is maybe, if you are a GMP developer with access to some fairly low level NTT (number theory transform) code. Even then it will be difficult.

2

Using Solve helps a bit. If vars is the list of variables, then Solve[A.vars == ConstantArray[0, n], vars, Modulus -> q] finds all solutions in terms of parameters C[1], C[2], etc. depending on the dimension of the solution space. Another bottleneck is computing the values of the general solution at all possible combinations of values for the ...

2

Borrowing Rojo's idea from Is it possible to define custom compound assignment operators like ⊕= similar to built-ins +=, *= etc?, we can construct a modular addition operator. MakeExpression[RowBox[{lhs_, rest : PatternSequence[SubscriptBox["⊕", m_], _] ..}], StandardForm] := MakeExpression[{{lhs, rest}[[1 ;; ;; 2]], m}, StandardForm] /. {x_, ...

2

c = 621455041; n = 74596505816855975484638389815392741477; sol1 = Solve[c == m^2, m, Modulus -> n] {{m -> 24929}, {m -> 52367465358866978466157125093802778}, {m -> 74544138351497108506172232690298938699}, {m -> 74596505816855975484638389815392716548}} If you want to know if it is right, substitiute the solution back into the equation And @@ ...

2

It works on a Mac with v9.0.1 \$Version "9.0 for Mac OS X x86 (64-bit) (January 24, 2013)" pml = PowerModList[96, 1/96, 100] {4, 22, 28, 46, 54, 72, 78, 96} And @@ (Mod[#^96, 100] === PowerMod[#, 96, 100] === 96 & /@ pml) True pml === (x /. Solve[4^96 == x^96, Modulus -> 100]) True

2

Solve[4^96 == x^96, Modulus -> 100] Solve[x^96 == 96, x, Modulus -> 100] PowerModList[96, 1/96, 100] (* {{x -> 4}, {x -> 22}, {x -> 28}, {x -> 46}, {x -> 54}, {x -> 72}, {x -> 78}, {x -> 96}} {{x -> 4}, {x -> 22}, {x -> 28}, {x -> 46}, {x -> 54}, {x -> 72}, {x -> 78}, {x -> 96}} {4,22,28,46,54,72,78,96} ...

2

In addition to what I've said in comments, you can write your function in shorter form: letterIndex2[l_, rot_: 0] := Mod[First@ToCharacterCode[l] - 64 + rot, 26, 1]

Only top voted, non community-wiki answers of a minimum length are eligible