Re: Mersenne: Repeating LL remainders
[EMAIL PROTECTED] writes: We can illustrate working modulo M23 = 8388607 = 47 * 178481. 3 is a quadratic reside modulo 47 (e.g, 12^2 == 3 mod 47), so 2 + sqrt(3) is in the base field of order 47. The multiplicative order of 2 + sqrt(3) divides 47-1, and turns out to be 23. 3 is a quadratic nonresidue modulo q = 178481. The order of 2 + sqrt(3) divides q + 1 = 178482 = 2 * 3 * 151 * 197 and turns out to be 178482. The least common multiple of these orders is 2 * 3 * 23 * 151 * 197. So L(2 * 3 * 23 * 151 * 197) == L(0) mod M23. For the L sequence, we need two powers of 2 whose difference is divisible by 2 * 3 * 23 * 151 * 197. The orders of 2 modulo 3, 23, 151, 197 are 2, 11, 15, 196, respectively. The order of 2 modulo 3 * 23 * 151 * 197 is the least common multiple of these orders, namely 2^2 * 3 * 5 * 7^2 * 11 = 32340. To include a factor of 2, we need L(2^32341) == L(2^1) mod M23. That is, S(32341) == S(1) mod M23. This is far more than 23 LL steps before the sequence repeats. EXERCISE: Repeat this analysis modulo M11 = 23 * 89. Find the period modulo M29 = 233 * 1103 * 2089, after getting the individual periods for each prime factor. Yes - the result for M29 is quite interesting due to the "unexpected" short period of 60. (I feel after a week I'm not spoiling it for anyone by giving the result away...) Incidentally the first repeating remainder for _all_ the non-prime Mersenne numbers with prime exponents is S(1) = 14. I was interested to see what would happen for larger exponents, in particular if the first repeating remainder would always be 14. Unfortunately this is not true, the first repeating remainder for M37 is S(5) = S(516929). Finding this took a fair bit of CPU time as, to start with, I more or less assumed that the remainder would eventually go back to 14 (Peter's impeccable logic seemed to suggest this to my inadequate maths!) so I had to run through 2^37-1 calculations to be sure that 14 never recurred, and even then I wasn't sure I wasn't fighting a program bug. Now I have a _much_ faster way of checking, assuming that the first repeating remainder will be one of the first few in the (S) sequence. But is this true? Instinctively one feels that it ought to be, but can one construct an example where the the index n of the first repeating remainder S(n) is large compared with the period? My math is totally inadequate to investigate this... (I'm only interested in the case p prime, M(p) composite. Of course when M(p) is prime then n=p and the period is 1) Also, Peter's logic seems to depend on knowing the factors. Would it be possible to "reverse engineer" at least one of the factors of M(p) (or at least be in a much-improved position to find them) if one knew the repeat period and/or the first repeating remainder in the S sequence for M(p)? The reason I ask is that my "experimental" method of finding the period remainder does not depend on _any_ knowledge of the factorization of M(p), and I reckon I could get the values for, say, M727 with the expenditure of a great deal less computer time than completing the search to B1=44*10^6 using ECM would take. Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Repeating LL remainders
Chris Nash [EMAIL PROTECTED] wrote: Define L(n)=(2+sqrt(3))^n+(2-sqrt(3))^n. It turns out that what we usually call *the* Lucas sequence is just S(n)=L(2^n). Yes. We can check S(0) = L(1) = 4 and S(n+1) = S(n)^2 - 2 from the definitions. So S defines the familiar Lucas sequence. The whole point of the proof is to show that the set of elements a+b.sqrt(3) (a, b mod N) that form a closed group under multiplication has the maximal order, N^2-1, and thus N is prime. The Lucas sequence does this with a little jiggery-pokery, because it is sufficient to show that L(N+1) is zero, while L((N+1)/q) isn't for any prime factor q of N+1. For Mersenne numbers the only factor to worry about is 2, so the test collapses into its briefer form. So the question becomes one of solving (2+sqrt(3))^n has zero surd part, and in fact prove that the group does not have order N^2-1. The sequence L(n) "will" recur in that case. However, it is not difficult to prove that the "first" recurrence, ie the point where L(x)=L(1), will generally occur quite late in the sequence unless N has all small factors - in which case, we would have eliminated this N by trial factoring. Remember too, this is late in the "L" sequence, not in the S sequence! Suppose for instance it occurred between L(2^(n-3)) and L(2^(n-2)) - which, even assuming the "first" recurrence is equally likely anywhere, would occur with probability 50%. The S-sequence would not even see it. We can illustrate working modulo M23 = 8388607 = 47 * 178481. 3 is a quadratic reside modulo 47 (e.g, 12^2 == 3 mod 47), so 2 + sqrt(3) is in the base field of order 47. The multiplicative order of 2 + sqrt(3) divides 47-1, and turns out to be 23. 3 is a quadratic nonresidue modulo q = 178481. The order of 2 + sqrt(3) divides q + 1 = 178482 = 2 * 3 * 151 * 197 and turns out to be 178482. The least common multiple of these orders is 2 * 3 * 23 * 151 * 197. So L(2 * 3 * 23 * 151 * 197) == L(0) mod M23. For the L sequence, we need two powers of 2 whose difference is divisible by 2 * 3 * 23 * 151 * 197. The orders of 2 modulo 3, 23, 151, 197 are 2, 11, 15, 196, respectively. The order of 2 modulo 3 * 23 * 151 * 197 is the least common multiple of these orders, namely 2^2 * 3 * 5 * 7^2 * 11 = 32340. To include a factor of 2, we need L(2^32341) == L(2^1) mod M23. That is, S(32341) == S(1) mod M23. This is far more than 23 LL steps before the sequence repeats. EXERCISE: Repeat this analysis modulo M11 = 23 * 89. Find the period modulo M29 = 233 * 1103 * 2089, after getting the individual periods for each prime factor. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Repeating LL remainders
Message text written by "Brian J Beesley" I think we should check the math first. I have a sneaky suspicion that looping won't occur in the relevant region (the first 2^n-3 iterations) unless n is composite - which may be interesting, but doesn't help us eliminate Mersenne numbers as candidate primes. But my math is inadequate to prove this 8-( I think that you mean n-2 iterations, but you may be right. Yup. Brain failure again. I think I must have been confused with the idea that the sequnce _must_ recur within 2^n-3 iterations - there are only 2^n-1 different values of the residual, and 2 of them are special - see below ...I wonder if the LL sequence for a biggish MP would give a decent pseudo-random series. That is, I wonder if the series would be "better" than the usual linear-congurential series (or sum of three). Might win some support if there are still random number chasers out there. Joth Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Repeating LL remainders
Just a quick note to thank Peter for his wonderful illustration of the "repeating LL test remainders" question, with what I hope was a somewhat surprising result! That is, S(32341) == S(1) mod M23. This is far more than 23 LL steps before the sequence repeats. EXERCISE: Repeat this analysis modulo M11 = 23 * 89. Find the period modulo M29 = 233 * 1103 * 2089, after getting the individual periods for each prime factor. *smiles* I will not pre-empt the result for anyone who wants to calculate these. The important observation is to look at each factor in turn just as Peter suggests. One can almost work in reverse as well. What we see in a (Mersenne number) Lucas-Lehmer test really is a very small sample of the sequence (2+sqrt(3))^n. If a cycle were detectable from this small sample, then all the factors of the number under test must satisfy some very stringent, perhaps intractable conditions. As Brian Beesley points out, I was guilty of a lot of guesswork, and didn't go into details of the calculation of the period of the L-sequence. Hopefully Peter's excellent examples show that the chances of the L-sequence period being spotted in a much briefer S-sequence are very small indeed. Chris Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Repeating LL remainders
Best I could come up with ;-). I think that the best course of action would be to try and find numbers where the remainder actually does repeat (should any exist.) When checking, we should consider exponents were all the remainders can be saved. The size of saving all the exponent, in bits is ~n*(n-1), so keeping it 10MB, solve the quadratic eq. n^2-n-10*8*1024*1024=0, so n is ~9159. Would anyone be willing to write the code to test this? (I would, but my programing skills are less than enough, I will however loan my CPU cycles) I think we should check the math first. I have a sneaky suspicion that looping won't occur in the relevant region (the first 2^n-3 iterations) unless n is composite - which may be interesting, but doesn't help us eliminate Mersenne numbers as candidate primes. But my math is inadequate to prove this 8-( If no-one else can patch the math, then the brute force method may be indicated, though (unless we start finding loops early) we could potentially "waste" a lot of time looking for the unfindable. Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Repeating LL remainders
I don't quite see how this makes it unneccessary to check only iteration numbers which are powers of 2. How long does it take to find a cycle length of, say, 127 if you're sampling only powers of 2? Let's say you have a cycle of length 127 beginning at 992. You keep 1, 2, ... 1024. When you get to 1151, you see it's the same as 1024, and you know you have a cycle. phma Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Repeating LL remainders
all, I think we should check the math first. I have a sneaky suspicion that looping won't occur in the relevant region (the first 2^n-3 iterations) unless n is composite - which may be interesting, but doesn't help us eliminate Mersenne numbers as candidate primes. But my math is inadequate to prove this 8-( I think that you mean n-2 iterations, but you may be right. It's hard to say, without any evidence, or solid math. Just a side note, but all l_n values are 2 after n-1 iterations on a mersenne prime. Maybe lends some small bit of evidence against that... -Lucas Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Repeating LL remainders
I think we should check the math first. I have a sneaky suspicion that looping won't occur in the relevant region (the first 2^n-3 iterations) unless n is composite - which may be interesting, but doesn't help us eliminate Mersenne numbers as candidate primes. But my math is inadequate to prove this 8-( I think that you mean n-2 iterations, but you may be right. It's hard to say, without any evidence, or solid math. Think of it like this. Define L(n)=(2+sqrt(3))^n+(2-sqrt(3))^n. It turns out that what we usually call *the* Lucas sequence is just S(n)=L(2^n). The whole point of the proof is to show that the set of elements a+b.sqrt(3) (a, b mod N) that form a closed group under multiplication has the maximal order, N^2-1, and thus N is prime. The Lucas sequence does this with a little jiggery-pokery, because it is sufficient to show that L(N+1) is zero, while L((N+1)/q) isn't for any prime factor q of N+1. For Mersenne numbers the only factor to worry about is 2, so the test collapses into its briefer form. So the question becomes one of solving (2+sqrt(3))^n has zero surd part, and in fact prove that the group does not have order N^2-1. The sequence L(n) "will" recur in that case. However, it is not difficult to prove that the "first" recurrence, ie the point where L(x)=L(1), will generally occur quite late in the sequence unless N has all small factors - in which case, we would have eliminated this N by trial factoring. Remember too, this is late in the "L" sequence, not in the S sequence! Suppose for instance it occurred between L(2^(n-3)) and L(2^(n-2)) - which, even assuming the "first" recurrence is equally likely anywhere, would occur with probability 50%. The S-sequence would not even see it. In short, it doesn't matter how you buffer the S-sequence. Suppose you recorded every residue, that's n-2 steps. There are only (n-2)^2 possible differences, while in theory the recurrence length could be any of O(N) lengths. The odds of success are small, we'll call them practically non-existent. If we are testing M(10,000,000+), then we could at most get 10^14 differences, while the number is as big as 10^300. The odds of a recurrence occurring make the odds of finding a prime seem positively good! Chris Nash Lexington KY UNITED STATES === Co-discoverer of the 7th and 10th largest known primes. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Repeating LL remainders
all, A couple of weeks ago, there was discussion about repeating remainders in the LL test. There was general agreement that this would be technically unworkable due to the fact that the remainders are so large. Wouldn't it be possible to store the last 1024 binary digits of the remainder (saving 1024 of these would be only 1MB, not a big deal.) Then we could check for repeating remainders in the last 1024 iterations, without signifigantly restraining performance. If it actually repeated, it could be confirmed in double-checking quite easily. As I don't know that much about searching algorithms, I don't know how much this would hurt performance. Any thoughts? If this turns out to be workable, is it still possible to implement in V19? -Lucas Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
