# 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 ...

13

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 2^...

13

This is bit faster: toPrime = 500; sums = Accumulate@FoldList[Times, 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.

12

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 ...

12

Yes, you can use the built in function Outer. It does exactly the kind of thing you are talking about it. Try Outer[Mod, list1, list2] Outer is a generalization of the outer product in Linear Algebra. Its first argument is a function, and the rest of its arguments are lists. Basically, it applies the function in the first argument to every element in the ...

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 = Prime[...

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 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], g[x]... 9 addmod = Mod[Plus[##],2]& ## is a Sequence of all the arguments given to addmod. 9 I do a lot of cybersecurity competitions where we crack crypto, so I'm used to grappling with Mathematica for ring algebra. The sole thing Mathematica honestly isn't great for is cryptography. For this stuff, I generally just use SageMath Cloud, because it has all of the above algorithms built into DiscreteLog. You just throw your values at the function and ... 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 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 ... 7 As already mentioned in the question, we can use Outer, for example (with a$3 \times 2$matrix) Outer[f, {x1, x2, x3}, {y1, y2}] {{f[x1, y1], f[x1, y2]}, {f[x2, y1], f[x2, y2]}, {f[x3, y1], f[x3, y2]}} so we just need a function f for which f[x, y] returns ChineseRemainder[{x, y}, {7, 30}]. That function could be defined simply as f[x_, y_] := ... 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 = Map[Reverse[... 6 Already answered in the comments by DumpsterDoofus and Daniel Lichtblau, to summarize: Machine floating point numbers such as 0.2 are not always exactly representable in binary (no terminating expansion in base 2). Thus floating point arithmetic is susceptible to roundoff error and other accuracy problems. For example, the following are not exactly equal to ... 6 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, n]... 5 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: PolynomialMod[... 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

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

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

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

check[rut_] := Module[{d = 11 - Mod[Total[IntegerDigits[rut]*{3, 2, 7, 6, 5, 4, 3, 2}], 11]}, Which[d == 11, 0, d == 10, "K", True, d]] Takes rut as integer (all digits less check digit), returns check code. Does not validate length of input, so add that if needed. Update: Since you've added check examples, and since they contain both 7 and 8 body ...

4

How about Assuming[101 < t < 109, FullSimplify[PiecewiseExpand[Mod[t, 10]]]] rhermans gives a simpler formulation: PiecewiseExpand[Mod[t, 10], 101 < t < 109]

4

To fix the memory problems you could rewrite it in a procedural style. It's probably more than a tweak, a bit ugly, and a bit slower. But you can go forever without having to worry about memory. ClearAll@fail; fail = Compile[{{m, _Integer}, {p, _Integer, 1}}, MemberQ[Mod[6 m - 3, #] & /@ p, 2] || MemberQ[Mod[6 m - 3, #] & /@ p, 4]]; ClearAll@...

4

You have a series of conditions you want to be true, so use Select, A1 = {2}; A2 = {3, 5, 6}; A3 = {7, 8, 10}; Select[Range[100], MemberQ[A1, Mod[#, 3]] || MemberQ[A2, Mod[#, 7]] || MemberQ[A3, Mod[#, 11]] &] (* {2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, \ 23, 24, 26, 27, 29, 30, 31, 32, 33, 34, 35, 38, 40, 41, 43, 44, 45, \ 47, ...

4

The lazy user just looking to solve equations can simply use Solve[4 x == 1, x, Modulus -> 5] and be done with it. However, one should recognize that this is in fact a modular inversion problem, and that there are specialized number-theoretic tools for dealing with this directly. All of this hinges on Bézout's identity, which says that for two nonzero ...

3

This seems to work Mod[Rationalize@1.2, Rationalize@0.2] == 0 I also tried with SetAccuracy, but it didn't always work. "If Your Only Tool Is a Hammer Then Every Problem Looks Like a Nail" What I mean is that I'm using here a function that is probably quite involved (Rationalize) for a problem that doesn't look complex (although it is complex when you ...

3

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} *...

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