The tag has no usage guidance.

learn more… | top users | synonyms

22
votes
1answer
379 views

Fast calculation of discrete logarithms

Does Mathematica have any built-in fast algorithms for calculating discrete logarithms over $(\mathbb{Z}_p)^\times$ (the group of integers modulo $p$)? Essentially, for a fixed large prime ...
13
votes
2answers
735 views

Factorizing polynomials over fields other than $\mathbb{C}$

I'd like to take a polynomial in $\mathbb{Z}_5[x]$ of the form $ax^2+bx+c$ and factor it into irreducible polynomials. For example: Input... x^2+4 Output... <...
10
votes
1answer
754 views

Modular arithmetic - efficiently calculating the remainders of factorials

When working on this question regarding the divisibility of the sum of factorials, I decided to write some code to test "small values" of the problem using the following code. ...
9
votes
2answers
748 views

Solving/Reducing equations in $\mathbb{Z}/p\mathbb{Z}$

I was trying to find all the numbers $n$ for which $2^n=n\mod 10^k$ using Mathematica. My first try: Reduce[2^n == n, n, Modulus -> 100] However, I receive ...
9
votes
5answers
521 views

Incrementing a number where each digit has a different base

Let's say I have a list, for instance {10,5,3}, indicating the bases for each digit of my 3-digit number. Using this basis, if I wanted to increment {8,4,1} a couple of times, here's what I would get: ...
8
votes
1answer
192 views

Taking one list Mod a second list

Just on my free trial and can't find this anywhere in online docs. Trying to use the Mod function as follows: Mod[{list},{list}} where it takes each number in list ...
7
votes
1answer
3k views

Solving a system of linear equations modulo n

