If p is a prime which for which 2^22-th roots of unity exist,
then p == 1 (mod 2^22). All such primes have 2 as a square, but 2 will
be a 2^22 power only one time in 2^21.
Of the 2^61/ln(2^61) primes between 2^61 and 2^62,
only one in 2^42 will meet both requirements.
You should find about 2^19/(61*ln(2)) ~= 520000/ 42 ~= 12000 cases.
To test whether 2 is a 2^22-the power, check whether
2^((p-1)/2^22) == 1 (mod p).
Once a p is found, you can take 22 successive square roots,
starting with sqrt(2). One algorithm for sqrt(y0) mod p where y0 <> 0
picks a random nonzero x0 and tries to solve the simultaneous equations
x^2 == y0 (mod p)
(x + x0)^((p-1)/2) == 1 (mod p)
The hope is that one of sqrt(y0) + x0 and -sqrt(y0) + x0
will be a quadratic residue, the other a non-residue.
This will happen for about half of the possible x0
values (precisely those for which x0^2 - y0 is a non-residue).
The left side of the degree-((p-1)/2) equation is
computed modulo the quadratic x^2 - y0 (and modulo p),
until one gets a linear equation ax == b (mod p).
If a is nonzero, one solves for x.
If a is zero, try another x0.
Getting a (2^22)-th root of 1 is easier.
Try x0^((p-1)/2^22) mod p, where x0 is a quadratic non-residue.
Peter Montgomery
> Jason Stratos Papadopoulos <[EMAIL PROTECTED]> asked
Hello. I'm putting the finishing touches on a large-integer convolution
library that's optimized for the Alpha ev6, and I want to build support
for Mersenne-mod convolution right into the library. However, the
library is integer-only and works with integers modulo a 62-bit prime
(eventually several 62-bit primes, once I code up Chinese remainder
convolution). This means that in order to perform DWT arithmetic I have to
find n_th roots of 2 in a finite field modulo a given prime, where n is a
large power of two.
I have no clue how to do this. Nick Craig-Wood's page gives some hints for
the special case of 2^64-2^32+1, but not enough for me to apply the theory
to other primes. It looks like you need to find primes p so that
(p-1)/(order of 2 mod p) has a large power of 2 as a factor. 62-bit primes
where this is the case seem quite rare; I've found only 14 primes of this
size that allow a Mersenne DWT of size 2^22 or more (out of a billion
candidates).
But now I need some way to figure out the actual root of two. Can anybody
point me in the right direction?
jasonp
PS: This code promises to be the fastest integer-only LL test available.
It's already producing runtimes in the ballpark of floating point code,
and will improve more when I add CRT code and optimize more heavily.
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
