Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Tag Info

Hot answers tagged modular-arithmetic

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 ...
• 12.1k
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 +...
• 3,677
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 ...
• 7,138
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 ...
• 14.1k
5 votes
Accepted

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$, $\... • 39k 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\}$. 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 ... • 1,483 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, ... • 161k 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 ... • 39k 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? • 30.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 ... • 161k 4 votes Accepted Name of graph family defined by modular sum Your graph class is the class of graphs that are a disjoint union of a clique and a bunch of bicliques, possibly singletons. We can safely assume that the labels$\ell(v) \in [0,T)$, and it is then ... • 16.5k 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)}.$$ • 278k 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(... • 9,837 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 ... • 278k 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) • 3,098 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 ... • 13.6k 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, ... • 161k 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 ... • 520 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. ... • 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 ... • 30.4k 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 ... • 278k 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 ... 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: ... • 30.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. ... • 278k 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 ... • 2,053 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}. $$• 278k 2 votes How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime? Based on your comments, I recommend go back to basics and first understand running time, bit-complexity, and the running time for multiplication well. Focus on that before you try to tackle any of ... • 161k 2 votes Accepted What is the big-\Omega complexity of Fermat's Little Theorem? 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} = (...
• 278k

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