Q: Factoring a number whose Euler phi is known?

From: Klaus Pommerening (pom@imsd.uni-mainz.de)
Date: 02/12/03 

From: Klaus Pommerening <pom@imsd.uni-mainz.de>
Date: Wed, 12 Feb 2003 12:52:34 +0100

How to factor a number n given the value \phi(n) where \phi is the
Euler Phi function?

This problem is related to the security of RSA encryption.

When the modulus n is a product of 2 primes p and q, there is an obvious
and well known algorithm:
  \phi(n) = (p-1)(q-1),
therefore
  p + q = n + 1 - \phi(n),
   pq = n
are known, and this results in a quadratic equation for (say) p that
is easily solved.

RSA works when the modulus n is squarefree. So the following questions
are of interest:

- Is there a solution in the case that n has 3 prime factors?
- What in the case of r \geq 3 prime factors and r is known?
- What in the case where r is unknown?

Remark. There is a probabilistic algorithm: Choose a "public" exponent
e,
construct a corresponding "private" exponent d such that ed \equiv 1
\pmod {\phi(n)}. Then use d to factor n by the well known probabilistic
algorithm.

My question asks for a deterministic algorithm. 

-- 
Klaus Pommerening [http://www.uni-mainz.de/~pommeren/]
Institut fuer Medizinische Biometrie, Epidemiologie und Informatik
Johannes-Gutenberg-Universitaet Mainz

Relevant Pages

  • Re: RSA Blinding
    ... the LTM book first shows the connection ... instead it referred to the i'th k-bit digit of the exponent b". ... then give figure 7.4 which is pseudo-code for the algorithm [and yes ... Section 7.2.2 introduces the sliding window where basically you slide ...
    (sci.crypt)
  • Re: Math processor
    ... >Perhaps you can slant your project towards something low end like "How ... >be more achievable than say "The worlds fastest 2048bit RSA encryption ... >algorithm" implemented in a bleeding edge FPGA. ...
    (sci.electronics.design)
  • Re: Math processor
    ... > It can do an 1024bit RSA encryption in 7ms. ... > algorithm" implemented in a bleeding edge FPGA. ...
    (sci.electronics.design)
  • Re: Meet-in-the middle attack on DH/ El Gamal?
    ... > attack would be slower than the general discrete log algorithm. ... on a 164-bit exponent it will take ...
    (sci.crypt)
  • Re: Math processor
    ... It can do an 1024bit RSA encryption in 7ms. ... algorithm" implemented in a bleeding edge FPGA. ... people out there designing super fast encryption algorithms, ...
    (sci.electronics.design)