It seems to work, but why ?

T.Rex · 2005-10-09, 19:50

With the following, I'm able to find divisors of Mersenne numbers.
It is surely not useful, because it is MUCH slower than dividing Mersenne numbers by candidate divisors.
But I do not understand why it works.
Do you have an idea ?

Tony

Look at the following PARI/gp code.

LLT(p,m) is a routine that computes several values (up to a maximum m) like the LLT does:
x=-5 is the starting value, then it applies : $x = (-2x-3) \ \bmod{p}$ .
When $x \equiv 0 \ \pmod{p}$ , it stops and returns the number of iterations done.

LLT2(q) enumerates all prime candidate divisors of Mq and calls LLT(p,q) for finding how many iterations (i) are required before x=0.
It is a success if x=0 is found after q-2 iterations.
(There are some rare cases where x=0 after a number of iterations different than q-2)

I've experimented with the following values of q: 11, 13, 17, 23, 29, 31, 41, 43, 47, 53, 59, 89 (not finished for 89), and the result is always:
- if Mq is prime, then LLT2 never succeeds (no divisor p is found).
- if Mq is composite, then LLT2 finds divisors of Mq, and only them.
It seems to be a miracle (or an evidence, or my mistake ?).

As an example, for q=53, it finds the 3 divisors of M_53: 6361, 69431 and 20394401.

LLT(p,m)=
{
x=-5;
for(i=1,m,
x=(-2*x-3)%p;
if(x == 0, return(i));
);
return(0);
}

LLT2(q)=
{
print(q);
for(i=1, sqrt(2^q-1)/2/q,
p=1+2*q*i;
if(isprime(p),
j=LLT(p,q);
if(j==q-2,
print(i," ", 1+2*q*i, " ",j),
if(j!=0, print("# ", j))
);
);
);
print
}

LLT2(11)
LLT2(13)
LLT2(17)
LLT2(19)
LLT2(23)
LLT2(29)
LLT2(31)
LLT2(41)
LLT2(43)
LLT2(47)
LLT2(53)
LLT2(59)
LLT2(89)
LLT2(101)

R. Gerbicz · 2005-10-09, 21:57

This isn't a miracle!
Let x(0)=-5 and x(n)=-2*x(n-1)-3 mod p.
New variable: let y(n)=x(n)+1. So y(0)=-4 and y(n)-1=-2*(y(n-1)-1)-3 mod p from this:
y(n)=-2*y(n-1) mod p so x(n)=y(n)-1=(-2)^n*y(0)-1=-(-2)^(n+2)-1 mod p.
It is easy to see that LT(p,m)=i if and only if i<=m and i is the smallest solution of x(n)=0 mod p or i=0 if it hasn't got a solution up to m.

Suppose that q is prime then every prime divisor of Mq is of the form p=1+2*q*i; where i>=1 is an integer and we can suppose that p<sqrt(Mq) so i<sqrt(2^q-1)/2/q.

Case 1.: Mq is prime ( q>2) . If LLT2 find a value : p=1+2*q*i and LLT(p,q)=q-2 so -(-2)^(q-2+2)-1=0 mod p, but q=1 mod 2 so 2^q=1 mod p from this p is a prime divisor of 2^q-1 and 1<p<sqrt(Mq) so it is a proper divisor of Mq, but Mq is prime this is a contradiction.

Case2.: Mq is composite. If LLT2 find a value p=1+2*q*i and LLT(p,q)=q-2, then we have seen that p is a prime divisor of Mq. And it is also true that if p<sqrt(Mq) and p is a prime divisor of Mq then LLT2 will find this p:
x(q-2)=0 mod p because 2^q=1 mod p, if LLT2=i<q-2 so x(i)=0 mod p then -(-2)^(i+2)-1=0 mod p from this (-2)^(i+1)=-1 mod p // ^2 mod p we get 2^(2*(i+1))=1 mod p but 2^q=1 mod p is also true ( here q is prime ) so the order of 2 modulo p is 1, it is a contradiction ( 2^1=1 modulo p isn't possible ). So LLT will find all prime divisors of Mq and only them. ( up to the square root of Mq ).

