### Number Theory, RSA

```Addition
How fast can you add A+B
How fast can you add A+B
1010111001
100100111
How fast can you add A+B
1010111001
100100111
0
How fast can you add A+B
1010111001
100100111
00
How fast can you add A+B
1010111001
100100111
100
How fast can you add A+B
1010111001
100100111
1111011100
n-bit numbers  time = O(n)
Multiplication
How fast can you
multiply A*B
1010111001
*1 0 1 1
Multiplication
How fast can you
multiply A*B
1010111001
*1 0 1 1
1010111001
1010111001
1010111001
Multiplication
How fast can you
multiply A*B
1010111001
*1 0 1 1
1010111001
1010111001
1010111001
n-bit numbers  time = O(n2)
Karatsuba-Offman
a=2n/2 a1 + a0
b=2n/2 b1 + b0
ab=(2n/2a1+a0)(2n/2b1+b0) =
2n a1 b1 +
2n/2 (a1 b0 + a0 b1) +
a0 b0
Karatsuba-Offman
a=2n/2 a1 + a0
b=2n/2 b1 + b0
Multiply(a,b,n)
if n=1 return a*b
else
R1  Multiply(a1,b1,n/2)
R2  Multiply(a0,b1,n/2)
R3  Multiply(a1,b0,n/2)
R4  Multiply(a0,b0,n/2)
return 2n R1+ 2n/2 (R2+R3) + R4
Karatsuba-Offman
Multiply(a,b,n)
if n=1 return a*b
else
R1  Multiply(a1,b1,n/2)
R2  Multiply(a0,b1,n/2)
R3  Multiply(a1,b0,n/2)
R4  Multiply(a0,b0,n/2)
return 2n R1+ 2n/2 (R2+R3) + R4
Recurrence?
Karatsuba-Offman
Multiply(a,b,n)
if n=1 return a*b
else
R1  Multiply(a1,b1,n/2)
R2  Multiply(a0,b1,n/2)
R3  Multiply(a1,b0,n/2)
R4  Multiply(a0,b0,n/2)
return 2n R1+ 2n/2 (R2+R3) + R4
Recurrence?
T(n) = 4T(n/2) + O(n)
Karatsuba-Offman
T(n) = 4T(n/2) + O(n)
T(n)=O(n2)
Karatsuba-Offman
ab=(2n/2a1+a0)(2n/2b1+b0) =
2n a1 b1 +
n/2
2 (a1 b0 + a0 b1) +
a0 b0
Can compute in less than 4
multiplications?
Karatsuba-Offman
ab=(2n/2a1+a0)(2n/2b1+b0) =
2n a1 b1 +
n/2
2 (a1 b0 + a0 b1) +
a0 b0
Can compute using 3
multiplications:
(a0+a1)(b0+b1) =
a0b0 + (a1 b0 + a0 b1) + a1 b1
Karatsuba-Offman
Multiply(a,b,n)
if n=1 return a*b
else
R1  Multiply(a1,b1,n/2)
R2  Multiply(a0,b0,n/2)
R3  Multiply(a1+a0,b1+b0,n/2+1)
R 4  R3 – R 2 – R1
return 2n R1+ 2n/2 R3 + R2
Recurrence?
Karatsuba-Offman
Multiply(a,b,n)
if n=1 return a*b
else
R1  Multiply(a1,b1,n/2)
R2  Multiply(a0,b0,n/2)
R3  Multiply(a1+a0,b1+b0,n/2+1)
R 4  R3 – R 2 – R1
return 2n R1+ 2n/2 R3 + R2
Recurrence?
T(n) = 3T(n/2) + O(n)
Karatsuba-Offman
T(n) = 3T(n/2) + O(n)
T(n)=O(nC)
C=log2 3  1.58
Integer Division
r=a mod b
a,b  q,r
a = q*b + r
0r<b
Can be done in
2
O(n )
time.
d divides a
DEFINITION:
d divides a (denoted d | a)
if there exists b such that
b*d = a
3|6
3|0
0|3
0|0
d divides a
DEFINITION:
d divides a (denoted d | a)
if there exists b such that
b*d = a
3|6
3|0
0|3
0|0
yes, b=2
yes, b=0
no
yes, b=?
d divides a
3|6 yes, b=2
3|0 yes, b=0
0|3 no
0|0 yes, b=?
d|a a|c d|c
Proof:
a = b*d, c=b’*a  c=(b*b’)*d
Divisibility poset
0
8
4
6
10
9
2 3
5
1
7
GCD
GCD (a,b)
“largest” d such that d|a, d|b
GCD
GCD (a,b)
“largest” d such that d|a, d|b
d|a, d|b
(c; c|a,c|b) : c|d
GCD(3,6)
GCD(0,8)
GCD(0,0)
GCD
GCD (a,b)
“largest” d such that d|a, d|b
d|a, d|b
(c; c|a,c|b) : c|d
GCD(3,6) = 3
GCD(0,8) = 8
GCD(0,0) = 0
GCD
How quickly can we compute
GCD (a,b) ?
GCD
How quickly can we compute
GCD (a,b) ?
Euclid
GCD(a,b) = GCD(b,a mod b)
GCD
wlog a>b
GCD(a,b)
if b=0 then return a
else
return GCD(b,a mod b)
Running time?
GCD
wlog a>b
GCD(a,b)
if b=0 then return a
else
return GCD(b,a mod b)
Running time?
(a,b)(b,a mod b)(a mod b, ?)
(a mod b) < a/2
GCD
(a,b)(b,a mod b)(a mod b, ?)
(a mod b) < a/2
2(log2 a)=O(n)
iterations
each mod O(n2) time
 O(n3) time total
Modular exponentiation
(a,b,m)  ab mod m
Modular exponentiation
(a,b,m)  ab mod m
a mod m
a2 mod m
4
a mod m
a8 mod m
a16 mod m
...
b = 10101
ab mod m
Modular exponentiation
(a,b,m)  ab mod m
mod-ex(a,b,m)
if b=0 then RETURN 1
else
if b mod 2 = 0 then
RETURN mod-ex(a,b/2,m)2 mod m
else
RETURN
a*mod-ex(a,(b-1)/2,m)2 mod m
Algorithms so far
a,b,m
n-bit integers
O(n) time
multiplication a*b O(n1.58) time
division a/b,a mod b O(n2) time
gcd(a,b)
O(n3) time
b
3
a mod m
O(n ) time
GROUP
(G,) is a group if
 : GG  G
(ab)c = a(bc)
exists  G
(aG) a = a
-1
aa
aa-1=
Modular arithmetic
G = {0,...,m-1} = Zm
modulo m
ab = a+b mod m
(G,) is a group if
 : GG  G
(ab)c = a(bc)
exists  G
(aG) a = a
a  a-1
aa-1=
Modular arithmetic
G = {0,...,m-1} = Zm
modulo m
ab = a+b mod m
(G,) is a group if
IS A GROUP
 : GG  G
(ab)c = a(bc)
exists  G
(aG) a = a
a  a-1
aa-1=
Modular arithmetic
G = {0,...,m-1} = Zm
modulo m
ab = a*b mod m
(G,) is a group if
 : GG  G
(ab)c = a(bc)
exists  G
(aG) a = a
a  a-1
aa-1=
Modular arithmetic
G = {0,...,m-1} = Zm
modulo m
ab = a*b mod m
(G,) is a group if
 b; ab=1 [mod m]

GCD(a,m)=1
 : GG  G
(ab)c = a(bc)
exists  G
(aG) a = a
a  a-1
aa-1=
Modular arithmetic
modulo m
*
G = Z m ={a | GCD(a,m)=1 }
ab = a*b mod m
(G,) is a group if
IS A GROUP
 : GG  G
(ab)c = a(bc)
exists  G
(aG) a = a
a  a-1
aa-1=
Fermat’s little Theorem
p a prime
p-1
a = 1 [mod p]
{ak | k Z} is a subgroup of Z*p
Fermat’s little Theorem
(m)
a =1
[mod m]
(m) = | Z*m |
m=p1a1 p2a2 ... pkak
(m) = (1-1/p1) ... (1-1/pk) m
Fermat’s little Theorem
m=p1a1 p2a2 ... pkak
(m) = (1-1/p1) ... (1-1/pk) m
E.g. if m=pq
(m)=
p,q primes
Fermat’s little Theorem
m=p1a1 p2a2 ... pkak
(m) = (1-1/p1) ... (1-1/pk) m
E.g. if m=pq
p,q primes
(m)=(p-1)(q-1)
Fermat’s little Theorem
a(p-1)(q-1) =1 [mod pq]
E.g. if m=pq
p,q primes
(m)=(p-1)(q-1)
RSA
1) choose primes p,q
2) let n  pq
3) choose e
4) compute
d=e-1 [mod (p-1)(q-1)]
5) announce n,e
RSA
1) choose primes p=13,q=17
2) let n  pq
3) choose e
4) compute
d=e-1 [mod (p-1)(q-1)]
5) announce n,e
RSA
1) choose primes p=13,q=17
2) let n  pq=221
3) choose e
4) compute
d=e-1 [mod (p-1)(q-1)]
5) announce n,e
RSA
1) choose primes p=13,q=17
2) let n  pq=221
3) choose e=5
4) compute
d=e-1 [mod (p-1)(q-1)]
5) announce n,e
RSA
1) choose primes p=13,q=17
2) let n  pq=221
3) choose e=5
4) compute
77=d=e-1 [mod (p-1)(q-1)]
5) announce n,e
RSA
1) choose primes p=13,q=17 d
2) let n  pq=221
3) choose e=5
4) compute
77=d=e-1 [mod (p-1)(q-1)]
5) announce n,e
n=221
e=5
= 77
RSA
d = 77
n=221
e=5
e
x
ENCODE: x mod n
DECODE: x xd mod n
RSA
m=42
d = 77
n=221
e=5
e
x
ENCODE: x mod n
DECODE: x xd mod n
RSA
m=42
425 (mod 221) = 9
d = 77
9
n=221
e=5
e
x
ENCODE: x mod n
DECODE: x xd mod n
RSA
m=42
425 (mod 221) = 9
d = 77
9
977 (mod 221) = 42
m=42
n=221
e=5
e
x
ENCODE: x mod n
DECODE: x xd mod n
Primality testing
```