A new Mersenne conjecture: roots of Lucas-Lehmer test.

[Tony Reix]

smile
Hello, I'm working on finding a new kind of numbers related to Mersenne primes.
I call them Roots of the Lucas-Lehmer test.

We all know
If Mq is the qth Mersenne number (so Mq = 2^q-1), then Mq is prime if and only if Sq(q-2) = 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 .

[ewmayer]

Tony Reix wrote:

The Lucas-Lehmer test starts from 4 .
I have a conjecture saying that the Lucas-Lehmer test works fine with
other numbers, like:
10 52 724 970 10084 95050 140452
I call them roots of Lucas-Lehmer test. I've proven that's true up
to q=86243 with my own (slow!) Lucas-Lehmer code.

I'd like to know if it possible to modify the Mlucas code so that it
starts with a number different than 4. And how.
This way I could check the numbers up to the last Mersenne prime.

Hi, Tony:

The fact that there are infinitely many possible starting values
for the LL test, the smallest being 4, 10, 52, ... is well-known,
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 double-checking, 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 double-checks 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 LL-test iterations modulu M67, first using
the initial seed x = 4 (the ?... %... is GP-PARI output, but one
could just as easily use unix bc or the like):

[code:1]
? x=4
%146 = 4
? b=2^67-1
%147 = 147573952589676412927
? x=(x^2-2)%b
%148 = 14
? x=(x^2-2)%b
%149 = 194
? x=(x^2-2)%b
%150 = 37634
? x=(x^2-2)%b
%151 = 1416317954
? x=(x^2-2)%b
%152 = 2005956546822746114
? x=(x^2-2)%b
%153 = 102405490444912989617
? x=(x^2-2)%b
%154 = 18156609623719939645
? x=(x^2-2)%b
%155 = 47311117138229729622
? x=(x^2-2)%b
%156 = 46721340763918645387
? x=(x^2-2)%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 LL-test
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^2-2*2^s)%b
%161 = 896
? s=(s+s)%67
%162 = 12
? y=(y^2-2*2^s)%b
%163 = 794624
? s=(s+s)%67
%164 = 24
? y=(y^2-2*2^s)%b
%165 = 631393746944
? s=(s+s)%67
%166 = 48
? y=(y^2-2*2^s)%b
%167 = 60817172317964601997
? s=(s+s)%67
%168 = 29
? y=(y^2-2*2^s)%b
%169 = 59809955896328411739
? s=(s+s)%67
%170 = 58
? y=(y^2-2*2^s)%b
%171 = 125003763597216405834
? s=(s+s)%67
%172 = 49
? y=(y^2-2*2^s)%b
%173 = 2052021842189766865
? s=(s+s)%67
%174 = 31
? y=(y^2-2*2^s)%b
%175 = 140911453820202593701
? s=(s+s)%67
%176 = 62
? y=(y^2-2*2^s)%b
%177 = 52188588101573724612
? s=(s+s)%67
%178 = 57
? y=(y^2-2*2^s)%b
%179 = 102283935673136730866
[/code:1]

Superficially, the two 10-iteration 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 leftward-circular-shifting the first by 57 bits (or equivalently,
rightward-shifting it by 67-57 = 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 double-check 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 first-time-
tested by Prime95.

[Tony Reix]

Prime95 gave the following link

http//www.mail-archive.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{n-1} - u{n-2} and 10, 970, 95050, ..., V{n}, ..., where V{n} = 98V{n-1} - V{n-2}. Also there are 2^(p-2) starting values that depend upon p. For example to test 2^5-1 we could use the starting values 4, 9, 10, 11, 20, 21, 22, or 27."

[ewmayer]

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.

Originally Posted by akruppa

I just found this factorization with GMP-ECM:

s_0 = 4
s_11 = 2 * 8191 * 4194619596652733275824127 * prp1143

I haven't tried to find any factors of M(4194619596652733275824127) or M(prp1143), though.

Yep, I just found this one last Friday myself (actually, it was running on
one of my Alphas, and at the same time I was in contact with Paul
Zimmerman re. the large-integer multiply algorithms used by GMP-ECM,
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 25-digit factor you also found, and the probable-prime 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 more-complete data (*= indicates an S-term 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]

Originally Posted by wpolly

I guess that for every positive integer n,

Sn(4)|Sn(52)

Indeed it does. As is well-known, for the LL test we can use starting values

4, 52, 724, ..., U{n}, ..., where U{n} =14 U{n-1} - u{n-2}

and

10, 970, 95050, ..., V{n}, ..., where V{n} = 98V{n-1} - V{n-2},

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_(p-2) 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 S-terms get large very quickly,
for any index j we have a decent number of not-too-huge 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_(n-2) have one of the two forms given by q = k*2^n +- 1.



Corollary:

The smallest possible odd factor of S_(n-2) is q = 2^n-1,
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_(n-2) smaller than 2^n-1, and this neatly rules that possibility out).
Clearly, if this minimum factor occurs, it must divide the primitive part of S_(n-2).

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_(k-1)] | S_j[U_k] (similarly for the
V-sequence of starting values), we have that

S_j[U_k] = S_j[U_(k-1)]*{ S_(j+1)[U_(k-1)] - 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_(k-1)],
since e.g. if S_(j+1)[U_(k-1)] factors as 2*q1*q2*...*qk, in order to factor
we still have to factor S_j[U_k]/S_j[U_(k-1)] = 2*q1*q2*...*qk - 1.

This is fun,
-Ernst

[wpolly]

Originally Posted by ewmayer

S_j[U_k] = S_j[U_(k-1)]*{ S_(j+1)[U_(k-1)] - 1 } .

In Fact,
S_j[U_k]=(2+sqrt(3))^(2^j*(2k+1))+(2-sqrt(3))^(2^j*(2k+1))
and
S_j[V_k]=(5+2sqrt(6))^(2^j*(2k+1))+(5-2sqrt(6))^(2^j*(2k+1))

[ATH]

This is a 1.5 year old thread. Did you ever take this work any further?

[ewmayer]

Originally Posted by ATH

This is a 1.5 year old thread. Did you ever take this work any further?

Not much - I found some additional ways of proving things about the special forms of the factors, but it was more by way of induction than something clean and a priori. Then something called "work for pay" intruded and I put it aside. I should get back to it - thanks for the reminder.

[jfollas]

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/cgi-bin/...i?Anum=A018844

Sequence 1: A(1)=4, A(2)=52, A(N)=14*A(N-1)-A(N-2)
Sequence 2: A(1)=10, A(2)=970, A(N)=98*A(N-1)-A(N-2)

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^(P-1) and symmetrical within the cycle about the period 2^(P-2) 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 Lucas-Lehmer Test for prime Mp and the P-2 term will be zero.