Modular exponentiation and fast powering - Discrete Math

1. In a Diffie-Hellman key exchange with prime $p = 23$ and generator $g = 5$, Alice chooses secret $a = 8$ and must compute $g^a \bmod p = 5^8 \bmod 23$. Using repeated squaring, what intermediate values will Alice compute?
   Answer: $5^1 = 5, 5^2 = 2, 5^4 = 4, 5^8 = 16$ Computing powers of 5 modulo 23 using repeated squaring: $5^1 = 5$. $5^2 = 25 = 23 + 2 \equiv 2 \pmod{23}$. $5^4 = (5^2)^2 \equiv 2^2 = 4 \pmod{23}$. $5^8 = (5^4)^2 \equiv 4^2 = 16 \pmod{23}$. Option B incorrectly shows $5^2 = 25$ without reducing modulo 23. Option C has the wrong final value $5^8 = 9$. Option D has incorrect intermediate values $5^4 = 6$ and $5^8 = 13$.
2. Irene wants to compute $2^{1000} \bmod 1001$ efficiently. She discovers that $1001 = 7 \times 11 \times 13$ and uses the Chinese Remainder Theorem. If she finds $2^{1000} \equiv 1 \pmod{7}$, $2^{1000} \equiv 1 \pmod{11}$, and $2^{1000} \equiv 1 \pmod{13}$, but then realizes she made an error in one calculation, which of these is most likely incorrect?
   Answer: $2^{1000} \equiv 1 \pmod{13}$ because $2^{12} \equiv 1 \pmod{13}$ and $12 \mid 1000$ By Fermat's Little Theorem: For mod 7: $2^6 \equiv 1 \pmod{7}$, and since $1000 = 166 \times 6 + 4$, we get $2^{1000} \equiv 2^4 \equiv 16 \equiv 2 \pmod{7}$, not 1. For mod 11: $2^{10} \equiv 1 \pmod{11}$, and since $1000 = 100 \times 10$, we get $2^{1000} \equiv 1 \pmod{11}$. For mod 13: $2^{12} \equiv 1 \pmod{13}$, but $1000 = 83 \times 12 + 4$, so $2^{1000} \equiv 2^4 \equiv 16 \equiv 3 \pmod{13}$, not 1. The error in choice C is that 12 does not divide 1000 (since $1000 = 83 \times 12 + 4$). Choice A has the right reasoning but wrong conclusion. Choice B is actually correct. Choice D is wrong since not all are correct.
3. A cryptographic protocol requires computing $g^{ab} \bmod p$ where $a$ and $b$ are secret values, $g$ is a generator, and $p$ is a large prime. Two approaches are suggested: (1) Compute $g^a \bmod p$, then raise this result to the power $b$; (2) Compute $g^{ab \bmod (p-1)} \bmod p$ directly. Under what condition are these approaches equivalent?
   Answer: Always equivalent when $p$ is prime and $g$ is a generator Both approaches are mathematically equivalent when $p$ is prime and $\gcd(g,p) = 1$. Method 1: $(g^a)^b = g^{ab}$. Method 2: By Fermat's Little Theorem, $g^{p-1} \equiv 1 \pmod{p}$, so $g^{ab} \equiv g^{ab \bmod (p-1)} \pmod{p}$. Since $g$ is a generator of the multiplicative group mod $p$, we have $\gcd(g,p) = 1$, so FLT applies. The results are identical. Option B is wrong - we need $\gcd(g,p) = 1$, not $\gcd(g,p-1) = 1$. Option C is wrong - the equivalence holds for any values of $a,b$. Option D is wrong - they're mathematically equivalent regardless of computational differences.
4. To compute $3^{100} \bmod 7$ efficiently, Alice uses repeated squaring. She observes that $3^4 \equiv 4 \pmod{7}$. Using this observation and the binary representation $100 = 64 + 32 + 4$, what is the value of $3^{100} \bmod 7$?
   Answer: $4$ Since $100 = 64 + 32 + 4 = 2^6 + 2^5 + 2^2$, we have $3^{100} = 3^{64} \cdot 3^{32} \cdot 3^4$. Given $3^4 \equiv 4 \pmod{7}$, we compute: $3^8 \equiv 4^2 \equiv 16 \equiv 2 \pmod{7}$, $3^{16} \equiv 2^2 \equiv 4 \pmod{7}$, $3^{32} \equiv 4^2 \equiv 2 \pmod{7}$, $3^{64} \equiv 2^2 \equiv 4 \pmod{7}$. Therefore $3^{100} \equiv 4 \cdot 2 \cdot 4 \equiv 32 \equiv 4 \pmod{7}$. Choice A results from incorrectly applying Fermat's Little Theorem. Choice B comes from computational errors in the squaring process. Choice D results from missing the final reduction modulo 7.
