The algorithm is very simple:
1. Choose a big random value x from some very broad range
(say, {1,2,..,N^2}).
2. Pick a random element g (mod N).
3. Compute y = g^x (mod N).
4. Ask for the discrete log of y to the base g, and get back some
answer x' such that y = g^x' (mod N).
5. Compute x-x'.
On 7/9/06, Ondrej Mikle <[EMAIL PROTECTED]> wrote:
I believe I have the proof that factorization of N=p*q (p, q prime) is
polynomially reducible to discrete logarithm problem. Is it a known fact
or not? I searched for such proof, but only found that the two problems
are believed to be equivalent
Ondrej Mikle wrote:
>I believe I have the proof that factorization of N=p*q (p, q prime) is
>polynomially reducible to discrete logarithm problem. Is it a known fact
>or not?
Be careful: when most people talk about the assumption that the
discrete log problem being hard, they usually are referr
Charlie Kaufman wrote:
I believe this has been "known" for a long time, though I have never seen the
proof. I could imagine constructing one based on quadratic sieve.
I believe that a proof that the discrete log problem is polynomially reducible
to the factorization problem is much harder and
ially reducible to discrete log - known fact or
not?
Hello.
I believe I have the proof that factorization of N=p*q (p, q prime) is
polynomially reducible to discrete logarithm problem. Is it a known fact
or not? I searched for such proof, but only found that the two problems
are believed to be equi
Hello.
I believe I have the proof that factorization of N=p*q (p, q prime) is
polynomially reducible to discrete logarithm problem. Is it a known fact
or not? I searched for such proof, but only found that the two problems
are believed to be equivalent (i.e. no proof).
I still might have som
