Tag Info

Hot answers tagged

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


14

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


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.


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

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


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


5

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


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[Algebra`PolynomialPowerMod`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

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

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

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

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


1

Yes, use a few auxiliary functions and ReplaceAll: power = PowerMod[#, #2, m] &; fractionMod = Mod[Numerator[#]*PowerMod[Denominator[#], -1, m], m] &; newThing = fractionMod[ReplaceAll[oldThing, Power -> power]];


1

Part[result /. Dynamic -> Identity, 2, 1]



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