The behavior of the recursion x[n+1] = x[n]^2 - 2 can be precisely
analyzed. (In fact, it is because of this that the LL-test works at
all.) For a fixed prime p, the periodicity depends on the factorization
of either p-1 (if x[1]^2-4 is a quadratic residue mod p) or p+1 (if
x[1]^2-4 is a quadratic nonresidue mod p). In either case, let the
factorization be t*2^m where t is odd. Without going into excruciating
detail, the length of the non-periodic portion starting with x[1] will
be at most m, and the length of the loop will be a divisor of phi(t)/2
(the Euler totient function). (The behavior of the recursion x[n+1] =
x[n]^2 is similar, except that only the factorization of p-1 is
involved.) For example, when p = 41, the loops are {-1}, {2}, {6,-7},
{14,-11,-4} and {8,-20,-12,19,-10,16}. The value x[1] = 13 has the
non-periodic portion 13, 3, 7 of length 3 before entering the {6,-7}
loop, corresponding to the factorization 41-1 = 5*2^3. The lengths of
the loops {2} and {6,-7} are factors of phi(5)/2 = 2. Similarly, the
lengths of the loops {-1}, {14,-11,-4} and {8,...,16} are factors of
phi(21)/2 = 6.
>From the point of view of factorization, these periods are much too long
to be practical. If we use x[n+1] = x[n]^2 + k, where k <> 0 and k <>
-2, then empirically the length of the loops mod p will be much smaller
than those for k = 0 or k = -2, while the length of the non-periodic
portion can easily be greater than m. For example, the recursion x[n+1]
= x[n]^2 - 6 mod 41 has three loops, {-2}, {3}, and {14,26}, and the
initial value x[1] = 0 has a non-periodic part of length 9. This is why
Pollard-rho works best for values of k other than 0 and -2.
An efficient Pollard-rho-like algorithm for factoring a Mersenne number
Mp is based on the iteration x[n+1] = x[n]^p + k. The idea is that
x[n+1] - x[n] = x[n]^p - x[n-1]^p = (x[n] - x[n-1]) * f[n], where f[n] =
(x[n]^p - x[n-1]^p) / (x[n] - x[n-1]) is known to have prime factors
which are all congruent to 1 mod p. Since Mp must also have prime
factors which are congruent to 1 mod p, this increases the chance that
gcd(x[n+1] - x[n], Mp) will produce a factor of Mp. Note that x[n+1] -
x[n] = f[n]*f[n-1]*f[n-2]*...*f[j]*(x[j] - x[j-1]), thus if any of the
terms in f[n]*f[n-1]*...*f[j] has a factor in common with Mp, this will
show up in the gcd. Ordinary Pollard-rho will also (given enough
iterations) find a factor of Mp, but the probability of this happening
within the first p-2 steps is minuscule. On the other hand, it would
cost little, after a failed LL-test, to calculate the gcd of the
difference of the last two results with Mp, just in case this happens to
reveal a factor. For that matter, one could just take the difference
between the final result and the last value stored in the p.... file.
Maybe if prime95 saved the final result in an r.... file, this test
could be performed later.
One interesting sidelight to this. The usual test for primality of a
Fermat number is to start with x[1] = 3, then calculate x[n+1] = x[n]^2
mod Fk up to x[2^k] mod Fk, which will be equal to -1 if and only if Fk
is in fact prime. Alternatively, one could start with y[1] = 3+1/3 mod
Fk (i.e., y[1] = (Fk+10)/3), then calculate y[n+1] = y[n]^2 - 2 mod Fk
up to y[2^k-1] mod Fk, which will be equal to 0 if and only if Fk is in
fact prime. This is because y[n] = x[n] + 1/x[n] mod Fk, thus y[2^k] =
(-1) + 1/(-1) = -2 mod Fk, thus y[2^k-1]^2 - 2 = y[2^k] = -2 mod Fk,
which implies y[2^k-1] = 0 mod Fk. If we calculate mod Fk(Fk+2) instead
of mod Fk, then the calculations can be carried out by prime95 with only
trivial modifications, and at the end we will have to reduce y[2^k-1]
mod Fk(Fk+2) to y[2^k-1] mod Fk to complete the test. Of course, there
are no longer any Fk within reach of current computers, so this is
merely of academic interest.
I suggested another (small) group of potential primes for testing in an
earlier message, but it never got through to the list (most likely
because my e-mail address has changed). Let F3(n) = (2^3^(n+1) - 1) /
(2^3^n - 1) = 2^(2*3^n) + 2^3^n + 1. F3(n) grows more quickly than the
Fermat numbers, so there aren't very many within reach of current
computers. There is a primality test for F3(n) which is similar to that
for Fermat numbers. 5 is a quadratic nonresidue of F3(n) for all n, thus
if F3(n) is prime, then 5^((F3(n)-1)/2) = -1 mod F3(n). On the other
hand, if 5^((F3(n)-1)/2) = -1 mod F3(n), and q is a divisor of F3(n),
then the congruence also holds mod q, which implies that q = 1 mod
2^3^n. However, since (2^3^n + 1)^2 > F3(n), it is not possible for
F3(n) to have two factors both of which are congruent to 1 mod 2^3^n,
thus if 5^((F3(n)-1)/2) = -1 mod F3(n), F3(n) must be prime. Thus, start
with x[1] = 5 and calculate x[j+1] = x[j]^2 mod 2^3^(n+1)-1 up to
x[3^n+1], then y[1] = 5*x[3^n+1] mod 2^3^(n+1)-1, then y[j+1] = y[j]^2
mod 2^3^(n+1)-1 up to y[3^n]. Reduce y[3^n] mod 2^3^(n+1)-1 to y[3^n]
mod F3(n). If the result is -1, then F3(n) is prime, otherwise F3(n) is
composite. (The idea of using 2^3^(n+1)-1 as a modulus is to be able to
take advantage of prime95's DWT code.) It's pretty unlikely that this
will find a large prime, but who knows?
Regards,
Bill
**********************************************************************
This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom
they are addressed.
This footnote also confirms that this email message has been swept by
MIMEsweeper for the presence of computer viruses.
**********************************************************************
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
