Main content
Computer science
Course: Computer science > Unit 2
Lesson 4: Modern cryptography- The fundamental theorem of arithmetic
- Public key cryptography: What is it?
- The discrete logarithm problem
- Diffie-hellman key exchange
- RSA encryption: Step 1
- RSA encryption: Step 2
- RSA encryption: Step 3
- Time Complexity (Exploration)
- Euler's totient function
- Euler Totient Exploration
- RSA encryption: Step 4
- What should we learn next?
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
Euler's totient function
Measuring the divisibility of a number. Created by Brit Cruise.
Want to join the conversation?
- I think Phi[a*b] = phi[a]*phi[b] only works if both a and b are relatively prime. Is that right?(61 votes)
- You are correct. Note that Brit said onthat Euler's Phi function is multiplicative, not completely multiplicative. 1:50
If a function f is multiplicative, then if (a,b) = 1 (gcd) → f(a*b) = f(a)*f(b)
If a function f is completely multiplicative, then for every a and b → f(a*b) = f(a)*f(b)(66 votes)
- In the graph atin the video, it seems that the set of dots coalesces into a straight line. You said those were the prime numbers. But there seems to be at least three other sets of dots that more or less coalesce into straight lines as well. Is there anything special about those sets of numbers? 1:11(26 votes)
- The above answer is very helpful, though having a miscalculation
When n and p are relatively prime, φ(n*p) = φ(n) * φ(p)
Suppose p is a prime number
φ(2p) = φ(2) * φ(p) = 1 * (p-1) = p - 1 -> k = 1/2
φ(3p) = φ(3) * φ(p) = 2 * (p-1) = 2p - 2 -> k = 2/3
φ(5p) = φ(5) * φ(p) = 4 * (p-1) = 4p - 4 -> k=4/5
φ(6p) = φ(2) * φ(3) * φ(p) = 1 * 2 * (p-1) = 2p - 2 -> k = 2/6 = 1/3
φ(7p) = φ(7) * φ(p) = 6 * (p-1) = 6p - 6 -> k = 6/7
φ(10p) = φ(2) * φ(5) * φ(p) = 1 * 4 * (p-1) = 4p - 4 -> k = 4/10 = 2/5
... ...
There're many possible values for the slope k
However, the smaller the n is, the clearer the straight line can be seen(8 votes)
- Could somebody tell me how the phi function works?(7 votes)
- Here's how the phi function works.
The phi function of n (n is a counting number, such as 1 2, 3, ...) counts the number of numbers that are less than or equal to n and only share the factor of 1 with n.
Example:
phi(15)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
15 has the factors of 3 and 5, so all multiples of 3 and 5 share the factor of 3 or 5 with 15. Therefore, they aren't counted.
1, 2, 4, 7, 8, 11, 13, 14
There are 8 numbers that only share the factor of 1 with 15. Therefore, phi(15)=8.
I hope this helps!(23 votes)
- This is very confusing. Can anyone explain this method?(7 votes)
- The proof of Phi(1st Prime) * Phi(2nd Prime) =Phi(1st Prime * 2nd Prime) seems obvious to me.
Assume A and B are Prime
We know that Phi(A) = A-1 and Phi(B) = B-1
Between 1 and (A*B), inclusive, there are B occurrences of numbers divisible by A by the definition of multiplication. Each time you add another A, you find another mutiple of A. And if you add A to itself B times, you would have B occurrences of multiples of A.
And between 1 and (A*B) there are also A occurrences of numbers divisible by B.
And because A and B are primes, there are no other occurences where the multiples overlap.
When you exclude the final number (A*B) there are (A-1) occurrences of numbers divisible by A and there are (B-1) occurences of numbers divisible by A.
The total numbers below (A*B) that are divisible by A or B is (A-1)+(B-1).
So the PHI(A*B) = All Numbers less than (A*B) less (A-1)+(B-1)
PHI(A*B) = (A*B-1) - ((A-1)+(B-1))
= A*B - 1- A + 1 - B + 1
= A*B -A - B +1 =(A-1)(B-1)
So Phi(A) = (A-1) and Phi(B) = (B-1) and Phi(A*B) = (A-1)*(B-1)
So for all primes numbers A and B, Phi(A)*Phi(B)=Phi(A*B)
I am not sure this is very eloquent, but I think the proof is correct.(13 votes)
- My son does not follow the part where, at, when trying to find the phi of 8, the number 4 is given as a solution. He can't understand what "4" has to do with any of it. Thanks!! LW 0:48(4 votes)
- simply count how many integers share no factor with 8, you always include 1. So: 1,3,5,7 = 4
phi(8) = 4(4 votes)
- Can't you find the phi of anything by figuring out its prime factorization?(4 votes)
- Yes, one can find the phi of a positive integer by figuring out its prime factorization
In general, for each of its prime factors, p, with a multiplicity, k
phi= product of ( p^(k-1)*(p-1) ) for all of its factors
e.g. 360=8 * 9 * 5=2^3 * 3^2 * 5
phi(360)= (2^2) * (2-1) * (3^1) * (3-1) * (5^0) * (5-1)
phi(360)= 4 * 1 * 3 * 2 * 1 * 4
phi(360)= 96
Unfortunately, factoring numbers is a hard problem when the numbers become large. In fact, RSA and some other cryptographic schemes rely on large numbers being hard to factor (someone who could factor these big numbers would be able to crack these codes).
Hope this makes sense(5 votes)
- Why does phi(8) = 4??
Please answer.(2 votes)- The Euler's Totient Function counts the numbers lesser than a number say n that do not share any common positive factor other than 1 with n or in other words are co-prime with n.
For 8 :
1 and 8 are co-prime as the only common factor is 1 itself
2 and 8 have a common factor 2
3 and 8 are co-prime
4 and 8 have a common factor 2
5 and 8 are co-prime
6 and 8 have a common factor 2
7 and 8 are co-prime
8 and 8 have a common factor 2
Hence, there are 4 numbers(1,3,5 and 7) that are lesser than 8 and are co-prime with it.
So, phi(8) = 4(6 votes)
- Don't prime numbers do have factors greater than 1 (themselves)? 1:10(2 votes)
- Yes, but generally we don't count that and it is not counted to calculate the (phi) of a number.(4 votes)
- "remember: we are using gcd(a,b) = 1" What is that supposed to mean? 1:51(2 votes)
- It means the greatest common denominator (gcd) of a and b are 1.
When the gcd(a,b)=1, then a and b are coprime, that is, they don't share any prime factors.
We can only use phi(a*b)=phi(a)*phi(b) when a and b don't share common factors i.e. gcd(a,b)=1
e.g phi(7)=6 ,phi(8)=4
7 and 8 share no prime factors i.e. gcd(a,b)=1
phi(56)=phi(7)*phi(8)=6*4=24
e.g. phi(8)=4,phi(12)=4
8 and 12 share common prime factors (both have 2 as a prime factor)
gcd(8,12)=4
phi(96)=32 which does not equal phi(8)*phi(12)=16
Hope this makes sense(3 votes)
- Is there a good way to determine if a number is prime? It seems like the phi function is useful for primes, but only if we know from the start that the number is prime.(2 votes)
- The 100% sure way to tell if n is prime is to check all numbers > 1 and <= sqrt(n) for factors. If there are none it is prime. Of course, for large numbers it's really slow.
So, in practice probabilistic tests are used to see if n is probably prime. If we assume n is prime, then we can assume it's value of phi is just n-1. We can test whether that assumption is false, by using properties established by Euler's Theorem i.e. a^phi(n) mod n = 1 mod n, where a is coprime to n. If we can find any values of a that don't satisfy that property then n is not prime. If instead, we test a bunch of values of a, and none of them fail, we can become more and more satisfied that n is probably prime.(2 votes)
Video transcript
- [Voiceover] Euler
continued to investigate properties of numbers, specifically the distribution of prime numbers. One important function he defined is called the phi function. It measures the breakability of a number. So, given a number, say N, it outputs how many integers
are less than or equal to N that do not share any
common factor with N. For example, if we want
to find the phi of eight we look at all values from one to eight, then we count how many integers eight does not share a
factor greater than one with. Notice six is not counted, because it shares a factor of two, while one, three, five
and seven are all counted, because they only share a factor of one. Therefore, phi of eight equals four. What's interesting is that calculating the phi function is
hard, except in one case. Look at this graph. It is a plot of values of phi, over integers from one to 1,000. Now, notice any predictable pattern? The straight line of points along the top represent all the prime numbers. Since prime numbers have no
factors greater than one, the phi of any prime number, P, is simply P minus one. To calculate phi of seven, a prime number, we count all integers, except seven, since none of them share
a factor with seven. Phi of seven equals six. So, if you're asked to find
phi of 21,377, a prime number, you would only need to subtract one to get the solution, 21,376. Phi of any prime is easy to compute. This leads to an interesting
result based on the fact that the phi function
is also multiplicative. That is, phi A times B
equals phi A times phi B. If we know some number N is
the product of two primes, P one and P two, then phi of N is just the value of phi for
each prime multiplied together, or P one minus one, times P two minus one.