Discrete Math Quiz: Modular Exponentiation

10 questions · exam conditions

0:00

Modular ExponentiationQuestion 1 of 10

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?

157 \bmod 272 = 157

157 \bmod 306 = 157

157 \bmod 324 = 157

157 \bmod 288 = 157

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Modular Exponentiation

Practice Modular Exponentiation in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Modular Exponentiation, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

$157 \bmod 272 = 157$
$157 \bmod 306 = 157$
$157 \bmod 324 = 157$
$157 \bmod 288 = 157$ (correct answer)

Explanation: 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).

Question 2

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?

32 multiplications using a naive approach of repeated multiplication
16 multiplications using standard repeated squaring
17 multiplications: 16 to compute $a^{2^{16}}$ plus 1 to multiply by $a$ (correct answer)
1 multiplication using $a^{65537} = a^{2^{16}} \cdot a^1$

Explanation: 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.

Question 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?

Always equivalent when $p$ is prime and $g$ is a generator (correct answer)
Equivalent only when $\gcd(g, p-1) = 1$
Equivalent only when $ab < p-1$
Never equivalent due to different computational complexities

Explanation: 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.

Question 4

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?

$5^1 = 5, 5^2 = 2, 5^4 = 4, 5^8 = 16$ (correct answer)
$5^1 = 5, 5^2 = 25, 5^4 = 4, 5^8 = 16$
$5^1 = 5, 5^2 = 2, 5^4 = 4, 5^8 = 9$
$5^1 = 5, 5^2 = 2, 5^4 = 6, 5^8 = 13$

Explanation: 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

Question 5

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?

Find $x$ such that $x \equiv 1 \pmod{7}$ and $x \equiv 4 \pmod{5}$
Find $x$ such that $x \equiv 4 \pmod{5}$ and $x \equiv 1 \pmod{7}$
Find $x$ such that $x \equiv 1 \pmod{5}$ and $x \equiv 4 \pmod{7}$ (correct answer)
Find $x$ such that $x \equiv 5 \pmod{1}$ and $x \equiv 7 \pmod{4}$

Explanation: 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.

Question 6

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?

Correct answer is $3^4 \equiv 4 \pmod{7}$ ; student should have used $1000 \bmod 6$ (correct answer)
Correct answer is $3^6 \equiv 1 \pmod{7}$ ; student should have used $1000 \bmod 6$
Correct answer is $3^1 \equiv 3 \pmod{7}$ ; student should have used $1000 \bmod 6$
Correct answer is $3^2 \equiv 2 \pmod{7}$ ; student should have used $1000 \bmod 6$

Explanation: 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

Question 7

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$ ?

Use Euler's theorem: $\phi(100) = 40$ , so compute $2^{100 \bmod 40} = 2^{20} \bmod 100$
Factor $100 = 4 \times 25$ , note $2^{100} \equiv 0 \pmod{4}$ , and apply CRT with modulo 25 (correct answer)
Compute $2^{10} = 1024 \equiv 24 \pmod{100}$ and use repeated squaring thereafter
Apply Carmichael's theorem: $\lambda(100) = 20$ , so compute $2^{100 \bmod 20} \bmod 100$

Explanation: 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

Question 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$ ?

$37$ (correct answer)
$52$
$25$
$13$

Explanation: 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

Question 9

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$ ?

$1$
$2$
$4$ (correct answer)
$6$

Explanation: 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.

Question 10

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?

$2^{1000} \equiv 1 \pmod{7}$ because $2^6 \equiv 1 \pmod{7}$ and $6 \mid 1000$
$2^{1000} \equiv 1 \pmod{11}$ because $2^{10} \equiv 1 \pmod{11}$ and $10 \mid 1000$
$2^{1000} \equiv 1 \pmod{13}$ because $2^{12} \equiv 1 \pmod{13}$ and $12 \mid 1000$ (correct answer)
All three calculations are correct since $2^{1000} \equiv 1 \pmod{1001}$

Explanation: 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.