Reduction from FACTORING to SQROOT

From: eugol (ep_at_eugeniopolito.it)
Date: 11/18/05 

Date: 18 Nov 2005 11:34:47 -0800

Hello,
I'm a new user of this group.

I would like to know if it exists a reduction from the factorization
problem (FACTORING) to the square roots problem (SQROOT), different
from the Rabin algorithm.
That is, if i have a square root modulo a composite n, i can factorize
n by applying the Rabin algorithm. Does exist a different way
(algorithm) to prove this result?

Thanks a lot.
Regards,
Eugenio

Relevant Pages

  • Re: Modular arithmetic question
    ... > solve this problem when the factorization of k is unknown (and k is ... algorithm for computing square roots mod p which ... If you could quickly compute the square roots of -1 mod F_n ... F_n as the sum of two squares. ...
    (sci.math)
  • Re: RSA encryption/decryption
    ... >>If you have e and d, with polynomial time work, you can factor. ... >>Getting e would just be another factorization method. ... square roots (and it is probabalistic, taking a random number M mod N, ... must divide M-M' and the other M+M' and GCDgives a factor of N. ...
    (sci.crypt)
  • Re: RSA encryption/decryption
    ... >> I know public key N and decryption exponent d, so I can decrypt messages ... >With a factorization you can get e from d. ... taking square roots is trivial. ...
    (sci.crypt)
  • Re: Reduction from FACTORING to SQROOT
    ... >I would like to know if it exists a reduction from the factorization ... >from the Rabin algorithm. ... Kristian Gjøsteen ...
    (sci.crypt)