Questions tagged [modular-arithmetic]
The modular-arithmetic tag has no usage guidance.
66
questions
27
votes
1answer
2k 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 ...
14
votes
2answers
989 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...
<...
11
votes
2answers
879 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.
...
10
votes
2answers
1k 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 ...
10
votes
6answers
628 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:
...
9
votes
3answers
996 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:
...
9
votes
2answers
601 views
MatrixPower with Modulus
I have a matrix that will be multiplied with itself by an extremely large amount of times under $Z/pZ$. The matrix itself contains small numbers, so ...
9
votes
1answer
5k 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 ...
9
votes
1answer
164 views
Modular equation problem
I have problem solving this modular equation $67^n \equiv 67 \pmod {317026939759222841944}$ with $n>1$. I have tried my Laptop and Wolfram Alpha engine, but I don't get any solution, I'm very ...
8
votes
1answer
258 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 ...
8
votes
1answer
147 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
<...
7
votes
1answer
1k 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 ...
6
votes
2answers
192 views
Memory problem when solving a system of modular equations [duplicate]
I need to solve the following system of modular equations, but the computation can't finish because I run out of memory (I have 12 GB of RAM). Is there any workaround to this problem? I am using ...
6
votes
1answer
318 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
1k 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[...
6
votes
2answers
719 views
How can I solve a certain congruence equation?
I want to solve the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$.
I know that one way to solve this is to first solve the congruence:
$t^2 \equiv 5 \pmod {19}$, because $b^2 - 4ac \equiv 24 \equiv ...
6
votes
1answer
187 views
RowReduce modulo 3
When I wanted to compute a row echelon form of a matrix over the finite field ${\Bbb F}_9$ with 9 elements (which is the three element field ${\Bbb F}_3$ adjoined a square root of $-1$ which I denote ...
5
votes
1answer
609 views
modulo with n instead of 0 without using if-statement
Is there a way to to express the following without using an if statement, but with mathematical operations instead?
{ 5 if x % 5 = 0, x % 5 otherwise }
5
votes
2answers
3k 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
813 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 ...
4
votes
3answers
328 views
How to reverse in modular arithmetic
Given an RGB color {127, 255, 212} where scale is 0-255, VBA's RGB function find a long integer x such that
...
4
votes
1answer
1k 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 ...
4
votes
1answer
188 views
Matrix operations “Modulus->non-prime” problem
I am using Mathematica 10.4.1.0. When I specify the "Modulus" option to be a non-prime, the functions RowReduce and MatrixRank return the error
...
4
votes
0answers
148 views
Sparse matrix multiplication mod p
Let A and B be sparse matrices with integer coefficients between 0 and ...
3
votes
2answers
1k 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
122 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
2answers
261 views
Evaluate modular fractions
If I have a list of numbers l = {256/11, 258/11, 263/11, 263/11, -22, -22, 251/11, 0, 261/11, -22, 265/11, 259/11, 0, 259/11} which I want to evaluate mod 26, how ...
3
votes
1answer
83 views
List of invertible congruence classes
I am attempting to create a list of the invertible congruence classes $\bmod 120$.
The code I have is ...
3
votes
1answer
170 views
Coppersmith method of small integer solutions to multivariate polynomials
In http://link.springer.com/chapter/10.1007%2F3-540-68339-9_14#page-7 is presented a method for finding small solutions to multivariate polynomials. (Although here he mentions that it "is not rigorous"...
2
votes
2answers
8k 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
405 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
83 views
How to Plot modulo function Mod on a function of two variables? [closed]
I know that Plot[Mod[x, 2], {x, -6, 6}] is a Mathematica command to plot the remainder of x over 2 when I range x over reals -6 to 6. How do I plot the same ...
2
votes
1answer
140 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
106 views
How to solve a system with GCD?
For example,
Solve[{x + y == 150, GCD[x, y] == 30}, {x, y}, Integers]
Solve::nsmet: This system cannot be solved with the methods available to Solve.
The same ...
2
votes
1answer
140 views
How to remove symmetries from this list?
First of all, I work with modular arithmetics and the elements of the arithmetics are lists themselves.
I recognize two kinds of symmetries - shift and mirroring. We could define shift of a list like ...
2
votes
1answer
543 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 ...
2
votes
1answer
86 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
37 views
FindEquationalProof to prove divisor theorem
I'm trying to implement proofs of concepts for Equational Proofs on some basic number theory theorems.
One such example is:
"let a and b be positive integers and let d = gcd (a, b). If t divides ...
2
votes
0answers
114 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 ...
2
votes
0answers
370 views
Parallel PowerMod
Is there anyway to parallelize the PowerMod function?
Here is my Left-To-Right modular exponentation:
...
1
vote
1answer
2k 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
914 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
249 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
79 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
96 views
Polynomial PowerMod
Is there equivalent of PowerMod for polynomials in Mathematica?
We have Mod[a^e,m]==PowerMod[a,e,m], $a$, $e$ and $m$ all ...
1
vote
1answer
60 views
Is this decryption function idiomatic?
This is my first non-trivial Mathematica notebook, which I wrote for a cryptology homework. It encrypts/decrypts strings using an affine cipher. Is the code readable/idiomatic? How could it be ...
1
vote
2answers
922 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
72 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
1answer
3k 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
...
1
vote
1answer
297 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 ...