wblipp · 2005-10-09, 23:07

Study the iteration without the mod. The negative signs are distracting, so take it 2 steps at a time,

F_2k(x) = 4 * F_2k-2(x)+3

It's not hard to show that

F_2k(x) = 2^2k(x+1)-1

Hence

F_2k+1(x) = -2^2k+1(x+1)-1

When x=-5, this is

F_2k+1(-5) = 2^2k+3-1

So the value, without any mod operations, is exactly the Mersenne Number at iteration "q-2." When the prime divides the Mersenne number, the mod is of course zero.

T.Rex · 2005-10-10, 17:12

Yes, it is not a miracle.
I've been a kind of stupid: I was studying LLT-like formula modulo Mq : x=(a*x^2+b*x+c)(mod Mq). And, with a=0, I did not think about looking at the numbers x without the modulo ... which are the Mersenne numbers.
Thanks for opening my eyes !
Tony

T.Rex · 2005-10-10, 21:06

The following formula seem to provide the same kind of primality test for Mersenne than the LLT does.
Why ?

$S_0=1 \ ,\ S_{i+1}=6S_i^2-6S_i+2$ . $M_q \text{ prime iff } S_{q-1} \equiv 0 \ \pmod{M_q}$

$S_0=5 \ ,\ S_{i+1}=2S_i^2-1$ . $M_q \text{ prime iff } S_{q-2} \equiv 0 \ \pmod{M_q}$

$S_0=6 \ ,\ S_{i+1}=(S_i-2)^2$ . $M_q \text{ prime iff } S_{q-1} \equiv 0 \ \pmod{M_q}$

Numbers · 2005-10-10, 21:58

Tony, I may have mis-read your post but according to your bottom line, if you start with

$\large S_{0}\,=\,6,\;S_{1}\,=\,S_{0}-2^{2}$

then you get:

$\large (6-2)^2\,=\,16,\;(16-2)^2\,=\,196,\;(196-2)^2\,=37636$ etc.

this last has the factors 2, 2, 97, 97 which does not seem to fit very well with a test for division by a Mersenne number. The LL number 37634 on the other hand has the factors 2, 31, 607 which does fit with Mersennes, so I‘m wondering if maybe there’s a typo in your post.

T.Rex · 2005-10-11, 08:44

Hi Numbers,
About the third formula, if you say: $\large x_0=4 \ ,\ llt(x_{i+1})=x_i^2-2$ and $\large x_0=6 \ ,\ f_3(x_{i+1})=(x_i-2)^2$ , then you see that: $\large f_3(x_{i+1})=\big(llt(x_i)\big)^2$ . So there is no miracle.
Better, if you define: $\large x_0=2 \ ,\ F(x_{i+1})=2x_i^2-1$ , then you produce the numbers: 7, 97, 31*607, ... that appear with the LLT and f_3.

But, if you look at second formula: $\large x_0=5 \ ,\ F_5(x_{i+1})=2x_i^2-1$ , which is the same than F(x), but with a different x_0, you get: 7^2, 4801, 31*1487071, 52609*80789839489, 127*769*36810112513*10050007226929279, ... . So this F_5 function generates different numbers but it still acts as a LLT-like test (PARI code):
F5(q)=x=2; for(i=1,q,x=(2*x^2-1)%(2^q-1);if(x==0,print(i)))

Notice that the function $\large F(x_{i+1})=2x_i^2-1$ mimics the look of Mersenne numbers: $\large 2*(2^x)^2-1$ .

About the first formula: $\large x_0=1 \ ,\ f_1(x_{i+1})=6x_i(x_i-1)+2$ , it produces different numbers: 2, 2*7, 2*547, 2*7*31*61*271, 2*6883*22434744889, 2*7*19*37*43*127*547*883*2269*2521*550554229, ... and it also looks like it is still a LLT-like primality test for Mersenne numbers.
f1(q)=x=1;for(i=1,q,x=(6*x*(x-1)+2)%(2^q-1);if(x==0,print(i))).

