CH5

Question 1

recall thm euler fermat

application

Answer 1

If a is coprime with n, then a^{ϕ(n)} ≡ 1 (mod n).

applications:
looking at RSA
how to we check if a large number is prime?

Question 2

Definition 5.1.1 (The RSA algorithm)

Answer 2

First of all, we generate the keys.
(1) fix a product N = pq of two large distinct prime numbers;
(2) compute ϕ(N) = (p − 1)(q − 1);
(3) pick some e with 1 < e < ϕ(N) such that e is coprime to ϕ(N);
(4) the** public key is the pair (N, e);**
(5) compute s such that es ≡ 1 (mod ϕ(N));
(6) the private key is the pair (N, s);
(7) throw away the numbers p, q, ϕ(N).
A message (either plaintext or cyphertext) is an integer m with 0 < m < N. in {1,2,…,N-1}
* To encrypt m: compute the remainder r of m^e modulo N.
* To decrypt r: compute the remainder m of r^s modulo N.

Question 3

By the Euler-Fermat theorem, encrypting and decrypting a message returns the original back:

Answer 3

(m^e)^s = m^{1+kϕ(N)} ≡ m (mod N).

large primes
Encryption and decryption are symmetric

Question 4

Example 5.1.2. Let us write calendar dates in the format DDMM as four-digit numbers.
For example, the 5th of November is 0511 = 511. Suppose someone has encoded their birthday using RSA with public key (3599, 17) and obtained 725. What is their
birthday?

Answer 4

First of all, we must finish generating the keys. If we factorise N =
3599, we find N = 59 · 61, hence ϕ(N) = 58 · 60 = 3480.
We then use Euclid’s algorithm(links to Bezouts lemma proof):
3480 = 204 · 17 + 12
17 = 1 · 12 + 5
12 = 2 · 5 + 2
5 = 2 · 2 + 1
2 = 2 · 1 + 0.
Reversing the equalities:
1 = 5 − 2 · 2 = 5 − 2 · (12 − 2 · 5) = 5 · 5 − 2 · 12
= 5 · (17 − 1 · 12) − 2 · 12 = 5 · 17 − 7 · 12
= 5 · 17 − 7 · (3480 − 204 · 17) = 1433 · 17 − 7 · 3480.

Thus s = 1433 works as a private key: indeed, se = 1433 · 17 ≡ 1 (mod 3480).

In turn, we calculate 725^1433 modulo 3599 and find 2701. :

725¹⁴³³=725⁷¹⁶*²⁺¹ = (725²)⁷¹⁶ .725
repeated squares again and again will help efficiently calc

modulo 3599

So the birthday is the 27th
of January.

here we break the encryption without knowing private key
(REALLY REALLY important- do ex in PS3 )

Question 5

when do we break the encryption?

Answer 5

because 3599 is a small number that we can easily factor by hand, at worst with the help of a calculator.

RSA relies on the fact that factorising a large number can take an impossible amount of time
To generate good RSA keys, we must be able to generate large prime numbers

Question 6

Example 5.2.1. If n is prime, and gcd(a, n) = 1, then a^{n−1} congruent to?

when does this fail?

Can we use to test primes?

Answer 6

aⁿ⁻¹≡ 1 (mod n). Thus, if the
congruence fails for some a chosen at random, n is definitely not prime.

e.g
n=21
a = 2: we have 2²⁰ ≡ 2⁸ (because ϕ(21) = 12), thus
2⁸ ≡ (2⁴)²≡ (−5)² ≡ 4 ̸≡ 1 modulo 21.

A much less obvious example is
n = 2³² + 1 = 4294967297 and a = 3. Then
3ⁿ⁻¹ = 3²^³²
≡ . . . (32 squaring later) . . . ≡ 3029026160 ̸≡ 1 (mod n).
Thus n cannot be prime.

strategy isn’t the best, not reliable

Question 7

why not reliable to test primes by seeing if aⁿ⁻¹≡ 1 (mod n).

Answer 7

strategy isn’t the best, not reliable infinitely many ns s.t congruent to 1 and n is composite: these are called Carmichael numbers

there are infinitely many of them

approx n^{2/7}of them in {1,.. n} as n goes to infinity

Question 8

Definition 5.2.2 (Carmichael numbers)

Answer 8

An integer n > 1 is a Carmichael number if a^n ≡ a (mod n) for every a ∈ Z.

Question 9

Example 5.2.3. The smallest Carmichael number is n = 561

Answer 9

