Math 5248 in-class test, Nov 8, 2023 Problem 1 (10 pts)

9973 is a prime (no need to prove it, Table 2 in the texbook on pp. 361-62 lists it as the largest prime below 10,000). Evaluate

94986 mod 9973

without any non-trivial computation (and explain how you did it).

Find an integer n with such that

Problem 2 (15 pts)

0 ≤ n < 47 × 79 = 3713, n ≡ 79 mod 47,

n ≡ 47 mod 79.

Problem 3 (20 pts)

p = 241 and q = 281 are primes. Consider RSA cipher with modulus n = pq = 67721. What is the smallest public encryption key e that you can use? Find the secret decryption key d for this public key e.

Problem 4 (15 pts)

Table 3 in the book (p. 363) tells us that 92 is a primitive root modulo 97. What is the most efficient way to verify this is not a typo? (No need to carry out the computations.)

Problem 5 (10 + 10 pts)

(a) Is there an integer solution x to x3 ≡ 6 mod 79 ?

(b) Is there an integer solution x to x3 ≡ 6 mod 80 ?

No need to produce a solution if any exist, only existence is to be determined.

Problem 6 (20 pts)

Find a square root of 2 modulo 232 = 529.