Transcript On Number theory algorithms from Srividya and George

Number Theory
Presented by
Shrividya Shivkumar and George Frederick
Contents












Division Theorem
Modular Exponential
Prime Numbers
Fermat’s Little Theorem
Miller-Rabin
Primes Is In P
Relatively Prime numbers
Euclid’s algorithm
Extended Euclid algorithm
Chinese Remainder Theorem
RSA
Pollard’s Rho
Division theorem

•
For any integer a and a positive integer n
there are unique integers q and r such that 0 ≤ r <
n and
a = qn + r
or
a = a/n  n + ( a mod n)
If (a mod n) = (b mod n) then
a is equivalent to b
a
b (mod n)
Ex : 61
6 (mod 11)
Properties of modular addition and multiplication:
Let a
b
a+b
ab
a’ (mod n)
b’ (mod n) then
( a’ + b’)( mod n)
(a’b’) (mod n)
Properties of common divisors:
 If d | a and d | b
d | (a + b)
 If d | a and d | b
d | ( a – b)
 If d | a and d | b
d | (ax + by)
Modular Exponential

Gives an efficient way to calculate
b
a mod n
Modular Exponential
What are prime numbers?

An integer having only trivial divisors
( 1 and itself)
Ex : 2 , 3 , 5 , 7 , 11 ….
What are relative Prime Numbers ?
Numbers whose only common factor is 1 or the gcd(a,b) = 1.
Ex: 6 and 35 are relatively prime (gcd = 1)
Ways to Check If a number is prime :
1.Trial division
2.Fermat’s Little theorem
3.Miller Rabin primality test
Finding Prime numbers
Trial division – testing for divisibility of
each integer starting from 2 … sqrt(n)
 Even integers greater than 2 can be
skipped.
 Worst case complexity : O (sqrt(n))

Fermat’s Little Theorem
Fermat’s Little Theorem

Disadvantages:
Does not work with Carmichael numbers.
Carmichael numbers - a Carmichael
number is a composite positive integer n
which satisfies the congruence bn1  1(mod n)
for all integers b which are relatively
prime to n .
Ex : 561 = 11 * 3 * 17
How to check if a number is prime?
Use the Miller-Rabin test
 Uses several randomly chosen base values

Miller-Rabin Test contd…

1.
2.
3.
Witness(a,n)
b(k),b(k-1)….b(0) .. Binary representation of n-1
D1
For I  k to 0
Do x  d
D  (d.d)mod(n)
if d = 1 and (x not equal 1) and (x not equal n-1)
return true
if b(i) = 1
d  (d.a)mod n
If ( d not equal 1)
return TRUE
Return FALSE
PRIMES is in P
Authored by Manindra Agrawal, Neeraj
Kayal, and Nitin Saxena
 Won the 2006 Gödel Prize
 Produced an unconditional deterministic
polynomial-time algorithm that
determines whether an input number is
prime or composite
 Previous efforts were all conditional,
randomized, or had exponential running
times

PRIMES is in P
As with most primality tests, is based on
Fermat’s Little Theorem (actually a
generalization of)
 Fermat’s Little Theorem: For any integer a:

a  a(mod p)
p

Generalization:
Let a  Z , n  N , n  2, and (a, n)  1. Then
n
n
n is prime iff ( X  a)  X  a(mod n)
What is a greatest common divisor?
The largest common divisor of a and b
1 < = gcd( a,b) <= min ( |a| , | b|)
Euler’s Phi Function

The number of positive integers less than
equal to n that are relatively prime to n
where,
P  Number of primes dividing n.
Ex: if n = 45
phi(45) = 45 ( 1-(1/3))(1-(1/5))
= 24
Euler’s Phi Function
When p is prime, then
Ø(p) = {1 , 2 , 3 , …., p-1} = p-1
When n is composite
Ø(n) < (n-1)
Euclid’s Algorithm for calculating gcd
What is Multiplicative inverse?

Multiplicative inverse is nothing but the
reciprocal of the number.
How to calculate Multiplicative inverse?
Using Extended Euclid’s algorithm
Extended Euclid’s algorithm