n = 561 = 3 · 11 · 17. Indeed,
observe that n − 1 = 560 is divisible by 2 = 3 − 1, 10 = 11 − 1, 16 = 17 − 1. Then pick
some arbitrary a, and note that:
* if 3 ∤ a, then a² ≡ 1 (mod 3), thus a⁵⁶¹ = a²⁸⁰²⁺¹≡ a (mod 3);
if 3 | a, then also a³ ≡ 0 ≡ a (mod 3);
* if 11 ∤ a, then a¹⁰ ≡ 1 (mod 11), thus a⁵⁶¹ = a⁵⁶¹⁰⁺¹ ≡ a (mod 11); if 11 | a,
then also a¹¹ ≡ a (mod 11);
* if 17 ∤ a, then a¹⁶ ≡ 1 (mod 17), thus a⁵⁶¹ = a³⁵*¹⁶⁺¹ ≡ a (mod 17); again, if
17 | a, then a¹⁷ ≡ a (mod 17).

BY CRT: a⁵⁶¹≡ a (mod 561).

(FLT a⁵⁶⁰ ≡1 mod 561
a⁵⁶⁰ ≡a^2≡ 1 mod 561??)

Question 10

Exercise 5.2.4 (⋆⋆, in exercise sheet). Show that a composite number n is a Carmichael
number if and only if whenever a prime p divides n, then (p − 1) | (n − 1) and p^2∤ n.
(This is known as ‘Korselt’s criterion’, 1899)

Answer 10

.

when you attempt, notice it matches when checking if is a carmichael number for our prev example 561: prime divisors 3,11,17 of 561 well 10 divides 560 2 divides 560, 16 divides 560 etc becomes generalised in this exercise

tricky exercise

Question 11

Exercise 5.2.5 (Extra). Use Korselt’s criterion to verify that 561 is the smallest Carmichael number.

Some hints below. Let n be a Carmichael number.
(1) Show that n must be odd.
(2) Show that n must be the product of at least three primes.
(3) Suppose that n = pqr for p, q,r distinct odd primes. Show that pq ≡ 1 (mod r − 1).
(4) Suppose n = 3qr, 3 < q < r: deduce that q ≥ 11 and r ≥ 17. Thus the Carmichael
numbers of this form are ≥ 561
(5) Suppose n = 5qr: deduce that q ≥ 13 and r ≥ 17. Thus the Carmichael numbers
of this form are ≥ 1105 (which happens to be Carmichael).
(6) Deduce that 561 is the smallest Carmichael number (just check how big the remaining product of distinct primes are).

Answer 11

(1) Suppose by contradiction that n is even. It is not divisible by 4, so it is divisible
by some odd prime p. Then (p − 1) | (n − 1), but p − 1 is even and n − 1 is
odd, a contradiction.
(2) Suppose that n = pq for two distinct primes p, q. Then (p − 1) | (pq − 1), so
1 ≡ pq ≡ q (mod p−1), hence (p−1) | (q−1). By symmetry, (q−1) | (p−1),
so p = q, a contradiction.
(3) Same as above: r ≡ 1 (mod r − 1), while (r − 1) | (pqr − 1), thus 1 ≡ pqr ≡ pq
(mod r − 1).
(4) Suppose n = 3qr, 3 < q < r. We have 3r ≡ 1 (mod q − 1). It follows that
gcd(3, q − 1) = 1 and similarly gcd(3, r − 1) = 1. This excludes the primes 7
and 13 right away for both q and r.
If q = 5, then 15 ≡ 1 (mod r − 1), thus (r − 1) | 14, hence r ∈ {3, 8, 15}, a
contradiction. Thus q ≥ 11, hence r ≥ 13 > 11, and so r ≥ 17.
(5) Suppose n = 5qr, 5 < q < r. Just like before, 5q ≡ 1 (mod r − 1), so gcd(5, r −
1) = 1, and similarly gcd(5, q − 1) = 1. This excludes 11 for both q and r.
If q = 7, then 5q = 35 ≡ 1 (mod r − 1), hence r − 1 | 34, so r ∈ {3, 18, 35}, a
contradiction. Thus, q ≥ 13, and in turn r ≥ 17 > 13.
(6) If n is a product of three primes and not divisible by 3 nor 5, then it is at least
n ≥ 7 · 11 · 13 = 1001 > 561, and if it is a product of four or more primes, then
n ≥ 3 · 5 · 7 · 11 = 1155 > 561.

Question 12

Proposition 5.3.1

Detecting composite numbers with primitive roots
We can spot non-primes better by playing with orders

Witness liar

Answer 12

Let n > 1 be an integer and p_1, . . . , p_t be the distinct prime factors of n − 1. If for some a we have
(1)
aⁿ⁻¹≡ 1 (mod n)
and
a[ⁿ⁻¹]/[ᵖ-ᶦ]/≡ 1 (mod n) for all i,
then n is prime.

To simplify the discussion: an a satisfying (1) is a witness that n is prime. If n is prime but a does not satisfy (1), we call a liar.

Question 13

a witness or a liar?

Answer 13

an a satisfying (1) is a witness that n is prime. If n is prime
but a does not satisfy (1), we call a liar.

