Gt Ga Notes Ra

Posted Oct 10, 2024 • Updated Oct 20, 2024

By yxlow 19 min read

Modular Arithmetic (RA1)

Short overview of topics:

• Math primer

◦ modular Arithmetic
◦ multiplicative inverses

◦ Euclidʼs GCD algorithm

• Fermatʼs little theorem

◦ RSA algorithm

• Primality testing

◦ is a number a prime number? or a composite number

◦ Generate random prime numbers

Huge integers

For huge n, consider n-bit integers, x,y, N, in the order of 1024 or even 2048 bits.

Modular Arithmetic

For integer x, x mod 2 = least significant bit of x, which tells you if x is even or odd. We can also
do this by x/2 and get the remainder.

For integer N ≥ 1 : xmodN is the remainder of x when divided by N.

Some additional notation:

X ≡ Y mod N

means X
N , Y
N have same remainder, another way of writing this is:

x mod N = r ⟺ x = qN + r, q, r ∈ Z

Then we have the following:

if x ≡ y mod N and a ≡ b mod N then x + a ≡ y + b mod N and xa ≡ yb mod N

Modular Exponentiation

n-bit numbers, compute x y mod N .

Consider the simple algorithm:

x mod N = a 1
x 2 ≡ a 1 x mod N = a 2
⋮
y
x = a y−1 x mod N = a n

Multiplying two n-bit numbers and dividing by a n-bit number takes O(n 2 ) per round, since we
have y rounds where y ≤ 2 n , the overall time complexity is O(n 2 2 n ) which is horrible

x mod N = a1
x ≡ (a 1 ) 2 mod N
2
= a2
x 4 ≡ (a 2 ) 2 mod N = a4
x 8 ≡ (a 4 ) 2 mod N = a8
⋮

Then we can look at the binary representation of y and find the appropriate a i . For example if
y = 25 = 11001, then we need a 24 =16 ∗ a a3 =8 ∗ a 20 =1 = a 25

Mod-Exp algorithm

Note that for even y, x y = (x y/2 ) 2 , and for odd y, x y = x(x ⌊y/2⌋ ) 2
  Plaintext 
mod-exp(x,y,N)
Input: n-bit integers, x,y N >= 0
Output: pow(x,y) mod N
if y = 0, return(1)
z = mod-exp(x, floor(y/2), N)
if y is even:
return (z^2 mod N)
else:
return (xz^2 mod N)

Multiplicative inverses

x is the multiplicative inverse of z mod N if xz ≡ 1 mod N , which can be re-written as :

x ≡ z −1 mod N

Note that the z is also the inverse of x, i.e z ≡ x −1 mod N

Note that the inverse is not guaranteed to exists, consider N = 14, what is the inverse of
4 mod 14?

Inverse: Existence

The key idea here is if x, N shares a common divisor, then it has no inverse.

Theorem: x −1 mod N exists if and only if gcd(x, N) = 1, gcd stands for greatest common
divisor. This also means x and N are relatively prime.

In addition, if we always report x −1 mod N in 0, 1, … , N − 1 if it exists, it is unique and does

not exists otherwise. For instance, 3 −1 ≡ 4 mod 11, but so is 15, 26, −7. Etc
3 ∗ −7 = −21 mod 11 = −1

Proof. Lets suppose x −1 mod N has two inverses,

y ≡ x −1 mod N, z ≡ x −1 mod N, y ≡ z, 0 ≤ y ≠ z ≤ N − 1.

This implies that xy ≡ xz ≡ 1 mod N . But if we multiply each by x −1 , then

x −1 xy ≡ x −1 xz mod N which implies y ≡ z mod N which is a contradiction.

Inverse: Non existence

if gcd(x, N) > 1 then x −1 ≡ mod N does not exists.

Lets assume z = x −1 mod N ⟹ xz ≡ 1 mod N and x, z shares a common divisor, k > 1

.

This means that xz = gN + 1, which means akz = g(bk) + 1, for some a and b since x, N
share some common divisor k. But this implies that k(az − gb) = 1, then az − gb = 1
k which
shows that az − gb is a fraction but az − gb is an integer since a,z,g,b are integers and k > 1,
which is a contradiction.