d = gcd ( a,b) = ax + by
i/p : random pair of integer a,b
o/p : triplet (d,x,y) which satisfies the above eqn.
Extended Euclid’s algorithm
Multiplicative inverse using
extended Euclid’s algorithm
Multiplicative inverse is nothing but the
reciprocal of the number.
If 2 numbers a,n are relatively prime then
gcd ( a,n) = 1
 ax + ny = 1
 ax = 1(mod n)
 x = inv(a) mod n
Where,
a and n are the inputs and x, y, and gcd(a,n) are
the outputs for Extended Euclid’s algorithm

Chinese Remainder Theorem
Original form created by Chinese
mathematician Sun Tzu
 Relates to finding solutions to
simultaneous congruences
i.e. x  y (mod m)

x  y (mod s)
x  y (mod ms)
(m and s are relatively prime)
Chinese Remainder Theorem
Let n  n1n2  nk where each ni is
pairwise relatively coprime
 Let Z denote the set of all integers,

[a]n  {a  kn : k  Z }, a [b]n  a  b(mod n) ,
ex. [3]7  {..., 11,4,3,10,17...} ,
Z n  {[ a]n : 0  a  n  1}
 Consider the correspondence
a  (a1 , a2 ,, ak ) , where a  Z n , ai  Z n ,
and ai  a mod ni for i  1,2, , k
i
Chinese Remainder Theorem

Then, mapping a  (a1 , a2 ,, ak ) is a
one-to-one correspondence (bijection)
between Z n and the Cartesian product
Z n 1  Z n 2  Z n k

