# Tag Info

17

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

17

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

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 + 2,...

14

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

14

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.

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^Defer[#2] ...

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

11

Using an undocumented function: AlgebraMatrixPowerMod[{{2, 3, 1}, {5, 2, 4}, {0, 3, 2}}, 4, 6] {{1, 0, 5}, {1, 1, 5}, {3, 3, 4}} Mod[MatrixPower[{{2, 3, 1}, {5, 2, 4}, {0, 3, 2}}, 4], 6] {{1, 0, 5}, {1, 1, 5}, {3, 3, 4}} Unfortunately, the undocumented function does not support the action form of MatrixPower[].

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$, $\mathbb{Z}_n$ ...

10

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

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

You are looking for the multiplicative order, MultiplicativeOrder[k, m]. The multiplicative order is the smallest exponent $k$ such that $x^k \equiv 1 \pmod m$. Note that the modulus $m=317026939759222841944$ is divisible by prime $67$. Your equation then becomes $67^{n-1}\equiv 1 \pmod {4731745369540639432}$. MultiplicativeOrder[67, 4731745369540639432] ...

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_] := ...

7

FindInstance easily finds one solution, and fails to find two, so there might not be more: FindInstance[{Mod[6 a + 0 b + 1 c + 1 d + 0 e + 1 f + 0 g + 1 h + 0 i, 1235788] == 990685, Mod[0 a + 3 b + 0 c + 0 d + 3 e + 0 f + 0 g + 0 h + 1 i, 1235788] == 404244, Mod[4 a + 0 b + 0 c + 0 d + 0 e + 1 f + 1 g + 0 h + 0 i, 1235788] == ...

7

You can use the Modulus option for Reduce to get the general solution. {ToRules[Reduce[{ 6 a + 0 b + 1 c + 1 d + 0 e + 1 f + 0 g + 1 h + 0 i == 990685, 0 a + 3 b + 0 c + 0 d + 3 e + 0 f + 0 g + 0 h + 1 i == 404244, 4 a + 0 b + 0 c + 0 d + 0 e + 1 f + 1 g + 0 h + 0 i == 1228796, 1 a + 2 b + 1 c + 0 d + 1 e + 1 f + 1 g + 0 h + 0 i == 626461, ...

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

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

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

Let $x \equiv r_1 \bmod p$ and $y \equiv r_2 \bmod p$. Then, $x y \equiv r_1 r_2 \bmod p$. So, we can compute the sum of the factorials mod p using: f[p_] := Mod[ Total @ FoldList[ Mod[Times[##], p]&, Range[p-1]], p] Let's compare this to the naive implementation: t[p_] := Mod[Sum[k!, {k, p-1}], p] For example: f[Prime[500]] //AbsoluteTiming t[Prime[...

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[AlgebraPolynomialPowerModPolynomialPowerMod[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}] &, {...

5

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

5

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

5

PowerMod can help: fracMod = Mod[Numerator[#] * PowerMod[Denominator@#, -1, 26], 26] &; fracMod@{256/11, 258/11, 263/11, 263/11, -22, -22, 251/11, 0, 261/11, -22, 265/11, 259/11, 0, 259/11} (* {2, 14, 5, 5, 4, 4, 11, 0, 19, 4, 17, 7, 0, 7} *) Addendum -- General-purpose function ClearAll[ratMod]; SetAttributes[ratMod, Listable]; ratMod[Rational[...

5

sol = Solve[ 3 x^2 + 6 x + 1 == 0, x, Modulus -> 19] or Reduce[3 x^2 + 6 x + 1 == 0, x, Modulus -> 19] Confirm: Mod[3 x^2 + 6 x + 1, 19] /. sol

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