24Practical use of this theorm::
(No releavance with JEE ofcourse)
Euler’s theorem is widely used in cryptography. The encryption scheme used nowadays,
called the RSA algorithm, works as follows:
A merchant wants to obtain the credit card number of a customer over the Internet.
The information traveling between the two can be viewed by anyone. The merchant is in
possession of two large prime numbers p and q. It transmits to the customer the product
n = pq and a positive integer k coprime to φ(n) = (p − 1)(q − 1). The customer
raises the credit card number α to the kth power, then reduces it modulo n and transmits
the answer β to the merchant. Using the Euclidean algorithm for the greatest common
divisor, the merchant determines positive integers m and a satisfying
mk − a(p − 1)(q − 1) = 1.
Then he computes the residue of βm modulo n. By Euler’s theorem,
βm ≡ αmk = αa(p−1)(q−1)+1 = α(p−1)(q−1)a · α = αφ(n)a · α ≡ α (mod n).
For n sufficiently large, the residue class of α modulo n is α itself. The merchant was
able to retrieve the credit card number.
As of this date there is no known algorithm for factoring numbers in polynomial time,
while large primes can be found relatively quickly, and for this reason an eavesdropper
cannot determine p and q from n in a reasonable amount of time, and hence cannot break
the encryption.