It should be possible to prove that F_5 and f_1 are really LLT-like primality tests for Mersenne numbers, by using method described by P. Ribenboim in his book. I'll have a look.

More comments ?
Tony

T.Rex · 2005-10-11, 21:06

Quote:

Originally Posted by T.Rex

It should be possible to prove that F_5 and f_1 are really LLT-like primality tests for Mersenne numbers, by using method described by P. Ribenboim in his book. I'll have a look.

The methods used by Lucas and Lehmer do not apply for F_5 and f_1. Tony

Numbers · 2005-10-12, 13:22

Tony,
I know this is going to sound trivially obvious, but all you have is (x+2-2)^2 = x^2

You have one sequence starts with a 4, and goes (x^2)-2
Then you have another sequence starting with a 6, going: (y-2)^2

So the second sequence is just (x+2-2)^2 which is pretty obviously x^2

I can’t believe you haven’t already seen this, but there doesn’t appear to be a better answer to why it happens.

wblipp · 2005-10-12, 15:00

FWIW, the closed form solution of the first itereation is

S_n = (3^2[sup]n[/sup])/6 + 1/2

Using the MersenneWiki explication of Lucas-Lehmer as a guide, it looks interesting to investigate the order of 3 mod Q - but I don't how.

T.Rex · 2005-10-12, 16:44

Quote:

Originally Posted by Numbers

I can’t believe you haven’t already seen this, but there doesn’t appear to be a better answer to why it happens.

In fact (and this happens too often), I realized my mistake once I have posted and switched off my PC and was ready to sleep. It it what I explain in first part of my post #7 about llt and f3. They are 2 different formula for the same kind of numbers.
About F5 and f1 in #7, I've read again papers. Based on Ribenboim work, they cannot be proved by usual technics because we must have: $\large S_{i+1} < S_i^2$ . This comes from a property of Lucas Sequences: $\large V_{2n} = V_n^2 -2Q^n$ . When n=2k.
Tony

2005-10-09, 19:50	#1
T.Rex Feb 2004 France 1110100101₂ Posts	It seems to work, but why ? With the following, I'm able to find divisors of Mersenne numbers. It is surely not useful, because it is MUCH slower than dividing Mersenne numbers by candidate divisors. But I do not understand why it works. Do you have an idea ? Tony Look at the following PARI/gp code. LLT(p,m) is a routine that computes several values (up to a maximum m) like the LLT does: x=-5 is the starting value, then it applies : $x = (-2x-3) \ \bmod{p}$ . When $x \equiv 0 \ \pmod{p}$ , it stops and returns the number of iterations done. LLT2(q) enumerates all prime candidate divisors of Mq and calls LLT(p,q) for finding how many iterations (i) are required before x=0. It is a success if x=0 is found after q-2 iterations. (There are some rare cases where x=0 after a number of iterations different than q-2) I've experimented with the following values of q: 11, 13, 17, 23, 29, 31, 41, 43, 47, 53, 59, 89 (not finished for 89), and the result is always: - if Mq is prime, then LLT2 never succeeds (no divisor p is found). - if Mq is composite, then LLT2 finds divisors of Mq, and only them. It seems to be a miracle (or an evidence, or my mistake ?). As an example, for q=53, it finds the 3 divisors of M_53: 6361, 69431 and 20394401. LLT(p,m)= { x=-5; for(i=1,m, x=(-2x-3)%p; if(x == 0, return(i)); ); return(0); } LLT2(q)= { print(q); for(i=1, sqrt(2^q-1)/2/q, p=1+2qi; if(isprime(p), j=LLT(p,q); if(j==q-2, print(i," ", 1+2q*i, " ",j), if(j!=0, print("# ", j)) ); ); ); print } LLT2(11) LLT2(13) LLT2(17) LLT2(19) LLT2(23) LLT2(29) LLT2(31) LLT2(41) LLT2(43) LLT2(47) LLT2(53) LLT2(59) LLT2(89) LLT2(101)

