14
"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 not be used interchangeably. It would be incorrect to say "19 and 64 are congruent modulus 5". It would also be incorrect to "the modulo is 5".
See also ...
12
Modular exponentiation is a well-known algorithm. It is routinely available in libraries and languages that can manipulate large integers, including Wolfram Alpha.
When making computations modulo a large number, one does not first make the whole computation in $\mathbb{N}$ and then take the remainder of the result, because for something like an ...
answered Nov 26 '14 at 22:42
Gilles 'SO- stop being evil'
39.8k77 gold badges105105 silver badges170170 bronze badges
9
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 b %= m line.) We want to calculate $ab \mod m$, which is to say, setting $x=ab$, we want to find $r_x$ such that $x = q_xm + r_x$ for some $q_x$.
The Non-Overflowing ...
answered Jun 21 '17 at 20:24
Derek Elkins left SE
11.6k11 gold badge2626 silver badges4141 bronze badges
8
A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.
answered Feb 2 '16 at 5:26
David Richerby
78.5k1717 gold badges125125 silver badges219219 bronze badges
6
There's a small chance you might be able to get a speed-up by using properties of arithmetic modulo $n^2$, depending on how $g$ was chosen.
Suppose $g=a(1+bn)$. Then note that, by the binomial theorem,
$$g^x = a^x (1+bn)^x = a^x \sum_i {x \choose i} (bn)^i = a^x (1 + bx n + n^2 \times \text{stuff})$$
so we see that
$$g^x = a^x (1 + bx n) \pmod{n^2}$$
...
5
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 + and *. In particular, a+b has the same remainder as mod_p(a) + mod_p(b) and a*b, the same as mod_p(a)*mod_p(b).
So, mod_p(a_0 + a_1*2^8 + a_2*2^16 + ...) = mod_p(mod_p(a_0) + mod_p(a_1)*mod_p(2^...
5
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 continuing to read.
There's a theorem that says, if $x \times y \cong z \mod m$, then $x' \times y \cong z \mod m$, for any $x' \cong x \mod m$. This means that, ...
4
There are many other solutions. For example, even keeping your True and False, you can have $a\lor b = 1 - (1-a)(1-b) = a+b-ab = a + (1-a)b$ and so on.
answered Nov 11 '13 at 7:20
Yuval Filmus
242k2020 gold badges244244 silver badges427427 bronze badges
4
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 for some unknown reason
Those matrices assignments seem to be a fancy way of writing:
$$ \gcd(m_0, \color{blue}{a_0}) = \gcd(a_0, \color{red}{m_0 \pmod{a_0}}) = ...
4
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, then you can find a solution to a single equation
$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$
in polynomial time (if one exists) by factoring the polynomial $...
4
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\}$.
4
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 value of polynomial modulo 10. We will just say "the remainder of some number" to mean the least positive remainder of that number divided by 10. (The ...
4
Write down the first 10 or so powers modulo 10. Do you see a pattern?
3
For $a,b \in \{0,\ldots,n\}$, subtraction is given by
$$
a - b = [a + (n+1-b)] \bmod{(n+1)}.
$$
answered Jul 18 '17 at 18:35
Yuval Filmus
242k2020 gold badges244244 silver badges427427 bronze badges
3
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$. The inverse of $a$ modulo $n$ is thus $x$.
The extended Euclidean algorithm gives a constructive proof of Bézout's identity, which states that for all integers $...
answered Oct 4 '15 at 14:08
Yuval Filmus
242k2020 gold badges244244 silver badges427427 bronze badges
3
Your question hits at the main part of the faster algorithm presented in the paper. Many people know the usual (base-2) "repeated squaring" algorithm to compute $g^n$ is to write $n$ in binary:
$$
n=\sum_{i=0}^m e_i2^i\qquad e_i\in\{0,1\}
$$
so
$$
g^n=g^{e_02^0+e_12^1+e_22^2+\dotsm}=(g^{2^0})^{e_0}(g^{2^1})^{e_1}(g^{2^2})^{e_2}\dotsm
$$
and observe that $g^{...
3
$$2^N \bmod 10 = 2^{(N-1) \bmod 4 + 1} \bmod 10$$
(try to prove it)
3
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 dividing by $2^b$ and rounding down.
3
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$, then $a^3 \equiv b^3 \pmod 7$. So, if there was any solution to $a^3 \equiv 5 \pmod 7$, then you could take $b = a \bmod 7$, and that would be another solution. ...
2
If $a = \prod_i a_i$ and $b = \prod_j b_j$ then $$\frac{a}{b} \pmod{m} = \prod_i a_i \pmod{m} \times \prod_j b_i^{-1} \pmod{m},$$
where the products on the right are performed modulo $m$.
answered Nov 12 '14 at 21:31
Yuval Filmus
242k2020 gold badges244244 silver badges427427 bronze badges
2
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 ones in the input; then divisible by 4 would correspond to even, and not divisible by 4 would correspond to odd. Since we have parity gates in our disposal, we ...
answered Apr 23 '16 at 11:18
Yuval Filmus
242k2020 gold badges244244 silver badges427427 bronze badges
2
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. Finally, 'modulo' is its ablative case. I believe that 'a is congruent to b modulo m' literally means something like 'a is congruent to b in the modulus m'.
English ...
2
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 $O (\max (N, M) \log \max (N, M))$ steps, and then you just rearrange the resulting values and add $P (0)$ which is just the constant coefficient of the ...
2
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 middle, adding other entries), you would need a little extra information to be able to insert into the middle at a latter access.
As I see it , You need need to ...
2
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: You can calculate $x^{12345}$ with about 25 multiplications, not 12345.
Hint 3: Probably less than 10 seconds for the last question if you find factors of n ...
2
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$. When we see a new input which leaves a remainder of $r$ after division by $k$, we count $m_{k-r}$ new pairs (where $m_k = m_0$), and then update the array $m$.
...
answered Jan 3 '17 at 15:27
Yuval Filmus
242k2020 gold badges244244 silver badges427427 bronze badges
2
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 remainder in the division of $a$ by $p$. Efficient implementations are also available in libraries like GMP.
answered Nov 18 '16 at 11:24
Yuval Filmus
242k2020 gold badges244244 silver badges427427 bronze badges
2
$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(10 \bmod{7}, 17\bmod{7}) \bmod{7} = GCD(3, 3) \bmod 7 = 3 \bmod 7 = 3$$
The second is also false
$$ LCM(12, 18) \bmod 7 = 36 \bmod 7 = 1$$
but
$$ LCM(12 \bmod ...
2
What you are missing is the identity
$$
(a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}.
$$
answered Sep 27 '17 at 10:08
Yuval Filmus
242k2020 gold badges244244 silver badges427427 bronze badges
Only top voted, non community-wiki answers of a minimum length are eligible
Related Tags
modular-arithmetic × 69algorithms × 22
number-theory × 12
time-complexity × 8
complexity-theory × 5
algorithm-analysis × 5
arithmetic × 5
multiplication × 5
circuits × 4
cryptography × 4
arrays × 3
discrete-mathematics × 3
polynomials × 3
primes × 3
formal-languages × 2
optimization × 2
runtime-analysis × 2
proof-techniques × 2
polynomial-time × 2
encryption × 2
rolling-hash × 2
fast-fourier-transform × 2
terminology × 1
formal-grammars × 1
reference-request × 1