EULER AND FERMAT THEOREM

EULER THEOREM AND FERMAT THEOREM WITH RSA EXAMPLE

1. Fermat and Euler’s Fermat and Euler’s
TheoremsTheorems
Presented By :Presented By :
Ankita PandeyAnkita Pandey
ME ECE- 112604ME ECE- 112604

2. CONTENTSCONTENTS
PRIME NUMBERSPRIME NUMBERS
 PRIME FACTORIZATIONPRIME FACTORIZATION
RELATIVELY PRIME NUMBERSRELATIVELY PRIME NUMBERS
GREATEST COMMON DIVISORGREATEST COMMON DIVISOR
FERMAT’S THEOREMFERMAT’S THEOREM
FERMAT THEOREM PROOFFERMAT THEOREM PROOF
EULER TOTIENT FUNCTIONEULER TOTIENT FUNCTION
EULER’S THEOREMEULER’S THEOREM
APPLICATIONSAPPLICATIONS
SUMMARYSUMMARY
REFERENCESREFERENCES

3. PRIME NUMBERS :PRIME NUMBERS :

4. PRIME FACTORIZATION :PRIME FACTORIZATION :

5. RELATIVELY PRIME NUMBERS :RELATIVELY PRIME NUMBERS :

6. GREATEST COMMON DIVISOR (GCD)GREATEST COMMON DIVISOR (GCD)

7. FERMAT’S THEOREMFERMAT’S THEOREM
º
º

8. FERMAT’S THEOREM PROOF :FERMAT’S THEOREM PROOF :
 Consider a set of positive integers less than ‘p’ : Consider a set of positive integers less than ‘p’ :
{1,2,3,…..,(p-1)} and multiply each element by ‘a’ and {1,2,3,…..,(p-1)} and multiply each element by ‘a’ and
‘modulo p’ , to get the set ‘modulo p’ , to get the set
X = {a mod p, 2a mod p,…, (p-1)a mod p}X = {a mod p, 2a mod p,…, (p-1)a mod p}
 No elements of X is zero and equal, since p doesn’t No elements of X is zero and equal, since p doesn’t
divide a.divide a.
 Multiplying the numbers in both sets (p and X) and Multiplying the numbers in both sets (p and X) and
taking the result mod p yieldstaking the result mod p yields

