# Questions tagged [modular-arithmetic]

The tag has no usage guidance.

74 questions
Filter by
Sorted by
Tagged with
38 views

### Montgomery multiplication -- algorithm question

I am a beginner, but I think I understand how to do Montgomery multiplication. Also, there are online calculators (for dummies like me)... But I have a paper in front of me, that is all about how to ...
70 views

### What algorithm is prefered to do a x b mod P with big numbers (256 bits)

I'm trying to implement multiple precision arithmetic operations modulo P, with P < 2^256. More specifically, ...
36 views

### Which is (if any) the generic fastest method to perform modular exponentiation?

After a bit of surfing, I have found that Schönhage–Strassen (without taking in consideration recent optimizations) seems to be the base algorithm to perform the requested operation. Anyways, this ...
44 views

### Is quadratic nonresiduosity in $\textbf{NP}$?

The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an ...
168 views

56 views

60 views

### Finding solutions to $n m\equiv x \mod n$

Given a modulus $n\in\mathbb{N}$ and another natural number $0<x<n$, what's an efficient algorithm to enumerate all pairs of natural numbers $(a,b)\in\mathbb{N}^2$ such that both $a$ and $b$ are ...
261 views

### Smallest multiple of a number that gives a specific remainder modulo another number

Given three positive integers $a, b$ and $c$, my task to find the smallest positive integer $k$ such that $(k * a) \mod b = c$. I can obviously try values of $k$ from $1$ and higher, until I find the ...
802 views

### modular arithmetic in rolling hash algorithm

My question was around the rolling hash function in RobinKarp algorithm. It is intuitive for me to understand how to get from xi to xi+1 without the mod, however with the mod i am not sure how we ...
1k views

### Calculating greatest common divisor and least common multiple modulo prime number

I'm trying to solve pretty complex problem with number theory and set of numbers. To make the problem more clear we are going to define $GCD(a, b)$ as the greates number that divides both $a$ and $b$...
91 views

### Is there an algorithm for a number line from $0$ to $n$

Where $n + 1 = 0$ and $0 - 1 = n$? The $n + 1 = 0$ case can be achieved by using the modulus operator, but I can't figure out how to treat the $0 - 1 = n$ case.
658 views

### 3-SAT and Systems of Nonlinear Modular Equations

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations? I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to ...
I was reading the Modular Multiplication page on wikipedia...and could not understand the algorithm to compute $a \cdot b \pmod{m}$. ...