5. To compute $3^{1000} \bmod 7$ efficiently, a student uses the fact that $3^6 \equiv 1 \pmod{7}$ by Fermat's Little Theorem. However, the student makes an error and computes $1000 \bmod 7 = 6$, concluding that $3^{1000} \equiv 3^6 \equiv 1 \pmod{7}$. What is the correct answer and what was the student's error?
   Answer: Correct answer is $3^4 \equiv 4 \pmod{7}$; student should have used $1000 \bmod 6$ The student's error is using $1000 \bmod 7$ instead of $1000 \bmod 6$. Since $3^6 \equiv 1 \pmod{7}$, we need $1000 \bmod (6) = 1000 \bmod 6$. We have $1000 = 166 \times 6 + 4$, so $1000 \equiv 4 \pmod{6}$. Therefore $3^{1000} \equiv 3^4 \pmod{7}$. Now $3^2 = 9 \equiv 2 \pmod{7}$ and $3^4 = (3^2)^2 \equiv 2^2 = 4 \pmod{7}$. So the correct answer is $3^4 \equiv 4 \pmod{7}$. The key insight is that when using $a^{\phi(n)} \equiv 1 \pmod{n}$, we reduce the exponent modulo $\phi(n)$, not modulo $n$.
6. For the computation $3^{2^{100}} \bmod 101$, a student wants to use Fermat's Little Theorem since 101 is prime. They need to reduce the exponent $2^{100}$ modulo 100. However, $2^{100}$ is astronomically large. What is the most efficient approach to find $2^{100} \bmod 100$?
   Answer: Factor $100 = 4 \times 25$, note $2^{100} \equiv 0 \pmod{4}$, and apply CRT with modulo 25 Since $100 = 4 \times 25$ and $\gcd(4,25) = 1$, we can use the Chinese Remainder Theorem. For mod 4: $2^{100} = (2^2)^{50} = 4^{50} \equiv 0 \pmod{4}$. For mod 25: Since $\gcd(2,25) = 1$ and $\phi(25) = 20$, we have $2^{20} \equiv 1 \pmod{25}$. Therefore $2^{100} = (2^{20})^5 \equiv 1^5 = 1 \pmod{25}$. By CRT, we need $x \equiv 0 \pmod{4}$ and $x \equiv 1 \pmod{25}$. Solving: $x = 25k + 1$ where $25k + 1 \equiv 0 \pmod{4}$, so $k + 1 \equiv 0 \pmod{4}$, giving $k = 3$, thus $x = 76$. Option A fails because Euler's theorem requires $\gcd(2,100) = 1$, but $\gcd(2,100) = 2 \neq 1$.
7. In RSA decryption, to compute $c^d \bmod n$ where $d = 157$ and $n = 323 = 17 \times 19$, a student decides to use Euler's theorem to reduce the exponent first. What is the reduced exponent that should be used?
   Answer: $157 \bmod 288 = 157$ For RSA with $n = p \times q$ where $p$ and $q$ are distinct primes, we use $\phi(n) = (p-1)(q-1)$. Here $\phi(323) = \phi(17 \times 19) = (17-1)(19-1) = 16 \times 18 = 288$. By Euler's theorem, if $\gcd(c,323) = 1$, then $c^{288} \equiv 1 \pmod{323}$. Therefore, $c^{157} \equiv c^{157 \bmod 288} \pmod{323}$. Since $157 < 288$, we have $157 \bmod 288 = 157$. The other options use incorrect values: 272 = 16×17 (wrong formula), 306 = 17×18 (another wrong formula), 324 = 18×18 (wrong formula).
