Re: Q: Factoring a number whose Euler phi is known?

From: Stefan Katzenbeisser (katzenb@REMOVEdbai.tuwien.ac.at)
Date: 02/12/03 

From: Stefan Katzenbeisser <katzenb@REMOVEdbai.tuwien.ac.at>
Date: Wed, 12 Feb 2003 15:25:21 +0100

In article <3E4A3582.D00FB8F2@imsd.uni-mainz.de>, Klaus Pommerening wrote:

>
> 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.

There is a far better algorithm for that problem: try to
find a non-trivial square root of 1 modulo n, given
an "oracle" that computes any multiple of d=\lambda(n),
where \lambda is Carmichael's function (\phi is always a multiple
of \lambda). Any such square root immediately yields to a
factorization of n.

If d=(2^k)d', there exists a probabilistic algorithm that
outputs such a non-trivial square root in time polynomial
in k and log(n). If n is a RSA modulus, the success probability
is greater 1/2, but the algorithm should also work for arbitrary n
(however, I don't know its success probability right now).

>
> My question asks for a deterministic algorithm.

To my knowledge, there is no deterministic algorithm
known, but I may have missed something here. It _is_ known
that there is a deterministic algo for that problem once
you assume the correctness of Riemann's hypothesis, though...

Hope this helps!

-S
 

Relevant Pages

  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... probability of mathematical failure just means that you are getting your ... contract for an algorithm, then it should do that, ... adverse effect is less than chance of all of you spontaneously ...
    (sci.crypt)
  • Re: Primes algorithm
    ... > method which is generally used, as far as I know, is the Miller-Rabin ... > algorithm, ... > that a given number is composite, then it is definitely composite; ... A number is prime with a probability equal to either 0 or to 1. ...
    (sci.crypt)
  • Re: Deterministic Algorithm for Random Number Generation Using Coin Flips
    ... -the algorithm can guarantee that there is 0 probability that the ... algorithm will run forever. ... generator that is guaranteed to terminate after finite throws? ... the rng be random? ...
    (sci.math)
  • Re: Deterministic Algorithm for Random Number Generation Using Coin Flips
    ... -the algorithm can guarantee that there is 0 probability that the ... algorithm will run forever. ... (or assuming the coins were not labeled: toss #1, toss #2, or toss ... Take a red coin and a green coin and toss ...
    (sci.math)
  • Re: random variable
    ... Looking at the documentation for rand, I see that both the 'twister' ... and 'state' random number generators generate numbers in the closed ... implication is that there is an algorithm similar to r = 2^53 * n where n ... probability of producing any of the numbers in one of these intervals must ...
    (comp.soft-sys.matlab)
Quantcast