268 5 Number Theory
Euler’s theorem is widely used in cryptography. The encryption scheme used nowa-
days, 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 numberspandq. It transmits to the customer the product
n=pqand a positive integerkcoprime toφ(n)=(p− 1 )(q− 1 ). The customer
raises the credit card numberαto thekth power, then reduces it modulonand transmits
the answerβto the merchant. Using the Euclidean algorithm for the greatest common
divisor, the merchant determines positive integersmandasatisfying
mk−a(p− 1 )(q− 1 )= 1.Then he computes the residue ofβmmodulon. By Euler’s theorem,
βm≡αmk=αa(p−^1 )(q−^1 )+^1 =(
α(p−^1 )(q−^1 ))a
·α=(
αφ(n))a
·α≡α(modn).Fornsufficiently large, the residue class ofαmodulonisα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 determinepandqfromnin a reasonable amount of time, and hence cannot break
the encryption.
783.Devise a scheme by which a bank can transmit to its customers secure information
over the Internet. Only the bank (and not the customers) is in the possession of the
secret prime numberspandq.
784.A group of United Nations experts is investigating the nuclear program of a country.
While they operate in that country, their findings should be handed over to the
Ministry of Internal Affairs of the country, which verifies the document for leaks of
classified information, then submits it to the United Nations. Devise a scheme by
which the country can read the document but cannot modify its contents without
destroying the information.
5.2.7 The Chinese Remainder Theorem...........................
Mentioned for the first time in a fourth-century book of Sun Tsu Suan-Ching, this result
can be stated as follows.
The Chinese Remainder Theorem.Letm 1 ,m 2 ,...,mkbe pairwise coprime positive
integers greater than 1. Then for any integersa 1 ,a 2 ,...,ak, the system of congruences
x≡a 1 (modm 1 ), x≡a 2 (modm 2 ),...,x≡an(modmk)has solutions, and any two such solutions are congruent modulom=m 1 m 2 ...mk.