25 votes
Accepted

What is the difference between modulo and modulus?

"modulo" is an operator. For instance, we might say "19 and 64 are congruent modulo 5". "modulus" is a noun. It describes the 5 in "modulo 5". We might say "the modulus is 5". No, the two should ...
D.W.'s user avatar
  • 156k
11 votes

modular multiplication

Here's a more compact and mathematical description of what is going on. Let $a$ and $b$ be the input, already reduced modulo $m$, so $a < m$ and $b < m$. (Code-wise, this means after the ...
Derek Elkins left SE's user avatar
8 votes
Accepted

Is the empty string of even length?

A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.
David Richerby's user avatar
5 votes
Accepted

Calculating modulus of large non-factored numbers

The map from natural numbers to the ring of remainders is a homomorphism, which is a way to say that it has all sorts of nice properties with respect to operations +...
Karolis Juodelė's user avatar
5 votes

how to calculate $2^{5000}$ mod 10 without calculator in fast way?

Consider the first few powers of 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024… Now take all of those mod 10: 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4… Try to solve it yourself, from this, before ...
Draconis's user avatar
  • 7,048
5 votes
Accepted

How does Pollard's rho algorithm work?

The idea behind Pollard $\rho$ is that if you take any function $f : [0, n - 1] \to [0, n - 1]$, the iteration $x_{k + 1} = f(x_k)$ must fall into a cycle eventually. Take now $f$ as a polynomial, and ...
vonbrand's user avatar
  • 13.9k
5 votes
Accepted

Understanding Rabin-Karp's rolling hash computation

Two modulo operations There are two modulo operations for a modulus $0\not=q\in\Bbb N$. $\newcommand{\q}{\!\!\pmod q}$ $\newcommand{\Q}{\text{mod}_q}$. Let $\text{mod}_q:\Bbb Z\to\Bbb Z/q\Bbb Z$, $\...
John L.'s user avatar
  • 38.6k
4 votes
Accepted

Curious about an old algorithm which calculates modular inverse

You can replace: $$ ~~q \leftarrow \Big\lfloor\frac{a - 1}{b}\Big\rfloor $$ $$ r \leftarrow a - q ~b $$ By $q, r \leftarrow \text{divmod}(a, ~ b)$ Algorithm terminates in even number of steps ...
Aristu's user avatar
  • 1,483
4 votes
Accepted

Meaning of $|w| ≡ 2 \mod 3$

Yes, $|w|$ is the length of $w$. So $|w| \equiv 2 \mod 3$ means that the length of w divided by three should have the remainder 2. It should be from the set $\{2, 5, 8, \dots\}$.
Peter Leupold's user avatar
4 votes
Accepted

3-SAT and Systems of Nonlinear Modular Equations

The answer depends on whether we're talking about a single equation, or a system of equations; and whether the modulus $m$ is prime or composite. A single equation When the modulus $m$ is prime, ...
D.W.'s user avatar
  • 156k
4 votes

Last digit of polynomial value

Remainder modulo 10 instead of last digit What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10. For simplicity, we will compute the ...
John L.'s user avatar
  • 38.6k
4 votes

how to calculate $2^{5000}$ mod 10 without calculator in fast way?

Write down the first 10 or so powers modulo 10. Do you see a pattern?
gnasher729's user avatar
  • 28.4k
4 votes

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

When the modulus is a prime $p$, you can compute quadratic residuosity in polynomial time using the Legendre symbol: $x$ is a quadratic residue mod $p$ iff $(x|p)=1$ or $0$. When the modulus is a ...
D.W.'s user avatar
  • 156k
3 votes

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

For $a,b \in \{0,\ldots,n\}$, subtraction is given by $$ a - b = [a + (n+1-b)] \bmod{(n+1)}. $$
Yuval Filmus's user avatar
3 votes
Accepted

Computing mod inverse?

In order to compute the inverse of $a$ modulo $n$, use the extended Euclidean algorithm to find the GCD of $a$ and $n$ (which should be 1), together with coefficients $x,y$ such that $ax + ny = 1$. ...
Yuval Filmus's user avatar
3 votes

