Lesson test: Fermat, Euler and RSA

Fermat, Euler and RSA

1.[2p]
Using Fermat's little theorem, find the remainder of $2^{1000}$ on division by $13$ , as a number from $0$ to $12$ .

CorrectNot quite: 3

2.[1p]
What is the last digit of $7^{222}$ ?

CorrectNot quite: 9

3.[3p]
Find the last two digits of $17^{2026}$ , entered as a whole number (for example, $07$ as $7$ ).

CorrectNot quite: 69

4.[2p]
Repeated squaring computes $a^{77} (mod n)$ by squaring and then multiplying together the squares it needs. How many multiplications does it use in all?

CorrectNot quite: 9

5.[2p]
An RSA key has $p = 11$ , $q = 17$ and public exponent $e = 7$ . Find the private exponent $d$ , as a number from $1$ to $φ (n) - 1$ .

CorrectNot quite: 23

6.[2p]
Encrypt the message $m = 2$ with the public key $(n, e) = (3233, 17)$ . Give $c$ as a number from $0$ to $3232$ .

CorrectNot quite: 1752

7.[3p]
An RSA modulus $n = 2021$ is the product of two primes, and a leak reveals $φ (n) = 1932$ . What is the larger of the two primes?

CorrectNot quite: 47

8.[3p]
Which of these statements are true?

Select all that apply

If $a^{n - 1} \equiv 1 (mod n)$ for some $a$ coprime to $n$ , then $n$ is prime

The answer is: If $2^{n - 1}$ is not congruent to $1$ modulo an odd $n$ , then $n$ is composite, In $a^{k} (mod n)$ with $\gcd (a, n) = 1$ , the exponent may be reduced modulo $φ (n)$ and the base modulo $n$ , RSA decryption returns the message even when the message shares a prime factor with $n$

If $2^{n - 1}$ is not congruent to $1$ modulo an odd $n$ , then $n$ is composite

Correct

In $a^{k} (mod n)$ with $\gcd (a, n) = 1$ , the exponent may be reduced modulo $φ (n)$ and the base modulo $n$

Correct

$φ (n)$ is always the smallest positive exponent $m$ with $a^{m} \equiv 1 (mod n)$

RSA decryption returns the message even when the message shares a prime factor with $n$

Correct

9.[2p]
Put these events in chronological order, earliest first.

RSA-250 is factored
Shor gives a quantum factoring algorithm
Fermat states his little theorem in a letter to Frénicle de Bessy
Rivest, Shamir and Adleman publish RSA
Clifford Cocks finds public-key encryption at GCHQ
Euler proves $a^{φ (n)} \equiv 1 (mod n)$

Show the answer

a, b, c, d, e, f

1.[2p] Using Fermat's little theorem, find the remainder of 21000 on division by 13, as a number from 0 to 12.

2.[1p] What is the last digit of 7222?

3.[3p] Find the last two digits of 172026, entered as a whole number (for example, 07 as 7).

4.[2p] Repeated squaring computes a77(modn) by squaring and then multiplying together the squares it needs. How many multiplications does it use in all?

5.[2p] An RSA key has p=11, q=17 and public exponent e=7. Find the private exponent d, as a number from 1 to φ(n)−1.

6.[2p] Encrypt the message m=2 with the public key (n,e)=(3233,17). Give c as a number from 0 to 3232.

7.[3p] An RSA modulus n=2021 is the product of two primes, and a leak reveals φ(n)=1932. What is the larger of the two primes?

8.[3p] Which of these statements are true?

9.[2p] Put these events in chronological order, earliest first.

1.[2p]
Using Fermat's little theorem, find the remainder of $2^{1000}$ on division by $13$ , as a number from $0$ to $12$ .

2.[1p]
What is the last digit of $7^{222}$ ?

3.[3p]
Find the last two digits of $17^{2026}$ , entered as a whole number (for example, $07$ as $7$ ).

4.[2p]
Repeated squaring computes $a^{77} (mod n)$ by squaring and then multiplying together the squares it needs. How many multiplications does it use in all?

5.[2p]
An RSA key has $p = 11$ , $q = 17$ and public exponent $e = 7$ . Find the private exponent $d$ , as a number from $1$ to $φ (n) - 1$ .

6.[2p]
Encrypt the message $m = 2$ with the public key $(n, e) = (3233, 17)$ . Give $c$ as a number from $0$ to $3232$ .

7.[3p]
An RSA modulus $n = 2021$ is the product of two primes, and a leak reveals $φ (n) = 1932$ . What is the larger of the two primes?

8.[3p]
Which of these statements are true?

9.[2p]
Put these events in chronological order, earliest first.