Hot answers tagged modular-arithmetic
14
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 ...
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$, ...
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
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, ...
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;
...
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:
...
4
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, ...
4
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 ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