If a  (a1 , a2 ,, ak ) and b  (b1 , b2 ,, bk )
then
(a  b) mod n  (( a1  b1 ) mod n1 ,, (ak  bk mod nk ),
(a  b) mod n  (( a1  b1 ) mod n1 ,, (ak  bk mod nk ),
(ab) mod n  (( a1b1 ) mod n1 ,, (ak bk mod nk )
CRT Example
k
n   ni
i 1
x  a1 (mod n1 )
mi  n / ni
x  a2 (mod n2 )
ci  mi (mi mod ni )
 x  a(mod n1n2 )
1
a  (a1c1  a2c2    ak ck )(mod n)
x  2(mod 5)
x  3(mod 13)
x  2  26  3  40(mod 65)
x  52  120(mod 65)
x  172(mod 65)
x  42(mod 65)
n  n1n2  5 13  65
a1  2, n1  m2  5
a2  3, n2  m1  13
c1  13(2 mod 5)  26
c2  5(8 mod 13)  40
CRT Proof
Transforming between the two
representations is fairly straightforward
 Going from a  (a1 , a2 , , ak ) requires
only k divisions i.e. performing
ai  a mod ni for each ni

CRT Proof
Going from (a1 , a2 ,, ak )  a is
somewhat more complicated
 Begin by defining mi  n / ni for i  1,2, , k
and thus mi is the product of all n j ' s
other than ni : mi  n1n2 ni 1ni 1 nk
1
 Next define ci  mi (mi mod ni ) for
i  1,2, , k

CRT Proof

1
ci  mi (mi mod ni ) is always well defined
◦ Since mi and ni are relatively prime,
(ab) mod n  ((a1b1 ) mod n1 ,, (ak bk mod nk )
1
(
m
guarantees that i mod ni ) exists

Finally, a can be computed as a function of
a1 , a2 ,, ak as such:
a  (a1c1  a2c2    ak ck )(mod n)

This ensures that a  ai (mod ni ) for
i  1,2, , k
CRT Proof

If j  i then m j  0(mod ni ) , implying that
c j  m j  0(mod ni )
1
Also ci  1(mod ni ) from ci  mi (mi mod ni )
 Thus we have the correspondence
c  (0,0,,0,1,0,,0) , a vector with all
0’s except for in the i' th coordinate,
which has a 1
 Thus the ci form a sort of basis for the
representation

CRT Proof

Therefore, for each i we have
a  ai ci (mod ni )
1
a  ai mi (mi mod ni )(mod ni )
a  ai (mod ni )
This produces a result a that satisfies the
constraints a  ai (mod ni ) for i  1,2,, k
 The correspondence is one-to-one, since
we can transform in both directions

CRT Corollary 1

If n1 , n2 ,, nk are pairwise relatively
prime and n  n1n2  nk , then for any
integers a1 , a2 ,, ak, the set of
simultaneous equations x  ai (mod ni ) for
i  1,2, , k has a unique solution
modulo n for some unknown x
CRT Corollary 2
If n1 , n2 ,, nk are pairwise relatively
prime and n  n1n2  nk, then for all
integers x and a ,
x  a(mod ni )
for i  1,2,, k if and only if
x  a (mod n)
 Therefore we can work modulo n by
working modulo n directly or by using
separate modulo ni computations

CRT Corollary 2 Proof

Theorem
x  y (mod p )
x  y (mod q ), gcd( p, q)  1
 x  y (mod pq)

Proof
x  y (mod p )
x  y  kp
x  y  kp
p | ( x  y)
q | ( x  y)
pq | ( x  y )
x  y  1( pq )
x  y (mod pq )
RSA - Introduction
Named after its creators Ron Rivest, Adi
Shamir, and Leonard Adleman from MIT
 Public-key cryptosystem
 Relies on dramatic difference between
ease of finding large prime numbers and
difficulty of factoring the products of large
primes

RSA – Public-Key Cryptosystems
Each participant has a public and a secret
key
 In RSA, each key is a pair of integers
 For example, Alice’s and Bob’s keys can be
denoted PA , S A and PB , S B respectively
 Participants create their own keys,
keeping the secret key secret while the
public key can be published

RSA – Public-Key Cryptosystems
Encrypting a message with the recipient’s
public key will ensure that only the
recipient will be able to decode it, using
his/her secret key
 Additionally, a public-key cryptosystem
allows for the use of unforgeable digital
signatures, ensuring the integrity of the
message as well as the identity of the
sender

RSA – Public-Key Cryptosystems
The public and secret keys are used as
functions that can be applied to messages
 Let D denote the set of allowable
messages, e.g. the set of finite-length bit
sequences
 We require that the public and secret
keys specify one-to-one functions from D
to itself.

RSA – Public-Key Cryptosystems
Alice’s public key function is denoted PA ()
and her private key as S A ()
 We assume that PA () and S A () are
efficiently computable given their
corresponding keys PA or S A
 A participant’s public and secret key
functions work as inverses of each other:

M  S A ( PA ( M ))
M  PA ( S A ( M ))
for any message M  D
RSA – Public-Key Cryptosystems
It is imperative that only Alice be able to
efficiently compute S A () in a practical
amount of time, as it ensures Alice’s
uniqueness and identity
 The difficulty is that PA () is the public
inverse to S A () , but the means to
compute S A () from PA () should be
impractical to determine

Non-Public-Key Cryptosystems
Public-Key Cryptosystems
RSA – Scenario 1
1.
2.
3.
4.
Bob wants to send a secret message M
to Alice
Bob obtains Alice’s public key PA either
directly from Alice or from a public
source
Bob computes the cyphertext C  PA (M )
and then sends C to Alice
Alice receives C and decrypts it with S A
to get the original message: M  S A (C)
RSA – Scenario 2
1.
2.
3.
4.
Alice wants to send a public digitally
signed message M ' to Bob
Alice computes her digital signature
for M ' using S A :   S A (M ' )
Alice sends the message/signature pair
( M ' ,  ) to Bob
Bob receives ( M ' ,  ) and uses the
equation M '  PA ( ) to verify that the
message and signature are from Alice
and have not been corrupted or forged
RSA – Scenario 3
1.
2.
3.
4.
5.
Alice wants to send a secret digitally
signed message M ' ' to Bob
Alice computes her digital signature as
in Scenario 2 and appends it to M ' '
Alice then encrypts ( M ' ' ,  ) with PB :
C'  PB (M ' ' , ) and sends C ' to Bob
Bob receivesC ' and decrypts it: M ' '  S B (C' )
Bob then uses the equation M ' '  PA ( )
to perform the same verification as in
Scenario 2
RSA - Algorithm
Participants create their own public and
secret keys as follows
1. Randomly selects two large primes p
and q such that p  q
2. Compute n  pq
3. Select a small odd integer e relatively
prime to  (n) , which by
 (n)  n (1  1 / p) , equals ( p  1)( q  1)
p|n
4. Compute d as the multiplicative inverse
of e , modulo  (n)

RSA - Algorithm
5.
6.
Publish the pair P  (e, n) as the
participant’s public key
Keep the pair S  (d , n) private as the
participant’s secret key
RSA - Algorithm
For this scheme, the domain D is the set Z n
 Encrypting a message is performed as
with the equation P(M )  M e (mod n)
 Decrypting a message is performed using
the equation S (C )  C d (mod n)
 Signing a message is done by using the
equation S (M )  M d (mod n)
 Verifying a signature is done by using the
e
equation P( )   (mod n)

RSA Example
q  61, p  53
n  pq  61 53  3233
 (n)   (3233)  (61  1)(53  1)  3120
e  1, gcd( e, n)  1
e  17, gcd(17,3120)  1
de  1(mod  (n))
17d  1(mod 3120)
d  2753
Pk (n, e)  (3233,17), S k (n, d )  (3233,2753)
m  123
c  m e mod n  12317 mod 3233  855
d  m d mod n  8552753 mod 3233  123
RSA – Correctness Theorem

Theorem (Correctness of RSA):
e
d
and
P(M )  M (mod n)
S (C )  C (mod n)
define inverse transformations of Z n
satisfying equations M  S A (PA (M )) and
M  PA (S A (M ))
RSA - Proof
e
P
(
M
)

M
(mod n) and
 From
S (C )  C d (mod n) , we have that for any
M  Z n , P(S (M ))  S ( P(M ))  M ed (mod n)
 Since e and d are multiplicative inverses
modulo  (n)  ( p  1)( q  1) ,
ed  1  k ( p  1)( q  1) for some integer k
 Then if M ! 0(mod p) , we have
M ed  M ( M p 1 ) k ( q 1) (mod p )
M ed  M (1) k ( q 1) (mod p )
M ed  M (mod p )
RSA - Proof
ed
M
 M (mod p) if M  0(mod p)
 Also,
Therefore, M ed  M (mod p) for all M and
similarly M ed  M (mod q) for all M
ed
 Thus according to CRT M  M (mod n)
for all M

RSA - Decryption
Relies mainly upon the difficulty of
factoring large integers
 If an interceptor can factor the modulus n
in a public key, he can derive the secret
key using knowledge of p and q in the
same way as the keys’ creator used them
 The statement that if factoring large
integers is hard then breaking RSA is hard
is unproven, but 20 years of research has
found no easier method

Pollard’s Rho
Factoring large integers is currently
computationally infeasible
 Pollard’s rho is a useful tool for factoring
large integers however
 Pollard’s rho is a heuristic, not an
algorithm, meaning its running time and
success are not guaranteed
 Very effective in practice though

Pollard’s Rho
Pollard-Rho(n)
1.
i= 1
2.
x1= random(0,n-1)
3.
y= x1
4.
k= 2
5.
while TRUE
6.
do i= i+1
7.
xi= (xi-12-1)mod n
8.
d= gcd(y-xi,n)
9.
if d!=1 and d!= n
10.
then print d
11.
if I == k
12.
then y= xi
13.
k=2k
Pollard’s Rho
Pollard-Rho never prints an
incorrect answer
 Any number printed is a nontrivial
divisor of n
 However Pollard-Rho may not print
anything at all
 There is no guarantee that it will produce
a result

Pollard’s Rho
There is good reason to believe that it
will print a factor p of n after ( p )
iterations of the while loop
 If n is composite, we can expect PollardRho to factor n completely after about
n1/4 updates since every prime factor p of
n except perhaps the largest is less than n

Pollard’s Rho Example
n=8051
x=x2+1 mod 8051
y=f(f(x))
i
xi
yi
gcd(|xi-yi|,8051)
1
5
26
1
2
26
7474
1
3
677
871
97
Questions?
References
Cormen, Thomas H., et al. Introduction to
Algorithms. 2nd ed. Cambridge, MA: MIT,
2001.
 Agrawal, Manindra, Neeraj Kayal, Nitin
Saxena. “PRIMES is in P.”Annals of
Mathematics 160 (2004):781-793.
