UNREASONABLE EFFECTIVENESS OF NUMBER THEORY

11

given by a number in the same range, calculated as follows

E =

Ms

mod r . (6)

Decrypting E is accomplished by calculating

El

mod r, where the decrypting

exponent t is given by

ts = 1 mod (j)(r) , (7)

i.e., ts = kj(r) + 1 for some k. With such at,

El

=

Mst

=M

k

^

( r ) + 1

mod r .

which, according to Euler's theorem, give the message M back.

So far, so good and - theoretically - trivial. The trick in public-key

encryption is to choose r as the product of two very large primes, each say 200

digits long. (There is no paucity of such primes, and enough for all

foreseeable purposes can be easily ferreted out from the jungle of composites

in the

10200

neighborhood.)

Now, with a composite r, prescription (7), so easily written down,

becomes practically impossible to apply because j)(r) can be calculated only

if the factors of r are known - and this knowledge is not published. In modern

parlance, the mapping (6) is a trap-door function.

A trap-door function is, as the name implies, a (mathematical) function

that is easy to calculate in one direction but very hard to calculate in the

opposite direction. For example, it takes a modern computer only

microseconds to multiply two 100-digit numbers. By contrast, to decompose

a 200-digit number, having two 100-digit factors, into its factors can take

"forever," even on the fastest computers available in 1992 and using the most

efficient factoring algorithms known today [3].

On the other hand, knowing the factors of r, as the legitimate recipient of

the encrypted message E does, j(r) can be easily calculated and decrypting

becomes possible. The decrypting exponent t is obtained by Euclid's

algorithm [7] or by solving (7) directly:

t s s * ^ " "

1

mod (j)(r) .