# Euler Totient or Phi Function

 HW Helper P: 7,132 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).