Euler’s Totient Function and Public Key Cryptography

Introduction

Several times as a consultant, I’ve had the opportunity to design and implement some

cryptosystems. Invariably I need to explain to the client the theory behind the methods

and this discussion leads to totients. Since many have never heard of or are familiar with

Euler’s totient function, I thought I’d put together a paper describing this function and its

relation to public key cryptography.

I will keep this paper in a somewhat informal style, but I will use some seemingly arcane

mathematics terms. However when I use them I will provide their definitions.

Euler’s Totient Function.

In order to talk about this, I will need to give a few definitions – some of these should

already be familiar to the reader. So here goes:

•

Natural Number – a number from the set of {1,2,3,L,∞}

•

Integer – a number in the set {−∞,L,−2,−1,0,1,2,L,∞}

•

and itself.

Prime Number – a natural number (greater than one) that is only divisible by one

•

Composite Number – a natural number (greater than one) that is not prime.

•

Greatest Common Divisor – the largest common factor of a set of numbers.

•

gcd(a,b) - mathematical shorthand for the greatest common divisor of a and b.

•

Coprime – a set of numbers is coprime if their greatest common divisor is one.

•

Relatively Prime – the same thing as coprime.

•

number.

So now with these definitions we can quite tersely define Euler’s

as the number of totatives of

function or simply the phi function. What does this definition really mean? It means that

the Euler totient function gives a count of how many numbers in the set, {1,2,3,

Totative – a number,m < n , is a totative of n if gcd(m,n) =1, where n is a natural1 totient function,ϕ (n) ,n. Sometimes the Euler totient function is called Euler’s phiL,n}

1

contributions to the fields of Calculus, Graph Theory, Mathematical Analysis, Mechanics, Optics, and

Astronomy. He is considered by many to be the top mathematician of the 18

Leonhard Paul Euler [1707 - 1783], a Swiss mathematician and physicist, who made a great number ofth century.

share no common factors with

evaluating the totient.

References

[1] R. Rivest, A. Shamir, L. Adleman, “A Method for Obtaining Digital Signatures and

Public Key Cryptosystems”

[2] J. Sylvester, “On Certain Ternary Cubic Form Equations”,

280-285, 357-393

[3] W. Diffie, M. Hellman,”New Directions in Cryptography”,

Information Theory

[4] L. Blum, M. Blum, M. Shub, “A Simple Unpredictable Pseudo-Random Number

Generator”,

[5] A. A. Gioia, The Theory of NumbersMIT/LCS/TM-82, Apr 1977Amer. J. Math. 2 (1879) ppIEEE Trans. On,pp 644-654, Nov 1976SIAM Journal on Computing,vol 15, pp 364-383, May 1986., Dover Publications, New York, 2001n that are greater than one. We will soon get in to