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
