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'
37.7k7 gold badges101 silver badges166 bronze badges
11
"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 ...
7
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 ...
7
A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.
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.
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 idea and ...
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)}.
$$
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 $...
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$.
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 ...
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$.
...
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.
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
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 possible regardless of whether modular arithmetic is used or not.
Going back to what you wrote though. Without the modular arithmetic, the division by R is possible ...
Only top voted, non community-wiki answers of a minimum length are eligible