2005-10-10, 17:12	#4
T.Rex Feb 2004 France 3×311 Posts	Too stupid I am, sometimes ... Yes, it is not a miracle. I've been a kind of stupid: I was studying LLT-like formula modulo Mq : x=(ax^2+bx+c)(mod Mq). And, with a=0, I did not think about looking at the numbers x without the modulo ... which are the Mersenne numbers. Thanks for opening my eyes ! Tony

2005-10-10, 21:06	#5
T.Rex Feb 2004 France 933₁₀ Posts	Some LLT-like tests for Mersenne The following formula seem to provide the same kind of primality test for Mersenne than the LLT does. Why ? $S_0=1 \ ,\ S_{i+1}=6S_i^2-6S_i+2$ . $M_q \text{ prime iff } S_{q-1} \equiv 0 \ \pmod{M_q}$ $S_0=5 \ ,\ S_{i+1}=2S_i^2-1$ . $M_q \text{ prime iff } S_{q-2} \equiv 0 \ \pmod{M_q}$ $S_0=6 \ ,\ S_{i+1}=(S_i-2)^2$ . $M_q \text{ prime iff } S_{q-1} \equiv 0 \ \pmod{M_q}$

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The best work for my CPU	MacMagnus	Information & Answers	57	2013-11-22 16:27
How to calculate work/effort for PRP work?	James Heinrich	PrimeNet	0	2011-06-28 19:29
No Work	Pilgrim	Information & Answers	1	2008-01-31 18:53
Out of Work?	birdman2584	Sierpinski/Riesel Base 5	12	2006-11-22 00:06
work to do...	guido72	Software	2	2002-09-26 15:47

2005-10-09, 21:57	#2
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 11001001011₂ Posts	This isn't a miracle! Let x(0)=-5 and x(n)=-2x(n-1)-3 mod p. New variable: let y(n)=x(n)+1. So y(0)=-4 and y(n)-1=-2(y(n-1)-1)-3 mod p from this: y(n)=-2y(n-1) mod p so x(n)=y(n)-1=(-2)^ny(0)-1=-(-2)^(n+2)-1 mod p. It is easy to see that LT(p,m)=i if and only if i<=m and i is the smallest solution of x(n)=0 mod p or i=0 if it hasn't got a solution up to m. Suppose that q is prime then every prime divisor of Mq is of the form p=1+2qi; where i>=1 is an integer and we can suppose that p<sqrt(Mq) so i<sqrt(2^q-1)/2/q. Case 1.: Mq is prime ( q>2) . If LLT2 find a value : p=1+2qi and LLT(p,q)=q-2 so -(-2)^(q-2+2)-1=0 mod p, but q=1 mod 2 so 2^q=1 mod p from this p is a prime divisor of 2^q-1 and 1<p<sqrt(Mq) so it is a proper divisor of Mq, but Mq is prime this is a contradiction. Case2.: Mq is composite. If LLT2 find a value p=1+2qi and LLT(p,q)=q-2, then we have seen that p is a prime divisor of Mq. And it is also true that if p<sqrt(Mq) and p is a prime divisor of Mq then LLT2 will find this p: x(q-2)=0 mod p because 2^q=1 mod p, if LLT2=i<q-2 so x(i)=0 mod p then -(-2)^(i+2)-1=0 mod p from this (-2)^(i+1)=-1 mod p // ^2 mod p we get 2^(2*(i+1))=1 mod p but 2^q=1 mod p is also true ( here q is prime ) so the order of 2 modulo p is 1, it is a contradiction ( 2^1=1 modulo p isn't possible ). So LLT will find all prime divisors of Mq and only them. ( up to the square root of Mq ).

