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...

Modular squareroots 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 reuse the S(i) with a different modulus). A classic time vs. space tradeoff. 
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 thoughtof, many GIMPSters will try to respond in a way that helps further your understanding.

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 
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 ?

[QUOTE=ppo]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 ?[/QUOTE]
Well, that's an important discovery that I made earlier this year and have been developing ever since.... I call this "Shortcutting the LucasLehmer Test" because all you need to do is prove that the S(p3) 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 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. 
[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^(n1)[/quote]First, I'll assume you mean that the Mersenne number being tested is M = 2^n1 (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^(n1) it is possible to replace it by MS, 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^n1, it's only about twice as big as 2^(n1)  i.e., one bit longer. Squaring a 12,016,057bit number is no slower than squaring a 12,016,056bit number. (The speed jumps come at FFT size boundaries.) [quote]Can this result in speedingup 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(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 ?[/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(n3)[/i] in order to test whether S(n3) = 2^((n+1)/2) mod M. And that's exactly what the LL test already does (except that it continues one more step to compute S(n2) mod M). There's no time savings.

[QUOTE=jfollas]I call this "Shortcutting the LucasLehmer Test" because all you need to do is prove that the S(p3) term is equal to +/ 2^((p+1)/2).[/quote]... and all you need to do to calculate S(p3) is to calculate S(1), S(2), S(3), ... and so on up to S(p3)  which is exactly what the LucasLehmer test already does. So there's no shortcut!! For all but the smallest p (< a few hundred), you can't tell whether S(p3) = +/ 2^((p+1)/2) mod 2^p1 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 p4 term that will produce the value of this p3 term....[/quote]But that's not useful in speeding up the testing unless you come up with a way of calculating S(p4) mod 2^p1 that's faster than the LL 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 LL, not a speedup (the subtraction of 2 is trivial). 
All times are UTC. The time now is 20:52. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.