Calculating Euler phi function

In summary, the Euler phi function is used in RSA encryption and requires knowledge of the prime factorization of the input. If the input is the product of two primes, then the formula for computing the Euler phi function is (p-1)(q-1). This can be implemented in Matlab using the method described in the Wikipedia link provided.
  • #1
paton51
8
0
How do i comput the euler phi function of a large interger?
i know that if p is prime then phi(p)=p-1 and I've found a formula for computing non primes but i don't know how to implement in something like Matlab.
Does anyone know how?
 
Mathematics news on Phys.org
  • #2
AFAIK, computing the Euler phi function requires you to know the prime factorization of the input. Unless you can find it, there's not much you can do.
 
  • #3
Yes i know the factorisation problem is hard. I am workin with RSA encryption so we know two large primes, the product of which is N this is what i want to do euler phi on.
Since N is the product of two primes (p and q) is phi(N) simply (p-1)(q-1)?
 

FAQ: Calculating Euler phi function

What is the Euler phi function?

The Euler phi function, also known as Euler's totient function, is a mathematical function that counts the number of positive integers less than or equal to a given number that are relatively prime to it. It is denoted by φ (n).

How do you calculate the Euler phi function?

The Euler phi function can be calculated using the formula φ (n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk), where n is the given number and p1, p2, ..., pk are its prime factors.

What is the significance of the Euler phi function?

The Euler phi function has many applications in number theory and cryptography. It helps in determining the number of integers coprime to a given number, which is useful in solving various mathematical problems.

What is the relationship between the Euler phi function and the prime factorization of a number?

The Euler phi function is closely related to the prime factorization of a number. It uses the prime factors of a number to calculate the number of integers that are relatively prime to it.

Can the Euler phi function be calculated for non-positive integers?

No, the Euler phi function is defined only for positive integers. For negative integers, the value of the function is undefined. For 0, the value is 0.

Similar threads

B Calculating the coprime probability of two integers in a different way
Replies
13
Views
2K
I Connection of zeta to primes: less Euler than error or L-functions?
Replies
2
Views
1K
I Extend Euler Product Convergence Over Primes: Basic Qs
Replies
1
Views
1K
A Help needed with derivation: solving a complex double integral
Replies
1
Views
1K
Insights Investigating Some Euler Sums
Replies
1
Views
2K
I Can Angular Velocity Accurately Control Ragdoll Limbs in Game Physics?
Replies
5
Views
1K
A How do I express an equation in Polar coordinates as a Cartesian one.
Replies
1
Views
2K
MHB Prove congruence for powers of 2
Replies
3
Views
2K
I Question about the Divisor Function/Sums and Project Euler
Replies
4
Views
2K
MHB Solving SIR Model with Euler's Method
Replies
7
Views
3K

Hot Threads

Recent Insights

Back
Top