Questions tagged [modular-arithmetic]
The modular-arithmetic tag has no usage guidance.
1
vote
1answer
56 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 ...
3
votes
1answer
58 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 ...
1
vote
1answer
55 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 ...
4
votes
3answers
311 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
...
0
votes
1answer
41 views
Looping on ranges (Modular iterations)
Is it possible to make the following code modular, so that it works up till depth n, and returns an array of all possible combinations for used{}?
...
2
votes
1answer
73 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 ...
6
votes
1answer
121 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 ...
0
votes
0answers
72 views
Variables defined modulo $\pi$ and avoiding singularities; phase plotting for a map
I have the following $2$-dimensional implicitly defined map
...
1
vote
1answer
83 views
Solving a modular equation with a large modulus [duplicate]
I am having trouble solving this equation:
$17^n\equiv 1 \mod 640826899755722841329632946651705039010285107743541637238400825304943424424715705661705191669759$
for the smallest integer $n > 0$
I ...
0
votes
1answer
44 views
Get missing cyclic numbers via modulus?
Consider a list of numbers:
list = {1,2,3,4,5};
Taking a random set of three of these numbers:
...
4
votes
2answers
430 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 ...
4
votes
1answer
148 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
...
3
votes
1answer
131 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 ...
9
votes
1answer
160 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 ...
1
vote
0answers
63 views
Last digits via PowerMod [closed]
Do you have an idea why this produces different results?
PowerMod[2003, 2002^2001, 1000]
241
...
6
votes
2answers
185 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 ...
0
votes
0answers
53 views
Function to add two matrices mod 2 [duplicate]
I have:
lightstep[m_, gg_] :=
Which[gg == {1, 1}, m = Mod[m + m, 2]]
Then I entered:
A = {{1, 1, 0}, {1, 0, 0}, {0, 0, 0}}
...
1
vote
0answers
64 views
Finite fields package doesn't simplify
I'm trying to do arithmetic using the FiniteFields package. Supposing a is a generator of a Galois field (say GF(2^5)) I want to be able to simplify things like a^32 and (a^8)^-1. I don't care about ...
0
votes
1answer
56 views
Putting some calculations together to form an algorithm
Considering these below where n is an odd number, k is also an odd number less than n:
<...
3
votes
1answer
147 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"...
3
votes
2answers
231 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 ...
-2
votes
1answer
71 views
9
votes
2answers
510 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 ...
4
votes
0answers
137 views
Sparse matrix multiplication mod p
Let A and B be sparse matrices with integer coefficients between 0 and ...
1
vote
1answer
195 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$
2
votes
0answers
104 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
votes
3answers
111 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$, ...
2
votes
1answer
84 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
1answer
134 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 ...
3
votes
2answers
113 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 ...
8
votes
1answer
245 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
141 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
<...
1
vote
1answer
74 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 ...
26
votes
1answer
1k 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 ...
1
vote
0answers
71 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
1answer
67 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 ...
2
votes
2answers
6k 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
1answer
462 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 ...
1
vote
2answers
816 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'...
0
votes
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
...
9
votes
3answers
872 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:
...
1
vote
0answers
149 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 ...
2
votes
2answers
399 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 ...
1
vote
1answer
76 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 ...
6
votes
1answer
947 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[...
0
votes
1answer
236 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:
...
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 ...
1
vote
0answers
603 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 ...
1
vote
2answers
876 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^...
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(...