9. FERMAT’S THEOREM PROOF :FERMAT’S THEOREM PROOF :
a * 2a *…* (p-1)a [1 * 2 * 3 *…* (p-1)] (mod p)a * 2a *…* (p-1)a [1 * 2 * 3 *…* (p-1)] (mod p)
Thus on equating (p-1)! term from both the sides, Thus on equating (p-1)! term from both the sides,
since it is relatively prime to p, result becomes,since it is relatively prime to p, result becomes,
An alternative form of Fermat’s Theorem is given asAn alternative form of Fermat’s Theorem is given as
º
)(mod)!1()!1(
1
pppa
p
-º-
-
)(mod1
1
pa
p
º
-
)(modpaa
p
º

10. EULER TOTIENT FUNCTION : EULER TOTIENT FUNCTION : φφ ( (nn))
¨ ((nn) : How many numbers there are between ) : How many numbers there are between
1 and 1 and nn-1 that are relatively prime to -1 that are relatively prime to nn..
¨ (4) = 2 (1, 3 are relatively prime to 4).(4) = 2 (1, 3 are relatively prime to 4).
¨ (5) = 4 (1, 2, 3, 4 are relatively prime to 5).(5) = 4 (1, 2, 3, 4 are relatively prime to 5).
¨ (6) = 2 (1, 5 are relatively prime to 6).(6) = 2 (1, 5 are relatively prime to 6).
¨ (7) = 6 (1, 2, 3, 4, 5, 6 are relatively prime (7) = 6 (1, 2, 3, 4, 5, 6 are relatively prime
to 7).to 7).
f
f
f
f
f

11. ¨From (5) and (7), (n) will be n-1
whenever n is a prime number.
¨This implies that (n) will be easy to
calculate when n has exactly two different
prime factors:
(P * Q) = (P-1)*(Q-1)
if P and Q are prime.
f ff
f
f
EULER TOTIENT FUNCTION : EULER TOTIENT FUNCTION : φφ ( (nn))

12. ¨If GCD(a, p) = 1, and a < p, then
a
(p)
1(mod p).
¨In other words, If a and p are relatively
prime, with a being the smaller integer, then
when we multiply a with itself (p) times and
divide the result by p, the remainder will be 1.
º
f
f
EULER TOTIENT FUNCTION : EULER TOTIENT FUNCTION : φφ ( (nn))

13. EULER’S THEOREM :EULER’S THEOREM :
()
( )na
n
mod1º
F

14. EULER’S THEOREM :EULER’S THEOREM :
¨ Above equation is true if n is prime because Above equation is true if n is prime because
then,then,
and Fermat’s theorem holds.and Fermat’s theorem holds.
¨Consider the set of such integers, labeled as,Consider the set of such integers, labeled as,
Here each element of R is unique positive Here each element of R is unique positive
integer less than n with GCD( ,n ) = 1.integer less than n with GCD( ,n ) = 1.
() )1(-=F nn
(){ }
n
xxxR
F
= ,...,,
21
i
x
i
x

15. EULER’S THEOREM :EULER’S THEOREM :
¨Multiply each element by a, modulo n :Multiply each element by a, modulo n :

The set S is permutation of R :The set S is permutation of R :
Because a and is relatively prime to n, Because a and is relatively prime to n,
so a must also be relatively prime to n. so a must also be relatively prime to n.
Thus the elements of S are integers that Thus the elements of S are integers that
are less than n and that are relatively are less than n and that are relatively
prime to n.prime to n.
There are no duplicates in S. There are no duplicates in S.

( )( )
()( ){ }naxnaxnaxS
n
mod,....,mod,mod
21 F
=
i
x
i
x

16. EULER’S THEOREM :EULER’S THEOREM :
¨If then If then naxnax
ji modmod=
ji
xx=
( )
()()
ÕÕ
F
=
F
=
=
n
i
n
i
ii
xnax
1 1
mod
()
( )na
n
mod1º
F
()()
( )nxax
n
i
n
i
ii
mod
1 1
ÕÕ
F
=
F
=
=
()
() ()
( )nxxa
n
i
i
n
i
i
n
mod
11
ÕÕ
F
=
F
=
F
º
ú
û
ù
ê
ë
é
´

17. APPLICATIONS:APPLICATIONS:

18. EXAMPLE :EXAMPLE :
1.Choose two large prime numbers P and Q.
2.Calculate N = P * Q.
3. Select the public key (i.e. the encryption key) E such
that it is not a factor of (P-1)*(Q-1).
Let P = 7 , Q = 17Let P = 7 , Q = 17
Thus , N = 7 x 17 = 119Thus , N = 7 x 17 = 119
• Now (7-1) x (17-1) = 6 x 16 = 96.Now (7-1) x (17-1) = 6 x 16 = 96.
• Factors of 96 are 2 and 3 (2 x 2 x 2 x 2 x 2 x 3).Factors of 96 are 2 and 3 (2 x 2 x 2 x 2 x 2 x 3).
• E has to be prime to 96, let E = 5.E has to be prime to 96, let E = 5.

19. EXAMPLE :EXAMPLE :
4.Select the private key (i.e. the decryption key) D such
that the following equation is true :
(D x E) mod (P-1) x (Q-1) = 1
5. For encryption, calculate the Cipher Text CT from the
Plain Text PT as follows :
CT = PT mod N.
ᴱ
• Substitute the values of E, P and Q in the equationSubstitute the values of E, P and Q in the equation
• Let choose D = 77 sinceLet choose D = 77 since
(5 x 77) mod 96 = 385 mod 96 = 1(5 x 77) mod 96 = 385 mod 96 = 1
Which satisfies the above condition.Which satisfies the above condition.

20. EXAMPLE :EXAMPLE :
6. Send CT as the cipher text to the reciever.
Let us consider of encoding of alphabets as A = 1,Let us consider of encoding of alphabets as A = 1,
B = 2, C = 3,….. , Z = 26.B = 2, C = 3,….. , Z = 26.
We have to encrypt a single alphabet ‘F’ (F = 6) We have to encrypt a single alphabet ‘F’ (F = 6)
using this scheme, with B’s public key as 77 using this scheme, with B’s public key as 77
(known to A and B) and B’s private key as 5 (known to A and B) and B’s private key as 5
(known only to B).(known only to B).
CT = PTCT = PT mod 119 =
ᴱ
mod 119 =
ᴱ
mod 119 = 41 mod 119 = 41
5
6
Send 41 as the cipher text to the reciever.Send 41 as the cipher text to the reciever.

21. EXAMPLE :EXAMPLE :
7.For decryption at the reciever, calculate the plain text
PT from the cipher text CT as follows :
PT = CT mod N.
ᴰ
PT = CTPT = CT mod 119 = mod 119 = 6
ᴰ
mod 119 = mod 119 = 6
ᴰ
Which was the original plain text i.e. the code of Which was the original plain text i.e. the code of
‘F’.‘F’.
77
41

22. 1.1.Encode the originalEncode the original
character using A=1,character using A=1,
B=2 etc.B=2 etc.
2. Raise the number to2. Raise the number to
power E, here 5.power E, here 5.
3.3.Divide the result by 119Divide the result by 119
and get the remainder.and get the remainder.
The resulting number isThe resulting number is
the cipher text. the cipher text.
F 6
Results modulo 119
= 41

Results modulo 119
6 F
5
6
F 41 F77
41
1.1.Raise the number to theRaise the number to the
power D, here 77.power D, here 77.
2. Divide the result by 1192. Divide the result by 119
and get the remainder.and get the remainder.
The resulting number isThe resulting number is
the plain text.the plain text.
3.3.Decode the originalDecode the original
character using 1=A,character using 1=A,
2=B etc.2=B etc.
Encryption algorithm using the Encryption algorithm using the
public keypublic key
Decryption algorithm using Decryption algorithm using
the private keythe private key

23. SUMMARY :SUMMARY :

Firstly Prime Numbers, Prime Factorization Firstly Prime Numbers, Prime Factorization
And Greatest Common Divisor were And Greatest Common Divisor were
discussed.discussed.
Secondly Fermat’s Theorem and its proof is Secondly Fermat’s Theorem and its proof is
done.done.
Then Euler Totient Function is discussed.Then Euler Totient Function is discussed.
Lastly Euler’s Theorem is discussed.Lastly Euler’s Theorem is discussed.

24. REFERENCES :REFERENCES :
[1] Cryptography and Network Security Principles [1] Cryptography and Network Security Principles
and Practice, Fifth Edition, By: William Stallings.and Practice, Fifth Edition, By: William Stallings.
[2] Cryptography and Network Security, Chapter 9 [2] Cryptography and Network Security, Chapter 9
Mathematics of Cryptography, Part III: Primes and Mathematics of Cryptography, Part III: Primes and
Related Congruence Equations, By: Behrouz Related Congruence Equations, By: Behrouz
Forouzan.Forouzan.
[3]L. Levine, \Fermat's Little Theorem: A Proof by [3]L. Levine, \Fermat's Little Theorem: A Proof by
Function Iteration," Math. Mag. 72 (1999), 308-Function Iteration," Math. Mag. 72 (1999), 308-
309.309.
[4] C. Smyth, \A Coloring Proof of a Generalisation [4] C. Smyth, \A Coloring Proof of a Generalisation
of Fermat's Little Theorem," Amer. Math. Monthlyof Fermat's Little Theorem," Amer. Math. Monthly
93 (1986), 469-471.93 (1986), 469-471.

25. THANK YOU.THANK YOU.