Calculating greatest common divisor and least common multiple modulo prime number

$GCD$ and $LCM$ do not depend on an algorithm, they are mathematical functions on pair of integers. The first statement is false. A counterexample: $$GCD(10, 17)\bmod{7} = 1 \bmod 7 = 1$$ but $$GCD(...
fade2black's user avatar
  • 9,757
3 votes
Accepted

Computing MOD_4 function using MOD_2, OR, AND, NOT gates

Suppose for simplicity that the number of ones in the input is even, and we want to know whether it is divisible by 4 or not. Intuitively, what we would like to do is to somehow "halve" the number of ...
Yuval Filmus's user avatar
3 votes

how to calculate $2^{5000}$ mod 10 without calculator in fast way?

$$2^N \bmod 10 = 2^{(N-1) \bmod 4 + 1} \bmod 10$$ (try to prove it)
HEKTO's user avatar
  • 3,068
3 votes
Accepted

Simple generator of pseudo-random permutations of variable length short sequence

The low bits of a linear congruential generator are notoriously weak. Try to use only the higher order bits. Normally this is done by bit operations, but you can discard the bottom $b$ bits by ...
orlp's user avatar
  • 12.7k
3 votes
Accepted

How to prove properties about a specific modular arithmetic equivalence

You can prove it by calculating the value of $a^3 \bmod 7$ for $a=0,1,2,3,4,5,6$; if none of those yield 5, then you have proven the claim. Why is this sufficient? Well, if $a \equiv b \pmod 7$, ...
D.W.'s user avatar
  • 156k
3 votes
Accepted

Floating-point modular multiplication algorithm

A completely general solution for this is difficult to achieve if a wider floating-point format with at least twice the number of significand bits is not available. Normally, on common system ...
njuffa's user avatar
  • 500
2 votes

What is the difference between modulo and modulus?

My knowledge in Latin and etymology is very limited, but, 'modulus' is a Latin word, and the form 'modulus' is singular, nominative. 'moduli' is its plural form, again in the nominative case. ...
AYun's user avatar
  • 174
2 votes

Can we evaluate a polynomial of degree N modulo M at all M points, faster than Θ(mn) time?

The answer given at Multi-point evaluations of a polynomial mod p actually answers the question. Given a primitive root g of M, it is possible to evaluate $P (g^0), P (g^1), \ldots, P (g^{M-1})$ in $...
gnasher729's user avatar
  • 28.4k
2 votes

Adding a character in the middle (rolling hash)

With just the Rolling HASH for the whole ABBDE, you can not insert into the middle of it. But... as I understand rolling Hash... If you are building the hashes up as you go (adding into the ...
Phillip Williams's user avatar
2 votes

Time required for mod operation

Hint: If you want to calculate $1234567809^{12345}$ modulo 9087654321, you do not start by calculating $1234567809^{12345}$. After every operation, you reduce the result modulo 9087654321. Hint 2: ...
gnasher729's user avatar
  • 28.4k
2 votes
Accepted

Sum of two elements in set evenly divisible by k

This solution actually works in time $O(n+k)$. The idea is to maintain an array $m_0,\ldots,m_{k-1}$, where $m_r$ is the number inputs seen so far which leave a remainder of $r$ after division by $k$. ...
Yuval Filmus's user avatar
2 votes

Calculating modulus of large non-factored numbers

The modulo operation is one of the basic arithmetic operations. As such, you can use the division algorithm you learned in school (if they still teach it) to calculate $a \bmod p$, which is the ...
Yuval Filmus's user avatar
2 votes

modular arithmetic in rolling hash algorithm

The video actually does it the other way around, kicking out the term with the highest power and then multiplying by R. It turns out to not really make a difference, but this is clearly always ...
harold's user avatar
  • 2,018
2 votes
Accepted

modular arithmetic in rolling hash algorithm

What you are missing is the identity $$ (a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}. $$
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible