 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   LL test speed up? (https://www.mersenneforum.org/showthread.php?t=2783)

 jebeagles 2004-07-16 03:09

LL test speed up?

I'm just curious if anyone has thought about backtracking from the end of a LL, and then going back to S(1) = 4, if S(1) != 4 from this backtrack, then we know that if the number is not prime. Possibly breaking a number into two parts, and then seeing if the two LL numbers are equal or not. etc...

 ColdFury 2004-07-17 02:08

Modular square-roots do not necessarily yield just one possible number.

(*sigh*) If we try to save the full, unmodded values of the S(i) so that we could backtrack as you suggest (or, in another attempted speedup, just perform the mods with different modulus), we will find that after just a small number (less than 1000) of iterations, the S(i) values become so large that the entire known universe is not large enough to store them. (Exercise: Calculate the number of digits in S(1000) if no mod is performed at each step. Compare that to the number of particles in the known universe!)

But when we perform the modulos to keep the S(i) sizes manageable, we lose information necessary to correctly backtrack (or to re-use the S(i) with a different modulus).

A classic time vs. space tradeoff.

 jebeagles 2004-07-17 14:38

It was just a random idea I had, no idea what would be entailed, and I figured that more would go into it then I thought, but oh well.

Oh, please continue coming up with those "random" ideas! Your next one could be something novel that [i]will[/i] work. Many improvements that have been incorporated in our search have been ideas that no one thought of before. And even when a suggestion turns out to have been already thought-of, many GIMPSters will try to respond in a way that helps further your understanding.

 ppo 2004-08-18 13:25

another random idea

if S is the generic term of the LL sequence and M is the Mersenne number to be tested, when S is bigger than 2^(n-1) it is possible to replace it by M-S, so reducing the size of the numer to be squared.(this is equivalent to using the simmetrical definition of modulus and ignoring the negative sign, since we have to square it) Can this result in speeding-up the test, or it is something already considered ?

ppo

 ppo 2004-08-18 13:49

one interesting thing is that if we do like I suggested in my previous post, S(n-3) seems to be always equal to 2^((n+1)/2), when M is prime. ( I have only tested with some small values of n). Someone has a proof for that ?

 jfollas 2004-08-18 15:45

[QUOTE=ppo]one interesting thing is that if we do like I suggested in my previous post, S(n-3) seems to be always equal to 2^((n+1)/2), when M is prime. ( I have only tested with some small values of n). Someone has a proof for that ?[/QUOTE]
Well, that's an important discovery that I made earlier this year and have been developing ever since.... I call this "Shortcutting the Lucas-Lehmer Test" because all you need to do is prove that the S(p-3) term is equal to +/- 2^((p+1)/2).

I was preparing a paper on the subject, but I'll provide some details of my research here (since the cat's already out of the bag :smile: )...

In my paper, I set up 3 Lemmas:

LEMMA 1: Mersenne Primes are the only number whose Lucas-Lehmer modulo sequence will result in a term of "zero" after some arbitrary number of iterations.

LEMMA 2: Using a starting value other than "4" for the Lucas-Lehmer sequence modulo 2^p - 1 *may* result in a term of "zero" at some iteration prior to p-2 for Mersenne Prime 2^p - 1. However, a different starting term may also result in no "zero" term after any number of iterations.

LEMMA 3: For any Mersenne Prime Mp, the Lucas-Lehmer sequence modulo that prime will have a term of +/- 2^((P+1)/2) just prior to the term of "zero".

Lemma 1 was a conclusion that I came to based on a lack of contradiction.

Lemma 2 comes from the simple notion that if you start with any actual intermediate term of a LL sequence modulo a Mersenne prime, then you will still get zero, only it will be less than p-2 iterations. But not all numbers < Mp are actual intermediate terms.

When combined, Lemmas 1 and 2 imply that regardless of the starting term, if a LL sequence modulo a Mersenne number yields a "zero" term after some number of iterations > 1, then that Mersenne number is prime. (proof?)

Acceptable starting terms that will produce "zero" terms on the p-2'th iteration for Mersenne prime Mp are found in Sloane's A018844:

A=4, A=52, An=(14*A[n-1]) - A[n-2] (mod Mp)

To date, I have not found a contradiction to my Lemma 1 for Mersenne composites using any starting term (with the exception noted below).

So, why does Lemma 3 (the p-3 term) work? Well, simply put, it satisfies the LL Primality test because if you square it, and then subtract 2, you left with 0 (mod Mp), which is the expected result for the p-2 term modulo prime Mp.

(2^((P+1)/2) ^ 2) - 2
= 2^(P+1) -2
= 2*(2^P - 1)
= 2*Mp
= 0 (mod Mp)

Note also that it's not sufficient to just start the LL sequence with 2^((P+1)/2) because it will produce a zero term after only one iteration for all values of P.

So, if the LL sequence must have this special term in order for Mp to be prime, then all we need to do is try to prove that there will be a natural p-4 term that will produce the value of this p-3 term.... In other words:

T^2 = 2^((p+1)/2) + x*Mp + 2 [T is the p-4 term]

or

T^2 = 2^((p+1)/2) + 2 (mod Mp)

