# Questions tagged [modular-arithmetic]

The tag has no usage guidance.

70 questions
Filter by
Sorted by
Tagged with
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 ...
1k 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... <...
893 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. ...
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 ...
641 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: ...
682 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 ...
1k 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: ...
6k 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 ...
166 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 ...
278 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 ...
149 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 <...
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 ...
194 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 ...
326 views

### Implementing Remainder Tree

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

261 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 ...
617 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 }
4k 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(...
840 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 ...
89 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 ...
340 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 ...
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 ...
210 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 ...
158 views

### Sparse matrix multiplication mod p

Let A and B be sparse matrices with integer coefficients between 0 and ...
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 ...
101 views

### how can I calculate $a_{n+3}=a_n+a_{n+1}+a_{n+2}$?

recently I need to calculate this: $a(n+1)=((a(n-2)+a(n-1)+a(n)) \bmod 10000)$ and get $a(20000000)$ (for example). I know RecurrenceTable,but ...
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 ...
292 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 ...
95 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 ...
189 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"...
9k 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 ...
411 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 ...
174 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 ...
142 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 ...
124 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 ...
150 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 ...
607 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 ...
90 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$: ...
38 views

### Why gives Modulo of complex numbers different answers for rationals and reals

When running Table[1.*Mod[(1 + I)^(1 + k*I), 1 + k*I], {k, 49, 50, 0.5}] Table[1.*Mod[(1 + I)^(1 + k*I), 1 + k*I], {k, 49, 50, 1/2}] I get for the first table <...
120 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 ...
373 views

### Parallel PowerMod

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