8. In RSA encryption with modulus $n = 77 = 7 \times 11$, the public exponent is $e = 13$. To decrypt a message, David needs to compute $d \equiv e^{-1} \pmod{\phi(77)}$. Using the extended Euclidean algorithm, he finds that $13 \times 37 + 60 \times (-8) = 1$. What is the correct private exponent $d$?
   Answer: $37$ We have $\phi(77) = \phi(7 \times 11) = (7-1)(11-1) = 6 \times 10 = 60$. The equation $13 \times 37 + 60 \times (-8) = 1$ shows that $13 \times 37 \equiv 1 \pmod{60}$, so $d = 37$. We can verify: $13 \times 37 = 481 = 8 \times 60 + 1 \equiv 1 \pmod{60}$. Choice B (52) comes from incorrectly computing $60 - 8 = 52$. Choice C (25) results from computational errors in the extended Euclidean algorithm. Choice D (13) represents the misconception that $d = e$.
9. A student computing $11^{123} \bmod 35$ decides to use the Chinese Remainder Theorem since $35 = 5 \times 7$. They correctly find $11^{123} \equiv 1 \pmod{5}$ and $11^{123} \equiv 4 \pmod{7}$. To combine these using CRT, what equation must they solve?
   Answer: Find $x$ such that $x \equiv 1 \pmod{5}$ and $x \equiv 4 \pmod{7}$ When applying the Chinese Remainder Theorem (CRT), you're reconstructing a number from its remainders modulo coprime factors. Since $35 = 5 \times 7$ and $\gcd(5,7) = 1$, you can find $11^{123} \bmod 35$ by combining the individual congruences. The key insight is that you must preserve each congruence exactly as computed. Since the student found $11^{123} \equiv 1 \pmod{5}$ and $11^{123} \equiv 4 \pmod{7}$, the CRT system becomes: find $x$ such that $x \equiv 1 \pmod{5}$ and $x \equiv 4 \pmod{7}$. This is answer choice C. Answer A switches the moduli incorrectly, giving $x \equiv 1 \pmod{7}$ and $x \equiv 4 \pmod{5}$ — this would solve a different problem entirely. Answer B makes the same error, just written in different order. Both A and B represent the common mistake of mixing up which remainder goes with which modulus. Answer D is nonsensical, presenting $x \equiv 5 \pmod{1}$ and $x \equiv 7 \pmod{4}$. Since every integer is congruent to 0 modulo 1, the first congruence is impossible, and neither congruence relates to our original problem. Study tip: When setting up CRT systems, always match each remainder with its original modulus. Write down the congruences immediately after computing them to avoid mix-ups. The format is always "$x \equiv (\text{remainder}) \pmod{\text{original modulus}}$" for each piece.
10. To optimize the computation of $a^{65537} \bmod n$ (a common RSA public exponent), a programmer notes that $65537 = 2^{16} + 1$. This means the binary representation has exactly two 1-bits. What is the minimum number of modular multiplications required using this insight?
    Answer: 17 multiplications: 16 to compute $a^{2^{16}}$ plus 1 to multiply by $a$ When you encounter modular exponentiation problems, especially with large exponents, think about how the binary representation of the exponent can optimize your computation strategy. The key insight here is that $65537 = 2^{16} + 1$, which has binary representation $10000000000000001_2$ — exactly two 1-bits. To compute $a^{65537} \bmod n$ efficiently, you need to break this into $a^{2^{16}} \cdot a^1 \bmod n$. First, compute $a^{2^{16}}$ using repeated squaring: start with $a$, then square it 16 times to get $a^2, a^4, a^8, \ldots, a^{2^{16}}$. This requires exactly 16 multiplications. Then multiply this result by $a$ to get $a^{2^{16}} \cdot a = a^{65537}$, requiring 1 additional multiplication. Total: 17 multiplications. Option A misunderstands the optimization entirely — naive repeated multiplication would actually require 65,536 multiplications, not 32. Option B correctly identifies that standard repeated squaring for a general 17-bit number would need 16 squaring operations, but fails to account for the final multiplication step required when the exponent isn't a pure power of 2. Option D makes a conceptual error by claiming you only need 1 multiplication, ignoring that you must first compute $a^{2^{16}}$ before you can multiply it by $a$. The correct answer is C: 17 multiplications total. Study tip: When optimizing modular exponentiation, count every operation carefully. The binary method requires one multiplication per 1-bit in the exponent's binary representation, plus squaring operations to build the necessary powers.

Start this quiz