This is the same thing as proving that 2^((p+1)/2) + 2 is a quadratic residue modulo Mp. (I'm going to refer to 2^((p+1)/2) + 2 as "Cp" for the rest of this post....)

Proving that a number is a quadratic residue involves calculating the Legendre Symbol (which will be +1 if it is a QR, -1 if it is not a QR, and undefined for non-prime Mp's. In this case, undefined means not +/- 1).

The Legendre symbol [C\M] is calculated as:

C^((M-1)/2)

Example: [130\8191] = 130^4095 (= +1, meaning that 130 is a QR of 8191)

What I've spent most of my time on over the last several months is trying to optimize the proving/disproving of whether the "Cp" is a quadratic residue of Mp.

One method that I came up with is similar to the LL test in that it involves repeated squaring, and then checking the results. It's similar to LL in that you square the proceeding term, but different because you don't need to subtract 2 with each iteration.

Using the 130\8191 example above, and without going into too much background, it is easy to see that 130^4096 would have to be equal to "130" if 130 is a QR of 8191. Since 4096 is a power of 2, this means that we would only have to repeatedly modular square 130 a total of 12 times, and then see if the result is equal to "130". If so, then we proved Mp to be prime, else it is composite.

I was working on another method that didn't turn out to be very efficient, but it needed to calculate the modular (multiplicative) inverse of "Cp". This is actually very trivial, because the resulting number in binary will have "p" bits with the high order bits set to 1 and the low order bits set to 0 (with the division being half way, giving the larger half to the 1's). I know I didn't describe that well, so here's the example:

8191 = 2^13 - 1 (P=13)

130^-1 (mod 8191) = 1111111000000 (7 1's and 6 0's)
=8128

This is also 8192 - 64. So, as a generalization, the modular inverse of "Cp" term is 2^p - 2^((p-1)/2).

Ok, so if Mp is prime, then the modular inverse will actually be the same as Cp^(((Mp-1)/2)-1). Or, in the 8191 example, this is 130^4094. Proving this fact is where I started to go, but I abandoned this idea because I could not find an improvement in efficiency.

It is important to note that even Mersenne composites will have the same format of modular inverse of Cp. But, the cyclical period is shorter (based on the factors of Mp), so Cp^((2^(p-1))-2) will not be equal to the modular inverse of Cp.

Hopefully this research will spark new ideas for efficient ways to shortcut the LL sequence. It's been pretty fun for me working on it alone, but I welcome others to improve on my work.

[QUOTE=ppo]if S is the generic term of the LL sequence and M is the Mersenne number to be tested, when S is bigger than 2^(n-1)[/quote]First, I'll assume you mean that the Mersenne number being tested is M = 2^n-1 (so n is the exponent of 2 for that number), and that by "S" you mean one of the S(i) terms [i]mod M[/i].

[QUOTE]when S is bigger than 2^(n-1) it is possible to replace it by M-S, so reducing the size of the numer to be squared.[/quote]But this reduction in size is trivial. When S(i) is just below 2^n-1, it's only about twice as big as 2^(n-1) -- i.e., one bit longer. Squaring a 12,016,057-bit number is no slower than squaring a 12,016,056-bit number. (The speed jumps come at FFT size boundaries.)

[quote]Can this result in speeding-up the test, or it is something already considered?[/QUOTE]1) no (well, it could if you could use a smaller FFT by reducing one bit, but that would happen too rarely to be worth the time needed to program the change), and 2) yes.

[QUOTE=ppo]one interesting thing is that if we do like I suggested in my previous post, S(n-3) seems to be always equal to 2^((n+1)/2), when M is prime. ( I have only tested with some small values of n). Someone has a proof for that ?[/QUOTE]Suppose it's true. It wouldn't speed up anything, because [i]one still has to compute all the S(i) mod M values leading up to S(n-3)[/i] in order to test whether S(n-3) = 2^((n+1)/2) mod M. And that's exactly what the L-L test already does (except that it continues one more step to compute S(n-2) mod M). There's no time savings.

[QUOTE=jfollas]I call this "Shortcutting the Lucas-Lehmer Test" because all you need to do is prove that the S(p-3) term is equal to +/- 2^((p+1)/2).[/quote]... and all you need to do to calculate S(p-3) is to calculate S(1), S(2), S(3), ... and so on up to S(p-3) --- which is exactly what the Lucas-Lehmer test already does. So there's no shortcut!! For all but the smallest p (< a few hundred), you can't tell whether S(p-3) = +/- 2^((p+1)/2) mod 2^p-1 unless you perform all the previous S(i) calculations.

[quote]So, if the LL sequence must have this special term in order for Mp to be prime, then all we need to do is try to prove that there will be a natural p-4 term that will produce the value of this p-3 term....[/quote]But that's not useful in speeding up the testing unless you come up with a way of calculating S(p-4) mod 2^p-1 that's faster than the L-L sequence, is it?

[quote]One method that I came up with is similar to the LL test in that it involves repeated squaring, and then checking the results. It's similar to LL in that you square the proceeding term, but different because you don't need to subtract 2 with each iteration.

Using the 130\8191 example above, and without going into too much background, it is easy to see that 130^4096 would have to be equal to "130" if 130 is a QR of 8191. Since 4096 is a power of 2, this means that we would only have to repeatedly modular square 130 a total of 12 times, and then see if the result is equal to "130". If so, then we proved Mp to be prime, else it is composite.[/QUOTE]So it's computationally equivalent to L-L, not a speedup (the subtraction of 2 is trivial).

All times are UTC. The time now is 20:52.