> That bit is virtually free of charge. Any quadratic non-residue will do
just
> >fine.
> But you don't easily know if a number is a QNR, do you?
Suppose the number you're testing is N. If we assume N is prime, then
quadratic reciprocity could be used to determine whether your base a is a
QNR. So pick your base a, do your test, which proves QNR and hence primality
(Proth's theorem basically states the Euler criterion for a QNR is necessary
*and* sufficient to prove primality). If you don't get what you expect from
the quadratic residue symbol, then it's composite. (Look up 'Kronecker
symbol' - basically, an excuse to use quadratic reciprocity whether or not
you know N is prime).
The LL test implicitly does the same for Mersenne tests - they only make
sense if 3 is a QNR. The start value S_0=4 is really
(2+sqrt(3))+(2-sqrt(3))... square that, and you'll see where the -2 comes
from :)
S_n=(2+sqrt(3))^(2^n) + (2-sqrt(3))^(2^n)
If the test proves compositeness, it doesn't matter whether 3 was *really* a
QNR or not, you've proved what you wanted either way. The final bit of glue
is that all Mersennes of odd exponent>1 are equal to 7 mod 12, and so 3 is
indeed a QNR for the prime ones.
Chris
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
