20021004, 09:45  #1 
Oct 2002
21_{16} Posts 
A new Mersenne conjecture: roots of LucasLehmer test.
smile
Hello, I'm working on finding a new kind of numbers related to Mersenne primes. I call them Roots of the LucasLehmer test. We all know If Mq is the qth Mersenne number (so Mq = 2^q1), then Mq is prime if and only if Sq(q2) = 0 (mod Mq). Where Sq(0) = 4 and Sq(k+1) = Sq(k)^2  2. In this test, 4 is a root of Sq=0, for any q such that Mq is prime. For a given q, many other roots do exist. But, in general, they are not root of Sq=0, for any q such that Mq is prime. I've found that 4 is not the only root of Sq=0 (for any q such that Mq is prime). Some of you may be aware that 10 is also a root of Sq=0 (for any q ...). (I don't know any proof for 10.) By means of programs, I've been able to find some new candidate roots of Sq=0 (for any q ...). Here they are all 1 4 2 10 3 52 4 724 5 970 6 10084 7 95050 8 140452 I've worked up to q=19 for finding these roots. So many other may exist. I've checked they are root of Sq=0 (for any q ...) for all the following values of q (all Mq primes) 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 I'm currently testing them with (I'm using my own Unix code for testing Lucas test, and it is very slow compared to the GIMPS program ...) 19937 21701 23209 44497 86243 Since I can't spend many time on that subject, I can't write adequate programs for efficiently finding more roots of Sq=0 (for any q ...). Is somebody interested in these numbers and willing to write some program that could find more Sq roots ? Is somebody interested in checking that the candidate roots 52 ... 140452 really are roots of all Sq such that q is prime (from q = 110503 up to 13466917) ? Some complementary results 4 = 4 (mod M3) 10 = 3 (mod M3) 52 = 3 (mod M3) 52 = 21 (mod M5) 724 = 3 (mod M3) 724 = 11 (mod M5) 724 = 89 (mod M7) 970 = 4 (mod M3) 970 = 9 (mod M5) 970 = 81 (mod M7) 10084 = 4 (mod M3) 10084 = 9 (mod M5) 10084 = 51 (mod M7) 10084 = 1893 (mod M13) 95050 = 4 (mod M3) 95050 = 4 (mod M5) 95050 = 54 (mod M7) 95050 = 4949 (mod M13) 140452 = 4 (mod M3) 140452 = 22 (mod M5) 140452 = 117 (mod M7) 140452 = 1205 (mod M13) 140452 = 9381 (mod M17) Where the numbers after the = sign are all roots of the Mq in the same line. As an example, 9381 is a root for S17=0 . 
20021009, 01:12  #2  
∂^{2}ω=0
Sep 2002
República de California
3×5^{3}×31 Posts 
Tony Reix wrote:
Quote:
The fact that there are infinitely many possible starting values for the LL test, the smallest being 4, 10, 52, ... is wellknown, although it's neat that you rediscovered this on your own. (I'll give technical details on precisely what properties the starting seeds must have in a separate post later). Note that it's not practical to use these alternate starting values for doublechecking, since for Mq composite, starting with 4 gives a different (nonzero) final residue than (say) starting with 10. However, there is a different approach that gives different intermediate data (which allows one to do valid doublechecks on the same hardware) and yet gives final residues that should be the same. It consists of shifting the "standard" LL starting value leftward by some randomly chosen number of bits s (where s < q, obviously.) If one starts with x0 = 4*2^s, then on the first iteration one must modify the standard LL recurrence as x1 = x0^2  2*2^(2*s) = 14*2^(2*s). That is, on iteration i one must subtract the 2 from the (s*2^i)th bit of the modular square. Since 2^x == 2^(x mod q) mod Mq, we simply start with our initial shift count s and then double it (mod q) on each iteration to keep track of where to subtract the 2. For example, let's do 10 LLtest iterations modulu M67, first using the initial seed x = 4 (the ?... %... is GPPARI output, but one could just as easily use unix bc or the like): [code:1] ? x=4 %146 = 4 ? b=2^671 %147 = 147573952589676412927 ? x=(x^22)%b %148 = 14 ? x=(x^22)%b %149 = 194 ? x=(x^22)%b %150 = 37634 ? x=(x^22)%b %151 = 1416317954 ? x=(x^22)%b %152 = 2005956546822746114 ? x=(x^22)%b %153 = 102405490444912989617 ? x=(x^22)%b %154 = 18156609623719939645 ? x=(x^22)%b %155 = 47311117138229729622 ? x=(x^22)%b %156 = 46721340763918645387 ? x=(x^22)%b %157 = 108817743211435641541 [/code:1] Next, we start with initial seed y = 32, which corresponds to an initial leftward shift of s = 3 bits, and again do 10 LLtest iterations. Note how we must now keep track of the shift count s, which gets doubled (modulo 67) on each iteration, and multiply the 2 that gets subtracted from the modular square on each iteration by 2^s: [code:1] ? y=32 %158 = 32 ? s=3 %159 = 3 ? s=(s+s)%67 %160 = 6 ? y=(y^22*2^s)%b %161 = 896 ? s=(s+s)%67 %162 = 12 ? y=(y^22*2^s)%b %163 = 794624 ? s=(s+s)%67 %164 = 24 ? y=(y^22*2^s)%b %165 = 631393746944 ? s=(s+s)%67 %166 = 48 ? y=(y^22*2^s)%b %167 = 60817172317964601997 ? s=(s+s)%67 %168 = 29 ? y=(y^22*2^s)%b %169 = 59809955896328411739 ? s=(s+s)%67 %170 = 58 ? y=(y^22*2^s)%b %171 = 125003763597216405834 ? s=(s+s)%67 %172 = 49 ? y=(y^22*2^s)%b %173 = 2052021842189766865 ? s=(s+s)%67 %174 = 31 ? y=(y^22*2^s)%b %175 = 140911453820202593701 ? s=(s+s)%67 %176 = 62 ? y=(y^22*2^s)%b %177 = 52188588101573724612 ? s=(s+s)%67 %178 = 57 ? y=(y^22*2^s)%b %179 = 102283935673136730866 [/code:1] Superficially, the two 10iteration residues look nothing like each other, but if we write them in binary form: [code:1] 108817743211435641541 = 1011110011000100110010010001110100011100001010010111100101011000101 102283935673136730866 = 1011000101101111001100010011001001000111010001110000101001011110010 [/code:1] we see that leftwardcircularshifting the first by 57 bits (or equivalently, rightwardshifting it by 6757 = 10 bits) gives the second. The final LL residue obtained this way will similarly be a bitwise circular shift of the traditional LL residue. Prime95 already uses such a scheme (note that a flawed early implementation thereof was responsible for the infamous "Version 17 bug" in that program, which wiped out several thousand LL test results in the Spring of 1999  don't know if you were with the project at that time). I haven't implemented it in Mlucas yet (partly because the program is used for a small enough fraction of GIMPS tests that the likelihood of it being used for both the first test and doublecheck of an exponent is less than 1%), and it seemed like it was going to be painful to do the first time I seriously thought about it a couple of years ago. This is mainly because of the way mlucas does the carry propagation step of the modular squaring, which is different than the way Prime95 does it. But, in thinking about it some more, I think it may not be so hard after all  a few relatively simple preprocessing steps should be sufficient. Let me think about it a bit more and I'll let you know how long it might take me to implement. In the meantime, you shouldn't hesitate to use Mlucas for DC'ing, simply because ~99% of the exponents will have been firsttime tested by Prime95. 

20021009, 15:16  #3 
Oct 2002
3·11 Posts 
So it's already known.
Prime95 gave the following link
http//www.mailarchive.com/mersenne@base.com/msg00739.html > In the LL test, we start with S(1) = 4. The Prime Page says we can use S(1) = > 10 and certain other values depending on p. Can anyone clarify this? "For starting values we can use 4, 52, 724, ..., U{n}, ..., where U{n} =14 U{n1}  u{n2} and 10, 970, 95050, ..., V{n}, ..., where V{n} = 98V{n1}  V{n2}. Also there are 2^(p2) starting values that depend upon p. For example to test 2^51 we could use the starting values 4, 9, 10, 11, 20, 21, 22, or 27." 
20021014, 21:51  #4  
∂^{2}ω=0
Sep 2002
República de California
2D69_{16} Posts 
Note: this is a continuation of a discussion started within Tony Reix's "Goldbach Conjecture..." thread. I moved it over to this thread since it more logically belongs here. Quote:
one of my Alphas, and at the same time I was in contact with Paul Zimmerman re. the largeinteger multiply algorithms used by GMPECM, and using timings for the same cofactor as an example. He fired up a few curves on one of his machines, and a few minutes later reported the 25digit factor you also found, and the probableprime cofactor.) (I'm planning on proposing these sequences as a nice factoring challenge in a mail to Zimmerman, Montgomery, Crandall and some others  Peter M. has long been interested in factorizations of regular Lucas sequences, so this is close to his normal stomping grounds, but I think of some considerable interest by itself). Here are some morecomplete data (*= indicates an Sterm divide by a Mersenne prime): [code:1] S0 [4] = 2.2 S1 [4] *= 2.7 S2 [4] = 2.97 S3 [4] *= 2.31.607 S4 [4] = 2.708158977 S5 [4] *= 2.127.7897466719774591 S6 [4] = 2.22783.265471.592897.2543310079.220600496383 S7 [4] = 2.113210499946729046527.71510428488234435849323250891975205208728978040847871 S8 [4] = 2.12289.665972737.3867637345756894712411491994657791.PRP100 S9 [4] = 2.1049179854847.27293256153178849431531258375109421840383.C241 S10[4] = 2.C586 S11[4] *= 2.8191.4194619596652733275824127.PRP1143 ... [/code:1] Here are the first few of the S0 = 10 sequence: [code:1] S1 [10] *= 2.7.7 S2 [10] = 2.4801 S3 [10] *= 2.31.1487071 S4 [10] = 2.52609.80789839489 S5 [10] *= 2.127.769.36810112513.10050007226929279 S6 [10] = 2.1279.212542494659839.9603749795193112055306105436352550778712005121 S7 [10] = 2.3583.55782066825217.45896243081785568814275071.PRP85 S8 [10] = 2.5119.64419841.128905150832968536864331777.C217 S9 [10] = 2.51199.10162177.C498 S10[10] = 2.4906458295537663.184023456784189587457.C984 S11[10] *= 2.8191.116184333317857001473.C2015 ... [/code:1] Quote:
4, 52, 724, ..., U{n}, ..., where U{n} =14 U{n1}  u{n2} and 10, 970, 95050, ..., V{n}, ..., where V{n} = 98V{n1}  V{n2}, where we define U1 = U0 = 4 and V1 = V0 = 10. (I'm only interested in the starting values that work for *any* Mersenne prime, not the additional ones that give an S_(p2) that has M(p) as a factor, for some particular p only, by mere happenstance.) Thus we have [code:1] S0 [52] = S0[4].13 S1 [52] *= S1[4].193 S2 [52] = S2[4].37633 S3 [52] *= S3[4].1416317953 S4 [52] = S4[4].769.314113.8304419329 S5 [52] *= S5[4].81409.49427725039504674210783029592577 S6 [52] = S6[4].310273.1674378241.31166535458340592006672641989850047959301818960703585863681 S7 [52] = S7[4].15361.C143 S8 [52] = S8[4].31252623361.261536198433160793898188046337.26315739764268897985597215805161179137.C216 S9 [52] = S9[4].3305473.3536560129.11590564601857.C557 S10[52] = S10[4].270337.21386688145268737.C1150 S11[52] *= S11[4].C2343 ... [/code:1] For the starting value V2 = 970, we have [code:1] S1 [970]*= S1[10].9601 S2 [970] = S2[10].92198401 S3 [970]*= S3[10].193.3457.12740606401 S4 [970] = S4[10].7998337.178600862593.50583668732161 S5 [970]*= S5[10].453889.6326017.1818474177246611367987147117589497752930980982885377 S6 [970] = S6[10].103356618801671002199041.PRP105 S7 [970] = S7[10].147457.23789569.5161326615565677037332776796681217.C209 S8 [970] = S8[10].132408306782587129755649.PRP487 S9 [970] = S9[10].12289.285922099201.2203263382290433.2369699936274268446721.C968 S10[970] =S10[10].356671489.389603329.883184938795009.C2007 S11[970]*=S11[10].209436673.788299777.11484601836158977.C4045 ... [/code:1] Similarly, we have that S_j[4] divides S_j[724] (and so on), and that S_j[10] divides S_j[970] and so on. When we divide out this "primitive part" of any S_j[U,V{n}] it keeps the remaining cofactor from growing too large with increasing starting values of the LL sequence, which is desirable for a sequence that is to be used as a benchmark factoring challenge. That is, even though for a given starting value the Sterms get large very quickly, for any index j we have a decent number of nottoohuge numbers to factor, e.g. S_j[U1], S_j[U2]/S_j[U1], etc. Now, I don't believe there is any correlation between factors of these and Mersenne prime exponents  607 and 1279 appear as factors for a different reason, which follows from the first of the following claims, which I leave to the interested readers to prove for themselves. Define: For the (j)th term of the sequence with starting value S_0 (where S_0 = U{n} or V{n}), call S_j[U,V{1}] the primitive part of S_j[S_0] and call S_j[S_0]/S_j[U,V{1}] the nonprimitive part. (E.g. S1[970] has primitive part = S1[10] and nonprimitive part = 9601.) Then, (1) For any of the aforementioned starting values of the sequence and n > 2, odd factors of S_(n2) have one of the two forms given by q = k*2^n + 1. Corollary: The smallest possible odd factor of S_(n2) is q = 2^n1, and this minimum is achieved when q is (by definition) a Mersenne prime. (I'd long wondered about the possibility of odd factors of S_(n2) smaller than 2^n1, and this neatly rules that possibility out). Clearly, if this minimum factor occurs, it must divide the primitive part of S_(n2). In addition, there appear to be further restrictions on the factors, depending on which term in either of the starting sequences one uses for the LL sequence. The following rules appear to hold: For S_0 = U2 (52) or V2 (970): Factors of the nonprimitive part must == +1 modulo 2^n, and have k == 0 modulo 2*3. For S_0 = U3 (724) or V3 (95050): All factors of the nonprimitive part of form p = k.2^n + 1 have k == 0 mod 2*3*5; All factors of the nonprimitive part of form p = k.2^n  1 have k == 0 mod 5; For S_0 = U4 (10084) or V4 (9313930): All factors of the nonprimitive part of form p = k.2^n + 1 have k == 0 mod 2*3*7; All factors of the nonprimitive part of form p = k.2^n  1 have k == 0 mod 7; The one exception is that S1[10084] has the factor 7 in both its primitive part (as expected) and its nonprimitive part (which violates the second of the above, i.e. this repeated factor is of p = k.2^n  1 with k = 1, which is not a multiple of 7). Other Notes: In addition to the fact that S_j[U_(k1)]  S_j[U_k] (similarly for the Vsequence of starting values), we have that S_j[U_k] = S_j[U_(k1)]*{ S_(j+1)[U_(k1)]  1 } . (For example, S3[52] = S3[4].1416317953 = S3[4]*{ S4[4]  1 }. ) Note, however, that this identity does not make trivial the problem of factoring the nonprimitive part S_j[U_k]/S_j[U_(k1)], since e.g. if S_(j+1)[U_(k1)] factors as 2*q1*q2*...*qk, in order to factor we still have to factor S_j[U_k]/S_j[U_(k1)] = 2*q1*q2*...*qk  1. This is fun, Ernst 

20021018, 11:32  #5  
Sep 2002
Vienna, Austria
DB_{16} Posts 
Quote:
S_j[U_k]=(2+sqrt(3))^(2^j*(2k+1))+(2sqrt(3))^(2^j*(2k+1)) and S_j[V_k]=(5+2sqrt(6))^(2^j*(2k+1))+(52sqrt(6))^(2^j*(2k+1)) 

20040606, 05:02  #6 
Einyen
Dec 2003
Denmark
2^{2}·13·59 Posts 
This is a 1.5 year old thread. Did you ever take this work any further?

20040607, 15:30  #7  
∂^{2}ω=0
Sep 2002
República de California
26551_{8} Posts 
Quote:


20040721, 17:45  #8 
Jul 2004
2·7 Posts 
I apologize if this is repeated information, but I haven't specifically seen it posted anywhere.
I did some studying of the "roots of LLT", specifically around Sloane's A018844: http://www.research.att.com/cgibin/...i?Anum=A018844 Sequence 1: A(1)=4, A(2)=52, A(N)=14*A(N1)A(N2) Sequence 2: A(1)=10, A(2)=970, A(N)=98*A(N1)A(N2) Even though Sloane's A018844 is defined as the union of two different sequences, I have found that only Sequence 1 appears to be necessary in order to generate the set of numbers that are valid starting terms of a LLT. Specifically, when you take Sequence 1 modulo Mersenne Mp, it will be cyclical in nature about the period 2^(P1) and symmetrical within the cycle about the period 2^(P2) iff Mp is prime (otherwise the periods are shorter). Sequence 2 above will occur naturally as part of Sequence 1 modulo Mp. So, any resulting term of Sequence 1 modulo Mp can be used as the starting term of a LucasLehmer Test for prime Mp and the P2 term will be zero. Last fiddled with by jfollas on 20040721 at 17:56 
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 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
Lucas Lehmer test question?  BMgf  Programming  23  20031209 08:52 
about LucasLehmer test and Prime 95  Annunaki  Math  22  20030805 21:52 