I have a system of linear equations $$ a+b+c \equiv 31 \pmod{54} $$ $$ 4a+2b+c \equiv 3 \pmod{54} $$ $$ 9a+3b+c \equiv 11 \pmod{54} $$ What should I input (I'm using ...
7
votes
2answers
294 views

Mod[1.2, 0.2] is not equal to zero

Why doesn't the following expression evaluate to zero? In[1]:=Mod[1.2, 0.2] Out[1]=0.2 Edit: This is what I wanted to do: ...
7
votes
1answer
936 views

How to Simplify equations over a Ring with Mathematica?

For example, when we work over a ring, the equation x^3=0 does not imply x^2=0 or x=0, but ...
7
votes
0answers
104 views

Bug in PiecewiseExpand and Mod with assumptions

Bug introduced in 9.0 or earlier and fixed in 10.4 The following code using PiecewiseExpandand Modgives the wrong answer <...
6
votes
1answer
184 views

Implementing Remainder Tree

I want to implement Remainder Tree based on this. With the answers on SE I've come up with: ...
6
votes
1answer
564 views

Polynomial GCD over a ring (with composite characteristic)

I'd like to implement the "Franklin-Reiter Related Message Attack" (see section 4.3 of Boneh's paper). As part of the implementation, I require to compute the GCD of two polynomials over $\mathbb{Z}_N[...
5
votes
2answers
1k views

Inverse of a polynomial in a polynomial ring

Let $N$ be a prime, and $q$ be a positive integer. Given a polynomial $f(x)$ in $R = \mathbb Z[x]/(x^N-1)$, I want to find another polynomial $f_q(x)$ in $R_q = \mathbb Z_q[x]/(x^N-1)$, such that $$f(...
5
votes
1answer
606 views

Montgomery Modular Exponentiation

I'm trying to write a Montgomery exponentiation based on this which can compete with Mathematica PowerMod. We know that PowerMod ...
3
votes
2answers
757 views

decompose a number (less than 255) in a sum of powers of 2

Is there a built in function that would take a number and decompose it into a sum of powers of 2? The numbers will be non negative less than 256. For what it's worth I'm trying to understand a paper ...
3
votes
2answers
102 views

Using “Outer” with “ChineseRemainder”?

I'm looking to build a $7\times3$ matrix using ChineseRemainder. Trying to use ${0,1,2,3,4,5,6} \pmod 7$ and ${3,15,21} \pmod {30}$ so that the first element of ...
3
votes
1answer
918 views

Linear Solve with Modular Arithmetic

I am interested in using LinearSolve[m,b] which will find a solution to the equation $m.x=b$, where I am in mod 2 arithmetic. Is there any way to perform this ...
3
votes
0answers
41 views

Sparse matrix multiplication mod p

Let A and B be sparse matrices with integer coefficients between 0 and ...
3
votes
0answers
296 views

Parallel PowerMod

Is there anyway to parallelize the PowerMod function? Here is my Left-To-Right modular exponentation: ...
2
votes
2answers
511 views

Check RUT (Rol Único Tributario) for numbers over 7 digits

In Chile the RUT (Rol Único Tributario) is a national identification number. Every RUT has a check digit modulo 11. The RUT has 7 or 8 digits plus a check digit or letter. I made this code that works ...
2
votes
2answers
348 views

Why is Mathematica getting this modular root wrong?

First, note that $4^{96}\equiv 96 \pmod {100}$. Mathematica claims that PowerMod[96, 1/96, 100] has no integer solutions. Even more obviously wrong, I get ...
2
votes
1answer
65 views

Twin Prime Max Gaps (Performance Tuning)

Ok, let's build a foundation here: A common way of testing primality, is dividing by all primes smaller than the number's square root. For instance, $97$ is prime because dividing by none of the ...
2
votes
1answer
62 views

A Difficult Application of Modular Arithmetic

Looking to input a $p$ for the first line: p=6; Build a list of primes from the 3rd to $p-1$: ...
2
votes
0answers
59 views

What does Mod^(1,0) mean in mathematica output [closed]

I am trying to take he derivative of mod(remainder). In:= D[Mod[x, y], x] Out = Mod^(1,0)[x,y] I cannot understand the meaning of Mod^(1,0). What does the ...
1
vote
1answer
956 views

Matrix Multiplication Modulo 2

I would like to perform matrix multiplication modulo 2. Hence, instead of the usual: A.B I did: ...
1
vote
2answers
503 views

Finding shortest non-zero vector $x$ satisfying $Ax=0 \pmod q$

Let $n$, $m$, and $q$ be positive integers (with $m > n$), and $A$ be a matrix over $\mathbb{Z}_q^{n \times m}$. Using Mathematica, I want to find the shortest non-zero vectors $x \in \mathbb{Z}_q^...
1
vote
1answer
61 views

Get Mathematica to solve Modular Arithmetic problem [closed]

How would I get Mathematica to solve something like this for $x$? $4x \equiv 1 \pmod 5$
1
vote
1answer
46 views

Simplify Mod to subtraction when possible

FullSimplify[Mod[t,10], t>101 && t<109] It's a long shot, but can I get Mathematica to return t-100 or something ...
1
vote
1answer
59 views

What is the correct idiom for mapping a 0 value in a modulo n expression back to n?

What is the correct idiom for mapping the $0$ value in a modulo $n$ expression back to $n$. For example if I want to be sure that any integer value maps back to the index for a character in the ...
1
vote
2answers
228 views

Modular arithmetic in Mathematica? [closed]

I want to implement something like 1 + 1 = 0; i.e., simple modular arithmetic in Mathematica. This seems like it should be a really easy built-in option, but I can'...
1
vote
1answer
271 views

Faster GCD Implementation

Is there any chance to write a faster GCD than the built-in one in Mathematica? @Mr.Wizard has written one in this question (although it's not for this purpose) which is 6 times slower on a 100k ...
1
vote
1answer
54 views

Converting an expression to modular arithmetic automatically

I have the expression $\frac{1}{15} \left(-(-1)^n-5\times 2^{n+2}+3\times 2^{2 n+1}+15\right)$ which I want to calculate mod m for a very large n. My current method is to ask for this exression in ...
1
vote
0answers
61 views

Working with large integers in Modular Arithemetic

What would be the most efficient method of finding the remainder of the following division, 2^(2^330000000 - 1)/(2^330000001 - 1). I have tried using PowerMod function in Mathematica but i did not get ...
1
vote
0answers
52 views

Sum of zeros in finite Galois field

In the following code: << FiniteFields` GF[2][{0}] + GF[2][{0}] == GF[2][{0}] GF[2][{0}] + GF[2][{0}] + GF[2][{0}] == GF[2][{0}] Why does the second line ...
1
vote
0answers
104 views

Solving an equation for rational modulus 1

I want to solve an system of equations of the form $$\prod_{i=1}^n x_i^{M_{i,k}}=1 \qquad k=1,\ldots,n$$ with complex $x_i$ with constraint $|x_i|=1$ and $M_{i,k}$ integers. This is basically a ...
1
vote
0answers
280 views

Is there a way to speed up Simplify and/or PolynomialReduce Modulus-> 2?

I'm trying to simplify a series of equations with at most 64 input terms. As the number of terms involved in the equations increase, the runtime seems to grow exponentially. Does anyone know of ways ...
0
votes
1answer
108 views

Reduce Vector/Matrix mod N [closed]

If I have a vector such as below and want to reduce it mod a number, how can I do this? V = {{176}, {648}}; MatrixForm[V] MatrixForm[V, Modulus -> 26] Both ...
0
votes
1answer
184 views

Solving for $d$ in $x= E^d \bmod(n)$

With regards to Public Key Cryptography, I have been tasked with the problem of attacking some information given in an assignment and discovered a private key used to digitally sign a message. Known: ...
0
votes
1answer
425 views

How to solve Mod equation with mathematica [closed]

i'm pretty noob with mathematica but i need to solve an equation: $$c\equiv m^2\pmod n$$ I tried something like ...
0
votes
1answer
75 views

How can I seperate specific elements from the list? [duplicate]

Possible Duplicate: Question about MapThread and Dynamic I write a function name as inputFieldsList and it returns both ...
0
votes
0answers
38 views

Montgomery Modular reduction

I saw a Mathematica Implementation of Montgomery reduction at Montgomery Modular Exponentiation, a beautiful one by Simon Woods. I ran this in Mathematica and it was fast, but it does not give the ...
-1
votes
3answers
80 views

Create table of elements which belongs to specific sets

I would like to produce elements (preferably by Table or For-If commands) that they belong to specific sets. For example I want to write positive integers from 1 to 100 such that they are $2 \pmod 3$, ...