witness could be prime or Carmichael number

Question 14

proof for PROPn

Let n > 1 be an integer and p_1, . . . , p_t be the distinct prime factors of
n − 1. If for some a we have
(1)aⁿ⁻¹≡ 1 (mod n)
and
a[ⁿ⁻¹]/[ᵖ-ᶦ]≡ 1 (mod n) for all i,
then n is prime.

To simplify the discussion: an a satisfying (1) is a witness that n is prime. If n is prime
but a does not satisfy (1), we call a liar.

Answer 14

Proof. A witness a must be coprime to n and have order n − 1 modulo n.

and for all number k strictly less than n-1
a^k is not going to be congruent to 1

we know that if a^k ≡ 1 then a^(gcd(n-1,k) ≡ 1 by bezouts lemma

therefore a has order n-1

Since a^{ϕ(n)} ≡ 1 (mod n), we must have n − 1 ≤ ϕ(n). Therefore, ϕ(n) = n − 1, thus n is prime. □

Question 15

Example 5.3.2. Let us determine if 700001 is prime

Use the fact that 3⁷⁰⁰⁰⁰⁰≡ 1 (mod 700001)

Answer 15

3⁷⁰⁰⁰⁰⁰≡ 1 (mod 700001)
(squaring and taking the 5th power)
The prime factors of 700000 are 2, 5, 7, so dividing by these:

3³⁵⁰⁰⁰⁰ ≡ 700000 ̸≡ 1 (mod 700001),
3¹⁴⁰⁰⁰⁰ ≡ 425344 ̸≡ 1 (mod 700001),
3¹⁰⁰⁰⁰⁰ ≡ 591336 ̸≡ 1 (mod 700001).
Therefore, 700001 is prime.

Question 16

explaining this check for primes:

Answer 16

input n: we try random a and check (1) find a s.t it holds we see its prime
2) n probably not prime if we find an a s.t this doesn’t hold (a might not be coprime? no)
relates to the primitive roots:
using a smaller power that doesn’t give the congruent to 1 it has to be n-1

if n is prime: it has a primitive root- automatically a witness satisfies conditions(1)
and there are ϕ(n − 1) primitive roots modulo n
which is at least (n-1)(1/2^t) as all primes >2 so (1-(1/n)) > 1/2

links to probability of finding a liar (future proposition)

Question 17

PROP 5.3.3

The proof shows that the all primitive roots of n are witnesses that n is prime. Thus,
picking a at random has a decent probability of spotting that n is prime.

Answer 17

Let n, p₁, . . . , pₜ as in Proposition 5.3.1. If n is prime, then there are at least {n−1}/2ᵗ witnesses that n is prime among {1, . . . , n − 1}. Thus, the probability that N random values in {1, . . . , n − 1} are all liars is
≤ [1 −(1/2ᵗ) ]ᴺ

Thus, if we cannot find witnesses for large N, we can be reasonably confident that n is
composite

Question 18

proof for
Let n, p₁, . . . , pₜ as in Proposition 5.3.1. If n is prime, then there are at least {n−1}/2ᵗ witnesses that n is prime among {1, . . . , n − 1}. Thus, the probability that N random values in {1, . . . , n − 1} are all liars is
≤ [1 −(1/2ᵗ) ]ᴺ

Thus, if we cannot find witnesses for large N, we can be reasonably confident that n is
composite

Answer 18