Euclid Rule

For integers x,y where x ≥ y > 0:

gcd(x, y) = gcd(x mod y, y)

Proof: gcd(x, y) = gcd(x − y, y), and if this is true we take x and minus y from it until we are
no longer able to do so. This gives us exactly x mod y.

Now, to proof gcd(x, y) = gcd(x − y, y):

• if d divides x, y then d divides x − y

• if d divides x − y, y, then it divides x since we can just sum them up.

Euclid’s GCD algorithm

 Plaintext 
Euclid(x,y):
input: integers (x,y) where x >= y >= 0
output: gcd(x,y)

if y = 0:
 return(x)
else:
return (Euclid(y, x mod y))

In the base case we are looking at y = 0, which is gcd(x, 0) What are the divisors of zero? How
should we define this? What is a reasonable manner of defining the divisors of zero? Well, we
got to this case by taking the GCD of sum multiple x with x:

gcd(x, 0) = gcd(kx, x) = x

Before we analyize the runtime analysis, lets prove:

Lemma: if x ≥ y then x mod y < x

2 .

• If y ≤ x/2 then x mod y ≤ y − 1 < y ≤ x/2

• If y > x/2, ⌊ xy ⌋ = 1 then x mod y = x − y < x − x
2 ≤ x
2

Note, because of the lemma, each rounds the values decreasings by half:

(x, y) → (y, x mod y) → (x mod y, y mod x mod y) ⟹ 2n rounds


   
< x2

So there is a total of 2n rounds. We can now do our run-time analysis.

Runtime analysis:

• x mod y takes O(N 2 ) time to compute where N is the number of bits, and this is for a
single round.

• Total of 2n rounds
• Total of O(n 3 ) runtime.

Extended Euclid Algorithm

This is to compute the inverse of x mod y. Suppose d = gcd(x, y) and we can express
d = xα + yβ and we have the following:

d = gcd(x, y) = d = xα + yβ
 if gcd(x, N) = 1 then x −1 mod N exists and we have the following:

d = 1 = xα + Nβ
1 ≡ xα + Nβ mod N

 
0
−1
x ≡ α mod N

Similarly,

β = N −1 mod X

 Plaintext 
Ext-Euclid(x,y)
input: integers, x,y where x >= y >= 0
output: integers d, α,β where d = gcd(x,y) and d = xα+yβ

# remember gcd(x,0) = x, so we just set α = 1,β = 0

