Re: Mersenne: LL and Pollard-rho in one?
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
Re: Mersenne: LL and Pollard-rho in one?
Alexander Kruppa [EMAIL PROTECTED] observes:
Hi,
the Lucas-Lehmer iteration
L_0 = 4
L_{n+1} = L_n ^2 -2
looks suspiciously like an iteration used in Pollard-Rho:
x_0 = a
x_{n+1} = x_n ^2 +b
Can this be used to do a LL test and Pollard-rho factoring attempt at
once?
I remember faintly having read something that b=-2 is not a good choice
for Pollard-rho, but I don't remember any explanation why.. would it
work here?
If L_0 = alpha + 1/alpha (where alpha = 2 + sqrt(3) is found
by solving a quadratic) then
L_n = alpha^(2^n) + alpha^(-2^n)
L_m - L_n = alpha^(2^m) + alpha^(-2^m) - alpha^(2^n) - alpha^(-2^n)
= (alpha^(2^m) - alpha^(2^n)) + (1 - alpha^(-2^m - 2^n))
If p is a factor of the number we are trying to factor, then
the order of alpha will divide one of p+1 and p-1
(depending upon whether alpha is in the base field GF(p)
or the extension field GF(p^2)).
The size of this order will be O(p).
m and n will usually need to have size O(p) before we achieve
alpha^(2^m) == alpha^(+- 2^n) (mod p)
(which is the same as 2^m == +- 2^n (mod (order of alpha)) ).
When b 0, -2, we know no such formula for the iterates of Pollard
Rho. x - x^2 + b (mod p) seems to behave like a pseudorandom function
modulo p, and Pollard Rho takes O(sqrt(p)) iterations rather than O(p).
For Lucas-Lehmer, when p = 2^q - 1 is a Mersenne prime, p+1 is
divisible by a very high :-) power of 2. The L_n values collapse to
0, -2, 2, 2, ... as alpha^(2^n) becomes sqrt(-1), -1, 1 in GF(p^2).
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: LL and Pollard-rho in one?
but doing the Pollard-Rho along a LL test would not be particularly efficient, anyways. Or particularly successful. Remember Pollard-rho heuristically expects to find a factor p in something along the lines of sqrt(p) iterations. Since we're doing lets call it 10^7 iterations, you'd probably be better off trial-factoring to 10^14 - which is already done and beyond with guarantees no factor is missed. You might get a lucky factor that's larger, but experience (and the law of averages) tells you you aren't going to be *that* lucky. For every 2 LL iterations, you'd have to do another one for the cycle find algorithm and a multiply to store up any factor you find. Thats 9 transforms instead of 4 Brent's modification of Pollard-rho doesn't require storing the two parallel sequences x_n and x_2n. Instead consider x_n-x_k, where k is the greatest power of 2 that's less than n. At worst it could take twice as long to find a cycle, but it's at least twice as fast. And Pollard-Rho is probably not very well suited for finding Mersenne factors as it cannot exploit the fact that these factor are 1 mod (2p) as P-1 can. The extra exponentiation at the start of the P-1 algorithm is hardly a great exploitation. Note that 'rho' definition of Pollard-rho just means that your iteration function should be (pseudo)random - you can create a pseudorandom iteration that does exploit the form of factors. Of course, that's no longer an LL iteration though. I'm mostly asking for curiosity, whether the LL iteration really makes a proper Pollard-Rho iteration, especially with the -2. The classic Pollard-rho iteration x - x^2+a isn't particularly good with a=0 or a=-2. The reason is the way the cycles degenerate. You want one of the cycles mod some unknown prime factor to be short. What you don't want is all the cycles to collapse at the same time... or never collapse at all. Suppose you applied the same Pollard-rho iteration simultaneously to all (or at least many) possible initial points mod N (this is a reportedly near-perfect parallelization according to a paper by Dick Crandall). Why Crandall's parallelization works is that its inevitable that the application of the iteration reduces the number of distinct points on each pass until eventually your N initial points are folded down to quite short and detectable cycle lengths. However, iterate with 0 and -2 and there are some obvious fixed points (solve the quadratic!) and other, less obvious, short cycles. In effect, there are some points you can't iterate away no matter how long you keep trying. There's a good visual indicator that 0 and -2 aren't particularly good. z - z^2+c is the Julia set iteration on the complex plane. Let's assume for the moment that somehow the behavior of the Pollard-rho iteration mod N and the behavior of the Mandelbrot iteration on C are equivalent - they are, but the mapping between them is hardly trivial. The Julia sets for c=0 and c=-2 are devastatingly boring, their iteration brings you no surprises, no pretty pictures. In much the same way you're not going to get any exciting factors with this iteration mod N, either. In Lucas-Lehmer terms, what happens during the LL / Pollard-rho iteration is that all the prime factors of the number have interlocked cycle lengths. That's great for primality proving (because if you get the expected final residue, you know something about *all* prime factors of your number - and hence conclude there can be only one). But a failed LL test simply tells you you now know *all* prime factors of your number failed identically. There's nothing in the LL recipe that distinguishes any one prime factor from any other. Chris Nash Lexington KY UNITED STATES _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
