Public-Key Math Essentials Checkpoint

Modular arithmetic, inverses, CRT, and RSA math basics.

1. An element a has a modular inverse mod m iff:

gcd(a, m) = 1 a is even m is prime a < m/2

2. If x = a mod m, then x is also equal to:

a + k*m for any integer k a^m a XOR m m - a

3. CRT gives a unique solution modulo M when moduli are:

Pairwise coprime All even All equal All prime powers

4. In RSA, the private exponent d satisfies:

e*d = 1 mod phi(n) e*d = 0 mod n d = e d = n - e

5. If p and q are primes, phi(p*q) equals:

(p-1)(q-1) p+q p*q (p+1)(q+1)

6. A linear congruence a*x = b (mod m) has a solution when:

gcd(a, m) divides b a is prime b is prime m is even

7. If g = gcd(a, m) divides b, how many solutions does a*x = b (mod m) have?

g 1 phi(m) m

8. Extended Euclid returns x,y such that:

a*x + b*y = gcd(a,b) a*x = b*y a*x + b*y = 1 always x = 1/a

9. Euler's theorem requires which condition on a and n?

gcd(a, n) = 1 n is prime a is even a < n/2

10. Which statement about modular inverses is true?

If m is prime and a != 0 mod m, then a has an inverse Every a has an inverse modulo any m Inverses exist only when a is even If a has an inverse, it is always 1

11. For non-coprime moduli, a CRT system has a solution only if:

Residues are congruent modulo gcd(m1, m2) Both moduli are prime Both residues are zero The moduli are equal

12. In RSA, why use lambda(n) = lcm(p-1, q-1) in the key equation?

It is the exponent of Z_n^* It equals n-1 It removes the need for modular inverses It guarantees n is prime

13. Why must RSA choose e with gcd(e, phi(n)) = 1?

So the modular inverse d exists So n is prime So encryption is faster So ciphertexts are smaller

14. Overflow is a real risk in modular arithmetic because:

Intermediate products can exceed integer limits Modulo cancels overflow automatically Addition is not associative Multiplication is commutative

15. True/False: If gcd(a, m) != 1, then a has no modular inverse mod m.

Auto-advance on pass