2005-10-09, 23:07	#3
wblipp "William" May 2003 Near Grandkid 3·7·113 Posts	Study the iteration without the mod. The negative signs are distracting, so take it 2 steps at a time, F_2k(x) = 4 * F_2k-2(x)+3 It's not hard to show that F_2k(x) = 2^2k(x+1)-1 Hence F_2k+1(x) = -2^2k+1(x+1)-1 When x=-5, this is F_2k+1(-5) = 2^2k+3-1 So the value, without any mod operations, is exactly the Mersenne Number at iteration "q-2." When the prime divides the Mersenne number, the mod is of course zero.

2005-10-10, 21:58	#6
Numbers Jun 2005 Near Beetlegeuse 388₁₀ Posts	Tony, I may have mis-read your post but according to your bottom line, if you start with $\large S_{0}\,=\,6,\;S_{1}\,=\,S_{0}-2^{2}$ then you get: $\large (6-2)^2\,=\,16,\;(16-2)^2\,=\,196,\;(196-2)^2\,=37636$ etc. this last has the factors 2, 2, 97, 97 which does not seem to fit very well with a test for division by a Mersenne number. The LL number 37634 on the other hand has the factors 2, 31, 607 which does fit with Mersennes, so I‘m wondering if maybe there’s a typo in your post.

2005-10-11, 08:44	#7
T.Rex Feb 2004 France 933₁₀ Posts	A family of different LLT-like primality tests for Mersennes ? Hi Numbers, About the third formula, if you say: $\large x_0=4 \ ,\ llt(x_{i+1})=x_i^2-2$ and $\large x_0=6 \ ,\ f_3(x_{i+1})=(x_i-2)^2$ , then you see that: $\large f_3(x_{i+1})=\big(llt(x_i)\big)^2$ . So there is no miracle. Better, if you define: $\large x_0=2 \ ,\ F(x_{i+1})=2x_i^2-1$ , then you produce the numbers: 7, 97, 31607, ... that appear with the LLT and f_3. But, if you look at second formula: $\large x_0=5 \ ,\ F_5(x_{i+1})=2x_i^2-1$ , which is the same than F(x), but with a different x_0, you get: 7^2, 4801, 311487071, 5260980789839489, 1277693681011251310050007226929279, ... . So this F_5 function generates different numbers but it still acts as a LLT-like test (PARI code): F5(q)=x=2; for(i=1,q,x=(2x^2-1)%(2^q-1);if(x==0,print(i))) Notice that the function $\large F(x_{i+1})=2x_i^2-1$ mimics the look of Mersenne numbers: $\large 2(2^x)^2-1$ . About the first formula: $\large x_0=1 \ ,\ f_1(x_{i+1})=6x_i(x_i-1)+2$ , it produces different numbers: 2, 27, 2547, 273161271, 2688322434744889, 2719374312754788322692521550554229, ... and it also looks like it is still a LLT-like primality test for Mersenne numbers. f1(q)=x=1;for(i=1,q,x=(6x(x-1)+2)%(2^q-1);if(x==0,print(i))). It should be possible to prove that F_5 and f_1 are really LLT-like primality tests for Mersenne numbers, by using method described by P. Ribenboim in his book. I'll have a look. More comments ? Tony

2005-10-12, 13:22	#9
Numbers Jun 2005 Near Beetlegeuse 2²·97 Posts	Tony, I know this is going to sound trivially obvious, but all you have is (x+2-2)^2 = x^2 You have one sequence starts with a 4, and goes (x^2)-2 Then you have another sequence starting with a 6, going: (y-2)^2 So the second sequence is just (x+2-2)^2 which is pretty obviously x^2 I can’t believe you haven’t already seen this, but there doesn’t appear to be a better answer to why it happens.

2005-10-12, 15:00	#10
wblipp "William" May 2003 Near Grandkid 2373₁₀ Posts	FWIW, the closed form solution of the first itereation is S_n = (3^2[sup]n[/sup])/6 + 1/2 Using the MersenneWiki explication of Lucas-Lehmer as a guide, it looks interesting to investigate the order of 3 mod Q - but I don't how.