Hi folks
>Benny Van Houdt asked about checking 2 mod Mp for "square-ness". [digest
>#537]
>The hard way is to square every number from sqrt(Mp) to Mp-1, mod Mp, for
>equality to 2. This will take ~`(Mp-sqrt(Mp)) square/mod operations, or
>O(Mp)...too long.
Just a suggestion to you all... don't take this question at face value.
2^(p+1)/2 is an obvious square root of 2 for odd Mersenne exponent p. (For
even Mersenne exponents, 3 divides Mn, 2 is not a square mod 3, therefore
can't be a square mod Mn).
The point Shaun was aiming for is, if Mp is composite, then 2 has more than
two "square roots" modulo Mp. In fact, it has 2^x square roots, where x is
the number of distinct prime factors of Mp. (2 has two square roots modulo
each prime factor and the result follows from the Chinese remainder
theorem). Hence, find one of the non-obvious square roots, and you'll be
able to deduce a factor.
Quick example, 2 has square roots 64 and -64 modulo 2^11-1. But it also has
the less obvious ones 915 and -915. Do a gcd calculation of 2^11-1 with
915+64 and 915-64, and the factors 23 and 89 will appear. (since these other
roots must be equal to one or other of the more obvious ones modulo some
prime factor).
As far as looking for such solutions goes, you could attempt the following
method. Attempt to solve x^2-Dy^2=2, where D=Mp. Such a solution will have
x/y a good rational approximation to sqrt(D), and such good rational
approximations can be generated by continued fractions. However, there's no
guarantee that if you find a solution, it isn't one of the known ones, not
to mention the method involves some rather hairy manipulation of quadratic
surds. The method has been used in the past (by I think Pollard) to generate
several relatively small quadratic residues modulo some composite N as an
aid to factoring. As here, the idea is to find two numbers a and b so
a^2=b^2 mod N, then examining (a-b) and (a+b) for common factors with N. Not
for the faint-hearted either - the residues generated may still be as large
as sqrt(N) and may themselves require factoring before two equal squares
modulo N are found.
Chris Nash
Lexington KY
UNITED STATES
=======================================================
Co-discoverer of the 7th and 10th largest known primes.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
