Euler Phi Function (part one of three)
.. is a really cool function. For those of you who don't know, you are using it pretty much every day -- at least when you are using computers, and more specifically encryption.
"Why should I care?" You find yourself asking. "It doesn't apply to me." Well, actually, it does -- It forms the most significant part of the underpinnings of the most famous (and widely-used) cipher, called RSA. RSA is what is known as a public key cipher -- where the ability to encrypt information is not at all the same as the ability to decrypt it. RSA impacts you directly because it is used in E-commerce, secure on-line transactions, and you even use it when you log onto LiveJournal. Yep, LJ uses it, and you didn't even know about it. Weird, huh?
[To eliminate shock, phi is usually printed this way: Φ If your browser can't display that, it looks like a small circle with a vertical slash thru it.]
What does it do? Well, in simplest terms, it is the count of the number of positive integers less than a given integer that are relatively prime to the given integer.
Some explanations are in order here, since I just threw a bunch of jargon in your face. In mathematician speak, the positive integers are the numbers in the set 1, 2, 3, 4, etc. In other words, the numbers without a fractional part that are greater than zero. Also, two integers are said to be relatively prime to each other when the greatest integer that will evenly divide both of them (that is, without a fraction or a remainder) is one. So, 4 and 5 are relatively prime, but 4 and 6 are not (2 evenly divides both four and six). Also, zero and one are (by definition) relatively prime to every integer.
It is worth noting that all prime numbers (by their very definition) are relatively prime to positive number less than them. This means that Φ(p) = p - 1, where p is a prime number. For example Φ(5) = 4. In this case the four integers in question are 1, 2, 3, and 4. This rule can be generalized to any power of a prime number (that is, a prime number multiplied by itself any number of times.) Using the carat as a power symbol, (x^y == x times itself y times) this means that Φ(p^n) = p^n - p^(n-1). For example, Φ(9) = Φ(3^2) = 3^2 - 3^(2-1) = 9 - 3 = 6. (1, 2, 4, 5, 7, and 8 are relatively prime to nine.)
But not all numbers are as clean as prime numbers and powers of prime numbers. In fact, for some numbers, phi is down right messy to calculate, and this is where we can start using phi in cryptography.
Phi is what is known as a multiplicative function. What this means is that Φ(n*m) = Φ(n) * Φ(m) -- Provided that n and m are relatively prime to each other.
Using these two pieces of information, you can calculate phi for any number, provided you know that number's factorization. Remember, two paragraphs ago, when I said that phi could be messy to calculate? If you don't know and can't obtain a number's factorization, phi is next to impossible to figure out. I'll explain in part three the implications of that caveat, and why this should give you (some) peace of mind.
Take for example Φ(20) = Φ(4*5) = Φ(4) * Φ(5) = Φ(2^2) * Φ(5) = (2^2 - 2^1) * (5 - 1) = 2 * 4 = 8. This means that there are 8 numbers less than twenty that are relatively prime to twenty. They are: 1, 3, 7, 9, 11, 13, 17, 19. Every other number less than twenty is divisible by two or five.
Next time: Euler's discovery and RSA.
"Why should I care?" You find yourself asking. "It doesn't apply to me." Well, actually, it does -- It forms the most significant part of the underpinnings of the most famous (and widely-used) cipher, called RSA. RSA is what is known as a public key cipher -- where the ability to encrypt information is not at all the same as the ability to decrypt it. RSA impacts you directly because it is used in E-commerce, secure on-line transactions, and you even use it when you log onto LiveJournal. Yep, LJ uses it, and you didn't even know about it. Weird, huh?
[To eliminate shock, phi is usually printed this way: Φ If your browser can't display that, it looks like a small circle with a vertical slash thru it.]
What does it do? Well, in simplest terms, it is the count of the number of positive integers less than a given integer that are relatively prime to the given integer.
Some explanations are in order here, since I just threw a bunch of jargon in your face. In mathematician speak, the positive integers are the numbers in the set 1, 2, 3, 4, etc. In other words, the numbers without a fractional part that are greater than zero. Also, two integers are said to be relatively prime to each other when the greatest integer that will evenly divide both of them (that is, without a fraction or a remainder) is one. So, 4 and 5 are relatively prime, but 4 and 6 are not (2 evenly divides both four and six). Also, zero and one are (by definition) relatively prime to every integer.
It is worth noting that all prime numbers (by their very definition) are relatively prime to positive number less than them. This means that Φ(p) = p - 1, where p is a prime number. For example Φ(5) = 4. In this case the four integers in question are 1, 2, 3, and 4. This rule can be generalized to any power of a prime number (that is, a prime number multiplied by itself any number of times.) Using the carat as a power symbol, (x^y == x times itself y times) this means that Φ(p^n) = p^n - p^(n-1). For example, Φ(9) = Φ(3^2) = 3^2 - 3^(2-1) = 9 - 3 = 6. (1, 2, 4, 5, 7, and 8 are relatively prime to nine.)
But not all numbers are as clean as prime numbers and powers of prime numbers. In fact, for some numbers, phi is down right messy to calculate, and this is where we can start using phi in cryptography.
Phi is what is known as a multiplicative function. What this means is that Φ(n*m) = Φ(n) * Φ(m) -- Provided that n and m are relatively prime to each other.
Using these two pieces of information, you can calculate phi for any number, provided you know that number's factorization. Remember, two paragraphs ago, when I said that phi could be messy to calculate? If you don't know and can't obtain a number's factorization, phi is next to impossible to figure out. I'll explain in part three the implications of that caveat, and why this should give you (some) peace of mind.
Take for example Φ(20) = Φ(4*5) = Φ(4) * Φ(5) = Φ(2^2) * Φ(5) = (2^2 - 2^1) * (5 - 1) = 2 * 4 = 8. This means that there are 8 numbers less than twenty that are relatively prime to twenty. They are: 1, 3, 7, 9, 11, 13, 17, 19. Every other number less than twenty is divisible by two or five.
Next time: Euler's discovery and RSA.