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.
Another way to look at this: if x == 2 (mod Mp), then x = kMp+2. X is square
if sqrt(kMp+2) is an integer.
If there was a "square" test, this approach would still take ~Mp tests. What
we need here is some way to construct k, or at least eliminate k's faster
than the growth rate of Mp. I would imagine a "square" test would look a lot
like one of the better factoring algorithms.
-Shaun
Shaun Griffith, Texas Instruments MSP Multimedia, [EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>
work (972)480-2186, fax (972)480-3555, pager (972)598-6823
alpha pager: [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>
Quantum Mechanics: The dreams stuff is made of
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
