How Is the Euler Totient Function Applied in Real Life?

[matqkks]

What is most motivating way of introducing this function? Does it in itself have any real life applications that have an impact. I can only think of a^phi(n)=1 (mod n) which is powerful result but is this function used elsewhere.

 

[jim mcnamara]

It is part of the RSA encryption scheme. Is that what you mean? ssh RSA keys which allow passwordless connections over the ssh protocol rely on RSA.

So a more general answer might be "cryptography"

 

[rcgldr]

I don't know what RSA encryption uses, but if n in (a^phi(n)) mod (n) = 1 is a product of 2 or more prime numbers, then phi(n) returns the count of how many numbers from 1 to n-1 are not multiples of those prime numbers. For example, if n = 3 x 37 = 111, then phi(n) = (3-1) (37-1) = 72, so there are 72 numbers from 1 to 110 not multiples of 3 or 37. Multpilication and division of any pair of those 72 numbers will produce a result that is part of the 72 number group, but addition and subraction may produce results that are not within the group.

If n is a prime number, then phi(n) is n-1, and there is at least one "primitive" often called "alpha" where every number 1 through n-1 mod n in the field can be considered as a power of "alpha" mod n. This can be the basis for a finite field group (add, subtract, multiply, divide all produce numbers within the group). Reed Solomon error correction code can be based on this type of finite field, such as pdf417 bar codes which use n = 929.

However, most error correction code is based on polynomials with singe bit coefficients (finite field mod 2) called a generator polynomial "g". Such a polynomial can be treated as a binary integer but the mathematical operations addition and subtraction are implemented as exclusive or. A finite field uses single bit polynomials modulo a generator polynomial "g".

Part of AES encryption calculates 1/x for 8 bit polynomials modulo the 9 bit polynomial $1 x^8 + 1 x^4 + 1 x^3 + 1 x + 1$ (hex 11b).

 

[rcgldr]

I forgot to mention that although (a^phi(n)) mod n = 1, phi(n) may not be the smallest value that results in (a^j) mod n = 1. Using the example in my previous post for n = 3 x 37 = 111, j is never greater than 36, regardless of a, and in the case of a = 73, j is 2: (73^2) mod 111 = 1.