if y = 0:
return (x,1,0)
else:
d,α',β' = Ext-Euclid(y, x mod y)
return (d, β', α' - floor(x/y)β')

The proof of the final expression can be found in the textbook, enjoy!

Runtime analysis:

• Similarly, O(n 2 ) to compute x mod y and calculating ⌊ xy ⌋

• n rounds
• Total of O(n 3 )

Summary:

• Fast Modular Exponentiation algorithm

• How to calculate multiplicative inverse

◦ Euclidʼs GCD algorithm - gcd(x, y)

 ◦ Extended Euclidʼs algorithm to compute x −1 mod N

RSA (RA2)

Fermat’s little theorem

If p is prime then for every 1 ≤ z ≤ p − 1, so gcd(z, p) = 1 then:

z p−1 ≡ 1 mod p

This is the basis of RSA algorithm and also allows us to test if a number x is prime.

Proof: Let S = 1, 2, 3, … , p − 1, S ′ = zS mod P = i × z mod p, i = 1, … , p − 1.

For example p = 7, z = 4, S = 1, 2, … , 6, S ′ = 4, 1, 5, 2, 5, 6. Notice that the sets are the

same, just in di�erent order, and we are going to use S = S ′ to prove Fermatʼs little theorem.

To proof that S = S ′ , we need to show elements of S ′ are distinct and non zero, which implies
|S ′ |= p − 1.

Part one - show that elements of S ′ are distinct and we do this by contradiction, suppose for
some i ≠ j:

iz ≡ jz mod P

And since P is a prime number, we know then that every element in S has an inverse mod P , so
z is an element in S since z is between a number 1, P − 1. Recall that: P is prime
⟹ z −1 mod p exists, multiplying both sides by z −1

izz −1 ≡ jzz −1 mod P

i ≡ j mod P

which is a contradiction.

Part two - Show that they are non zero. Suppose we have an index i such that:

iz ≡ 0 mod P
and since z −1 exists,

izz −1 ≡ 0z −1 mod P
i ≡ 0 mod P

which is also a contradiction since i is between 1, P − 1.

Back to the proof of Fermatʼs little theorem, is to show that z p−1 ≡ mod P if P is prime. We
have S = S ′ , then:

P −1 P −1
∏ i ≡ ∏ i × z mod P
i=1 i=1
P −1
(P − 1)! ≡ z (P − 1)! mod P
Since 1 −1 , 2 −1 , 3 −1 , . . . ,(P − 1) −1 exists:
(P − 1)! ≡ z P −1 (P − 1)! mod P
1 ≡ z P −1 mod P

Euler’s theorem

Euler theorem is the generalization of Fermatʼs little theorem

For any N, z where gcd(z, N) = 1 then:

z ϕ(N) ≡ 1 mod N

where ϕ(N) is the number of integers between 1 and N which are relatively prime to N , i.e the
size of the set - |x : 1 ≤ x ≤ N, gcd(x, N) = 1|.

• ϕ is also known as Eulerʼs totient function

• when P is prime, then there is P − 1 numbers relatively prime to P . So, ϕ(P ) = P − 1.

So, for primes p, g where N = pq, this implies that ϕ(N) = (p − 1)(q − 1)

• Consider N = pq as 1p, 2p, … , qp so there are q multiples of p.

• Likewise, q, 2q, … , pq there are p multiples of q.
• So, we need to exclude all these numbers!
 • Therefore we get pq − p − q + 1 which equals to (p − 1)(q − 1)

◦ The +1 comes from pq = pq which is a duplicate so we need to add 1 back.

With this, we can re-write Euler theorem as the following:

z (p−1)(q−1) ≡ 1 mod pq

And this is going to allow us to use p − 1, q − 1 to generate a encryption and decryption key.

RSA Idea

Fermatʼs Theorem:

For prime P , take b, c where bc ≡ mod P − 1. This means we can re-write

bc = 1 + k(P − 1) for some integer k. We then take a number Z between 1 and P − 1:

z bc ≡ z 1+K(P −1) mod P


 ≡ z( z (P−1) ) k mod P
1by Fermat's
≡ z mod P

The problem here is I need to tell everyone P , and given b, they are able to figure out c which is
the inverse of b with respect to mod P − 1.

Eulerʼs theorem:

Take d, e where de ≡ 1 mod (p − 1)(q − 1), and N = pq:

z de ≡ z × (z (p−1(q−1))


k
 ) mod N
1
≡ z mod N

Note the terms D and E decryption, encryption. So given a message Z , tell the other party E
and N :

• If the other party wants to send you the message Z

◦ raise it to the power of E and get mod N , i.e z E mod N

 ◦ send it over

• On my end, I compute D, which is the inverse of D = E −1 mod (q − 1)(p − 1) which is

my decryption key

• Take the encrypted message z E mod N , raise to the power D to get z DE mod N which
gives me Z , the original message.

Notice that the other party only knows N , is it possible for the other party to figure out (p − 1)
or (q − 1)?

• Even if you tell the other party pq, the other party is also unable to get (p − 1) or (q − 1)
• But I can compute D since I know p, q and E.

Here is an image to illustrate:

Bob

• Bob picks 2 n-bit random primes p, q

• Bob chooses e relatively prime to (p − 1)(q − 1)

◦ Let N = pq and try e = 3, 5, 7, 11 …

◦ Good to keep encryption key small, easier for someone to encrypt information and send
it to you.
◦ If you are unable to do so, usually you go back to the previous step

• Bob publishes his public key (N, e)

• Bob computes his private key

◦ d ≡ e −1 mod (p − 1)(q − 1)
 ◦ We can do this because of the extended Euclid algorithm.

Alice

• Looks up Bobʼs public key (N, e)

• Computes y ≡ m e mod N

◦ Using the fast mod-exp algorithm

• Sends y to bob

Bob

• Bob receives y
• Decrypts by computing y d mod N = m

◦ This is because y = m ed mod N

◦ m ed = m 1+k(p−1)(q−1) mod N

◦ m 1+k(p−1)(q−1) mod N = m mod N

▪ This is because of euler theorem

◦ This also holds when M, N has a common factor namely P or Q

▪ You can still prove this statement holds with the chinese remainder theorem

Now, the question is, how do we generate this random prime number to start with?

RSA Pitfalls

Attack number one When gcd(m, N) > 1, and gcd(m, N) = p, N = pq

• (m e ) d ≡ mod N by the chinese remainder theorem

• y ≡ m e mod N

• If P divides m, N since gcd(m, N) = p

◦ Then it is also going to divide y

◦ This means that gcd(y, N) = p
 ◦ The attacker can then reverse engineer q

Attack number two when gcd(m, N) > 1 and m not too large, m < N but m < 2 n , N ≥ 2 n

But in this case, we m cannot be too small, for example if e = 3, then m 3 < N , we simply have
y = m 3 since mod N does nothing! To reverse the message we can simply just take the cube
root.

• To avoid this we can choose a random number r, m ⊕ r or m + r, and we can send the
padded message, as well as a second message that is r itself.

◦ As long as r is not too small, you will be fine.

◦ Imagine youʼre the receiving user, you receive m + r and r, you can then reverse
engineer it to get m

Attack number three

Send the same m for e times, then we have (N 1 , 3), (N 2 , 3), (N 3 , 3).

Then we have Y i , ≡ m 3 mod N i and they can figure out m by using the chinese remainder
theorem. (DPV 1.44)

RSA Algorithm

• Choose primes p, g let N = pg

• Find e where gcd(e, (p − 1)(q − 1)) = 1

◦ This means we want e that is relatively prime to (p − 1)(q − 1)

◦ This means e has an inverse by Fermatʼs little theorem.

• Let d ≡ e −1 mod (p − 1)(q − 1)

◦ Use the extended Euclid algorithm

◦ Keep this private key d secret

• Publish public key (N, e)

• Given a message m, Encrypt m by y ≡ m e mod N
 ◦ Send over message y

• Decrypt y by y d mod N = m

Why RSA is hard to break - the whole world knows N = pq but only we know (p − 1)(q − 1),
and therefore only we can compute the inverse of e −1 mod (p − 1)(q − 1)

• A natural question is, can you get (p − 1)(q − 1) from N without knowing p and q
individually?

• The assumption is no, it is not possible to do that. The only way to get p − 1, q − 1 is to
factor N into p and q.

Random primes

let r be a random n-bit number

 Plaintext 
Choose random r
check if r is prime
if yes:
output r
else:
try again

A random number can be chosen by a n-bit strings.

Runtime:

Primes are dense, P r(r is prime) ≈ 1

n , so you can expect to have a random prime number
a�er n tries, so, complexity here is O(n).

Primality: Fermat’s test

Recall that if r is prime then for all z ∈ 1, . . . , r − 1, z r−1 ≡ 1 mod r.

So, we need to find z where z r−1 ≡ 1 mod r ⟹ r is composite. We call this z a Fermat
witness with respect to Fermatʼs little theorem.

• Does every composite r have a Fermat witness?

◦ Surprisingly, YES!

• How do we find one?

◦ In fact every composite number has multiple Fermat witness

◦ Some exceptions such as Pseudo Primes

Fermat Witnesses

Fermat witness for r : z if 1 ≤ z ≤ r − 1 & z r−1 ≡ 1 mod r, then the number r is

composite.

First proof that every composite r has ≥ 1 Fermat witness. Since r is composite, there is at least
two divisors.

Take z where gcd(r, z) = z since z ≤ r − 1, and since r is composite, we know this divisor is
greater than one so z > 1. So any z which is not relatively prime to r and r is composite will
work.

This implies that z −1 mod r does not exists because it only exists if and only if the
gcd(r, z) = 1 and this is also from the inverse existence.

Suppose z r−1 ≡ 1 mod r, then we have z r−2 × z ≡ 1 mod r, so z −1 ≡ z r−2 mod r which is
a contradiction.

Feel free to see Dpv 1.3 for more information.

• Trivial Fermat witness : z where gcd(z, r) > 1

• Non-trivial Fermat witness is where gcd(z, r) = 1

◦ Some composite numbers have no non-trivial fermat witnesses, these are called pseudo
primes, but those are relatively rare.
◦ For all other composite numbers, they have at least one non-trivial Fermat witness, and
 if they have at least one, they in fact have many Fermat witnesses.
◦ Therefore, it will be easy to find a Fermat witness

• Trivial Fermat witnesses always exists!

◦ Every composite number has at least two trivial Fermat witnesses!

◦ They are dense and therefore easy to find

Non-Trivial Witnesses

z is a nontrivial Fermat witness for f if z r−1 ≡ 1 mod r and gcd(z, r) = 1.

• Carmichael numbers - sort of pseudoprime numbers

◦ They behave like primes with respect to Fermatʼs little theorem

• A Carmichael number is a composite number r with NO nontrivial Fermat witnesses

• Such a number is going to be ine�icient to use Fermatʼs test to prove that r is a composite
number

◦ Find a di�erent way to deal with them

• These Carmichael numbers are rare

◦ smallest one are 561 and 1105, 1729 and so on

◦ Ignore them for now

Lemma: if r has ≥ 1 non trivial Fermat witness, then ≥ 1

2 that z ∈ 1, 2, . . , r − 1 are Fermat
witness.

• Proof is in the book, enjoy yourself as usual!

• Question still remains, how to check a number is prime?

◦ Take z from the set 1, 2, . . , r − 1 and raise it to the power r − 1 and look at mod r
and see whether it is one or not.

Simple Primality tests

  Plaintext 
For n-bit r

choose z randomly from {1,2,...,r-1}

Compute pow(z, r-1) === 1 mod r
if pow(z, r-1) === 1 mod r:
then output r is prime
else
output r is composite (z is a witness to the fact that r is composite)

For prime r, z r−1 ≡ 1 mod r is true because of Fermatʼs little theorem.

• So Pr(algorithm outputs r is prime) = 1

For composite r and assume that it is not a carmichael number. Sometimes the algorithm is
going to be correct, it is going to output that r is composite. This happens when it finds a z
which is a Fermat witness. z r−1 ≡ 1 mod r

• sometimes it is going to get confused, it is going to make a mistake, and it is going to find a
z which z r−1 ≡ 1 mod r, so it is going to think that r is prime.
• Recall that at most half of them are not witnesses
• The Pr(algorithm outputs r is prime) ≤ 1
2

The question now is, can we improve this error probability of a false positive of 1
2

Better primality test

Instead of choosing a particular z, we choose k − z and run the algorithm k times.

Then Pr(algorithm outputs r is prime) ≤ ( 12 ) k . You can think of it as a coin toss each with
probability 1
2 . So the probability that the coin toss is all tails with k flips is ( 12 ) k .

So you can take k = 100, so ( 12 ) 100 is a very small number and you will be willing to take the
risk on that.

• Again we assume that the numbers are not Carmichael

 • to deal with these Carmichael, it is not that much more complicated of an algorithm

Dealing with Carmichael

So we know it is composite if there is a non trivial square root of 1 mod x. Trivial square root of
1 means 1 or -1 since 1 2 , −1 2 = 1.

For example, x = 1729 and choose z = 5, and note that x − 1 = 1728 = 2 6 × 27

5 27 ≡ 1217 mod 1729

5 2×27 ≡ 1217 ≡ 1065 mod 1729
2
52 ×27
≡ 1065 2 ≡ 1 mod 1729
2
52 ×27
≡ 1 2 ≡ 1 mod 1729
⋮
5 1728 ≡ 1 mod 1729

So, when Fermat tests fail, we see if there is a non trivial square root of 1 exists.

It turns out that for a composite number X, even if its Carmichael, for at least three quarters of
the choices of Z , this algorithm works.