Register to reply 
Euler Totient or Phi Function 
Share this thread: 
#1
Oct2613, 09:02 AM

P: 153

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.



#2
Oct2613, 09:12 AM

Sci Advisor
PF Gold
P: 1,382

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" 


#3
Oct2613, 10:23 AM

HW Helper
P: 7,131

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 n1 are not multiples of those prime numbers. For example, if n = 3 x 37 = 111, then phi(n) = (31) (371) = 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 n1, and there is at least one "primitive" often called "alpha" where every number 1 through n1 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 [itex]1 x^8 + 1 x^4 + 1 x^3 + 1 x + 1 [/itex] (hex 11b). 


#4
Oct2713, 03:58 AM

HW Helper
P: 7,131

Euler Totient or Phi Function
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.



Register to reply 
Related Discussions  
Limit of the Euler totient function  Calculus  4  
Euler totient puzzle  Linear & Abstract Algebra  2  
Euler's Totient Function  Linear & Abstract Algebra  2  
About Euler's totient function  Linear & Abstract Algebra  2  
Euler's Totient Function Proving  General Math  1 