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 ...
9
"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
A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.
6
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 ...
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)
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
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
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
Assuming you replace that second if with else if, the explanation of an even number of iterations is simple; you are repeatedly computing remainders, so each iteration swaps which of $x_{12}$ and $x_{22}$ is bigger. Each iteration alternately decreases $x_{12}$ or $x_{22}$ starting with $x_{22}$. Since the loop ends after decreasing $x_{12}$, you must go ...
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
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
$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 ...
2
Modular exponents can be computed efficiently using repeated squaring. This is a recursive method (which can also be implemented iteratively) that relies on the following two identities:
$$
a^{2k} = (a^k)^2, \qquad a^{2k+1} = a(a^k)^2.
$$
This allows us to give a recurrence for $f(a,b,n) = a^b \bmod n$:
$$
f(a,b,n) =
\begin{cases}
1 & \text{if } b = 0, \...
2
The standard algorithm for inverting an element is using the extended Euclidean algorithm. You can read all about this connection on Wikipedia.
2
One algorithm to compute inverses in a finite field is to raise to a large power. In particular, $x^{-1} = x^{p-2}$ if you are working in $\mathbb{F}_p$ (by Fermat's little theorem). You can use standard algorithms for fast modular exponentiation to compute this with about $2 \lg p$ multiplications, or fewer (depending on the specific value of $p$ and the ...
Only top voted, non community-wiki answers of a minimum length are eligible
