# Questions tagged [modular-arithmetic]

The tag has no usage guidance.

65 questions
Filter by
Sorted by
Tagged with
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 ...
968 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... <...
872 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 ...
625 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: ...
944 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: ...
570 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 ...
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 ...
161 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 ...
254 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 ...
144 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 ...
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 ...
315 views

### Implementing Remainder Tree

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

161 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 ...
3k views

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(... 1answer 806 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 316 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 171 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 143 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 117 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 253 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 75 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 155 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 402 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 40 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 ... 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 85 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 136 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 517 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 33 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 ... 0answers 112 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 367 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 889 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^... 1answer 217 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 1answer 77 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 ... 1answer 79 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 ... 1answer 58 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 ... 2answers 874 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'... 1answer 71 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 ... 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 ...
I am having trouble solving this equation: $17^n\equiv 1 \mod 640826899755722841329632946651705039010285107743541637238400825304943424424715705661705191669759$ for the smallest integer $n > 0$ I ...