20040716, 03:09  #1 
Jun 2004
Chicago
2^{2}×7 Posts 
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...

20040717, 02:08  #2 
Aug 2002
2^{6}·5 Posts 
Modular squareroots do not necessarily yield just one possible number.

20040717, 03:18  #3 
"Richard B. Woods"
Aug 2002
Wisconsin USA
17014_{8} Posts 
(*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 reuse the S(i) with a different modulus). A classic time vs. space tradeoff. 
20040717, 14:38  #4 
Jun 2004
Chicago
1C_{16} Posts 
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.

20040719, 15:24  #5 
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
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 thoughtof, many GIMPSters will try to respond in a way that helps further your understanding.

20040818, 13:25  #6 
Aug 2004
italy
113 Posts 
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^(n1) it is possible to replace it by MS, 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 speedingup the test, or it is something already considered ?
ppo 
20040818, 13:49  #7 
Aug 2004
italy
113 Posts 
one interesting thing is that if we do like I suggested in my previous post, S(n3) 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 20040818 at 13:50 
20040818, 15:45  #8  
Jul 2004
1110_{2} Posts 
Quote:
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 LucasLehmer 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 LucasLehmer sequence modulo 2^p  1 *may* result in a term of "zero" at some iteration prior to p2 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 LucasLehmer 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 p2 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 p2'th iteration for Mersenne prime Mp are found in Sloane's A018844: A[0]=4, A[1]=52, An=(14*A[n1])  A[n2] (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 p3 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 p2 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 p4 term that will produce the value of this p3 term.... In other words: T^2 = 2^((p+1)/2) + x*Mp + 2 [T is the p4 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 nonprime Mp's. In this case, undefined means not +/ 1). The Legendre symbol [C\M] is calculated as: C^((M1)/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^((p1)/2). Ok, so if Mp is prime, then the modular inverse will actually be the same as Cp^(((Mp1)/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^(p1))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. 

20050920, 00:30  #9  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
Quote:
Quote:
Quote:


20050920, 00:41  #10  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:


20050920, 01:10  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Quote:
Quote:


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  20180311 23:20 
maximum theoretical speed of LL test w/o bandwidth limitations?  ixfd64  Hardware  30  20120305 06:16 
Different Speed in different OS's  Dubslow  Software  11  20110802 00:04 
TF speed  Unregistered  Information & Answers  10  20110727 12:34 
what speed should I be seeing for my PII266MHz?  there_is_no_spoon  Hardware  1  20040407 20:50 