Re: Modular arithmetic question

From: Bart Goddard (goddardbe_at_netscape.net)
Date: 07/22/04 

Date: 22 Jul 2004 17:39:26 GMT

Lance Lamboy wrote:

> It looks like there are methods that are more practical than mine.
> But a commonality is that you have to be able to factorize k. Am I
> correct in my understanding that there is no known efficient way to
> solve this problem when the factorization of k is unknown (and k is
> large)?

That's pretty much the state of the problem. Shanks has an
algorithm for computing square roots mod p (a prime) which
mimics Newton's Method, but the algorithm doesn't work for
complex modulus.

If you could quickly compute the square roots of -1 mod F_n
(the nth Fermat number) two of them are trivial,
+/-2^(2^(n-1)) and if F_n is composite, another pair
+/- b is not trivial.

Since b^2=-1 mod F_n, there's an elementary way to write
F_n as the sum of two squares. Since F_n is defined as the
sum of two _other_ squares, we can now apply Euler's factorization
method and factor F_n. We can apply the same trick to any of
the factors.

So finding a square-root of -1 algorithm for composite moduli
would be a big deal. If you can find two different (not by sign)
square roots of -1 modulo k, then you can factor k by Euler's
method.

Bart

Relevant Pages

  • 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)
  • Reduction from FACTORING to SQROOT
    ... I would like to know if it exists a reduction from the factorization ... problem to the square roots problem, ... n by applying the Rabin algorithm. ...
    (sci.crypt)
  • number of the beast
    ... by accident I found an algorithm with a quite funny result. ... I told my computer to sum up square roots, starting with i=1, stopping at n. ...
    (sci.math.num-analysis)
  • Re: square roots mod p.
    ... the algorithm in the "Handbook of Applied Cryptography" by Menezes, ... Legendre symbol of a mod p and found that a is a quadratic residue ... The expected running time of the ... r and -r are the two square roots of a mod p. ...
    (sci.math)
Quantcast