Tag Info

Hot answers tagged

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


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.


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

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

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


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}]]] :)


3

You seem to be referring to the Rol Único Tributario. This article gives a verification algorithm. rasher already wrote the algorithm to compute the check digit, so I'll write something slightly different, the verification algorithm. Strip out all non-numeric characters, except an optional trailing K. Pad the number to nine digits with zeros on the left. ...


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



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