If n is prime, then there are ϕ(n − 1) primitive roots modulo n. Since primitive roots are all witnesses, we find at least
ϕ(n − 1) =
(n − 1)(1 −(1/p_1)· · · (1 −(1/p_t)
≥[1 −(1/2ᵗ) ]
many witnesses.
Thus, the probability that a random a lies is 1 −[ϕ(n−1)]/[n−1] ≤ 1 − [1 −(1/2ᵗ)]

If we test N random
values, the probability that they are all liars is ≤ [1 −(1/2ᵗ) ]ᴺ

Of course, the major flaw in this plan is that we must factor n − 1, and that might take ages for large values of n

Question 19

Proposition 5.4.
Detecting primes with the Miller-Rabin test

(I divide by 2 as much as I can)

Answer 19

Let n > 1 be an integer and write n − 1 = 2ᵏm with m odd. If for
some a in {1, 2, . . . , n − 1} we have
(2) aᵐ ̸≡ 1 (mod n) and a²^{ˡ} ᵐ ̸≡ −1 (mod n) for all 0 ≤ ℓ < k,
then n is composite.
note its a^{2^{l}m}

We now flip the perspective: an a satisfying (2) is a witness that n is composite; if n is composite but a does not satisfy (2), call a liar

Question 20

Let n > 1 be an integer and write n − 1 = 2ᵏm with m odd. If for
some a in {1, 2, . . . , n − 1} we have
(2) aᵐ ̸≡ 1 (mod n) and a²ˡᵐ ̸≡ −1 (mod n) for all 0 ≤ ℓ < k,
then n is composite.

We now flip the perspective: an a satisfying (2) is a witness that n is composite; if n is composite but a does not satisfy (2), call a liar

PROOF

Answer 20

proof is in the notes only mentioned:

Suppose that n is prime. By Fermat’s Little Theorem,
a{²^ᵏ} ᵐ = aⁿ⁻¹ ≡ 1 (mod n).
Let 0 ≤ s ≤ k be minimal with a{²^ˢ}ᵐ ≡ 1 (mod n)
(at worst, we find s = k).
If s = 0, then
(2) fails. If s > 0, let ℓ = s − 1 < k and x = a^{2^{ℓ} m}. Then
x^2 =
(a^{2^{ℓ}m})^2
= a^{2^{ℓ+1}m} = a^{2^{s}m} ≡ 1 (mod n).
Since n is prime, we have x ≡ ±1 (mod n) (because n divides x^2 − 1 = (x + 1)(x −1)). By the minimality of s, we have x ≡ −1 (mod n). In other words, a^{2^{ℓ}m} ≡ −1
(mod n), thus (2) does not hold.

Question 21

Example 5.4.2. When (2) fails in propn
Let n > 1 be an integer and write n − 1 = 2ᵏm with m odd. If for
some a in {1, 2, . . . , n − 1} we have
(2) aᵐ ̸≡ 1 (mod n) and a²ˡᵐ ̸≡ −1 (mod n) for all 0 ≤ ℓ < k,
then n is composite.

We now flip the perspective: an a satisfying (2) is a witness that n is composite; if n is composite but a does not satisfy (2), call a liar

Answer 21

when fails
means that the seq
not mentioned in lectures

(aᵐ, (aᵐ)²,((aᵐ)²)²,…., a ⁽ⁿ⁻¹⁾/²) of successive squares either starts with 1:
(1,…,1)
or hits -1
(b,c,d,…,-1,1,1,…,1)
mod n

Let n=41 (we know prime)
n-1=40= 2^3 x 5
so m=5 k=3
trying some values of a ∈ {1, . . . , n − 1}

• a = 2: here aᵐ = 2⁵ = 32, and (32, 32², 32⁴) ≡ (−9, −1, 1) (mod 41);
• a = 3: here 3⁵ ≡ −1, and (3⁵,(3⁵)²,(3⁵)⁴) ≡ (−1, 1, 1) (mod 41);
• a = 5: here 5⁵ ≡ 9, and (5⁵,(5⁵)²,(5⁵)⁴) ≡ (9, −1, 1) (mod 41);
• a = 7: here 7⁵ ≡ −3, and (7⁵,(7⁵)²,(7⁵)⁴) ≡ (−3, 9, −1) (mod 41);
• a = 10: here 10⁵ ≡ 1, and (10⁵
  ,(10⁵)²,(10⁵)⁴) ≡ (1, 1, 1) (mod 41

thus for all we have tried the seq of successive squares always starts with 1 or hits -1 and is 1 after
a⁵, (a⁵)², (a⁵)⁴)

Question 22

thm 5.4.3 Miller Rabin test

Answer 22

not mentioned in lectures? Then mentioned in review🫠

Let n ≥ 5 be odd. Test (2) on N random values in {1, 2, . . . , n − 1}.
If n is composite, then the probability that N random values in {1, . . . , n − 1} are all
liars is ≤ 1/4^N .

Question 23

thm miller rabin extra mentions

Answer 23

only in notes: skipped
The Miller–Rabin test is fast: writing n − 1 = 2ᵏm is a matter of dividing n by 2 until it
becomes odd (at most ⌈log2
(n)⌉ times) and computing a^{2ˡm} is similarly fast. Then we simply
try as many a’s as we want until we find a witness.

If the purpose is generating primes, this is enough: when searching for primes of approximately N digits, one typically needs to try ≤ 2N random values to find a prime. We can check if each of those values is prime by trying the Miller–Rabin test for some N random values of a.
One can simply insist until one finds a prime; with a very high probability, the procedure will
stop quickly.
If instead you want to be sure that a particular n is prime, the matter is more delicate. If the
generalized Riemann Hypothesis is true, the smallest witness will be no greater than about
2(log(n))^2
, which guarantees that the Miller–Rabin test can find a witness in a short time (not just with high probability!). Without the Riemann hypothesis, the first reasonable algorithm was found in 2022 by Agrawal, Kayal, and Saxena – it is usually called the AKS test. The AKS
test will determine whether n is prime in no more than C(log(n))^{12} steps for some fixed C > 1
(the exponent 12 has been reduced to 6 by H.W. Lenstra and Pomerance).