# Questions tagged [modular-arithmetic]

The tag has no usage guidance.

64 questions
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 ...
2answers
950 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... <...
2answers
868 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. ...
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 ...
6answers
619 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: ...
3answers
885 views

### Mod[1.2, 0.2] is not equal to zero

Why doesn't the following expression evaluate to zero? In:=Mod[1.2, 0.2] Out=0.2 Edit: This is what I wanted to do: ...
2answers
527 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 ...
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 ...
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 ...
1answer
249 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 ...
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 <...
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 ...
2answers
186 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 ...
1answer
305 views

### Implementing Remainder Tree

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

1answer
800 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 ...
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 ...
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 ...
1answer
158 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 ...
0answers
137 views

### Sparse matrix multiplication mod p

Let A and B be sparse matrices with integer coefficients between 0 and ...
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 ...
2answers
114 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 ...
2answers
243 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 ...
1answer
60 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 ...
1answer
133 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 ...
1answer
151 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"...
2answers
7k 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 ...
2answers
401 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 ...
1answer
135 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 ...
1answer
75 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 ...
1answer
477 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 ...
1answer
85 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$: ...
0answers
105 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 ...
0answers
366 views

### Parallel PowerMod

Is there anyway to parallelize the PowerMod function? Here is my Left-To-Right modular exponentation: ...
1answer
1k views

### Matrix Multiplication Modulo 2

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

0answers
63 views

### Last digits via PowerMod [closed]

Do you have an idea why this produces different results? PowerMod[2003, 2002^2001, 1000] 241 ...
0answers
65 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 ...