mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2004-07-16, 03:09   #1
jebeagles
 
jebeagles's Avatar
 
Jun 2004
Chicago

22·7 Posts
Default 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...
jebeagles is offline   Reply With Quote
Old 2004-07-17, 02:08   #2
ColdFury
 
ColdFury's Avatar
 
Aug 2002

32010 Posts
Default

Modular square-roots do not necessarily yield just one possible number.
ColdFury is offline   Reply With Quote
Old 2004-07-17, 03:18   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

160248 Posts
Default

(*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.
cheesehead is offline   Reply With Quote
Old 2004-07-17, 14:38   #4
jebeagles
 
jebeagles's Avatar
 
Jun 2004
Chicago

22·7 Posts
Default

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.
jebeagles is offline   Reply With Quote
Old 2004-07-19, 15:24   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

Oh, please continue coming up with those "random" ideas! Your next one could be something novel that will 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.
cheesehead is offline   Reply With Quote
Old 2004-08-18, 13:25   #6
ppo
 
ppo's Avatar
 
Aug 2004
italy

113 Posts
Default 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 is offline   Reply With Quote
Old 2004-08-18, 13:49   #7
ppo
 
ppo's Avatar
 
Aug 2004
italy

1618 Posts
Default

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 ?

Last fiddled with by ppo on 2004-08-18 at 13:50
ppo is offline   Reply With Quote
Old 2004-08-18, 15:45   #8
jfollas
 
Jul 2004

11102 Posts
Default

Quote:
Originally Posted by 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 ?
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 )...

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[0]=4, A[1]=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.
jfollas is offline   Reply With Quote
Old 2005-09-20, 00:30   #9
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

Quote:
Originally Posted by 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)
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 mod M.

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.
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?
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.
cheesehead is offline   Reply With Quote
Old 2005-09-20, 00:41   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1C1416 Posts
Default

Quote:
Originally Posted by 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 ?
Suppose it's true. It wouldn't speed up anything, because one still has to compute all the S(i) mod M values leading up to S(n-3) 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.
cheesehead is offline   Reply With Quote
Old 2005-09-20, 01:10   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

Quote:
Originally Posted by 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).
... 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....
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.
So it's computationally equivalent to L-L, not a speedup (the subtraction of 2 is trivial).
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
maximum theoretical speed of LL test w/o bandwidth limitations? ixfd64 Hardware 30 2012-03-05 06:16
Different Speed in different OS's Dubslow Software 11 2011-08-02 00:04
TF speed Unregistered Information & Answers 10 2011-07-27 12:34
what speed should I be seeing for my PII266MHz? there_is_no_spoon Hardware 1 2004-04-07 20:50

All times are UTC. The time now is 12:17.

Sat Oct 24 12:17:07 UTC 2020 up 44 days, 9:28, 0 users, load averages: 1.73, 1.63, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.