The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Euler's Phi Function Applied to Large Numbers

Date: 08/23/2004 at 12:27:22
From: Aruna
Subject: Finding the phi (Euler's function)  of a large number

Euler's phi function [phi(N)] is defined as the number of numbers less
than N and coprime to N.  I need to find the phi of a large number.  I
understand that if this number is a prime P, then phi(P) = P - 1.
However, the number I have in mind is composite and may be a 10 digit

I want to know if this can be done in polynomial time, and if so, is 
there an algorithm for it?

I realize that one way to do this is to find the prime factorization 
of the number N.  We know that phi(P*Q) = (P-1) * (Q-1), if P and Q 
are primes.  However, factorization itself is a hard problem.

Thank you!

Date: 08/23/2004 at 15:21:38
From: Doctor Vogler
Subject: Re: Finding the phi (Euler's function)  of a large number

Hi Aruna,

Thanks for writing to Dr Math.  The answer to your question is no,
there is no known way to get phi(n) in polynomial time for general
(large) n.  In fact, if n is a product of two primes,

  n = p*q

then finding phi(n) is equivalent to factoring n, because if you can
find phi(n), then

  p + q = n + 1 - phi(n)
  p * q = n,

so p and q are, respectively,

  n + 1 - phi(n) + sqrt((n + 1 - phi(n))^2 - 4n)


  n + 1 - phi(n) - sqrt((n + 1 - phi(n))^2 - 4n)

And those two expressions are very easy to calculate.  So if you could
compute phi(n) in polynomial time, then you could factor n in 
polynomial time, and it is conjectured (but not yet proven) that it is
impossible to factor n in polynomial time.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum 
Associated Topics:
College Algorithms
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.