20051009, 19:50  #1 
Feb 2004
France
1110011111_{2} 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 : . When , 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 q2 iterations. (There are some rare cases where x=0 after a number of iterations different than q2) 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*x3)%p; if(x == 0, return(i)); ); return(0); } LLT2(q)= { print(q); for(i=1, sqrt(2^q1)/2/q, p=1+2*q*i; if(isprime(p), j=LLT(p,q); if(j==q2, print(i," ", 1+2*q*i, " ",j), if(j!=0, print("# ", j)) ); ); ); } 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) 
20051009, 21:57  #2 
"Robert Gerbicz"
Oct 2005
Hungary
11^{2}·13 Posts 
This isn't a miracle!
Let x(0)=5 and x(n)=2*x(n1)3 mod p. New variable: let y(n)=x(n)+1. So y(0)=4 and y(n)1=2*(y(n1)1)3 mod p from this: y(n)=2*y(n1) 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^q1)/2/q. Case 1.: Mq is prime ( q>2) . If LLT2 find a value : p=1+2*q*i and LLT(p,q)=q2 so (2)^(q2+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^q1 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)=q2, 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(q2)=0 mod p because 2^q=1 mod p, if LLT2=i<q2 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 ). 
20051009, 23:07  #3 
"William"
May 2003
New Haven
2^{2}·593 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_{2k2}(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 "q2." When the prime divides the Mersenne number, the mod is of course zero. 
20051010, 17:12  #4 
Feb 2004
France
3^{2}·103 Posts 
Too stupid I am, sometimes ...
Yes, it is not a miracle.
I've been a kind of stupid: I was studying LLTlike 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 
20051010, 21:06  #5 
Feb 2004
France
3^{2}×103 Posts 
Some LLTlike tests for Mersenne
The following formula seem to provide the same kind of primality test for Mersenne than the LLT does.
Why ? . . . 
20051010, 21:58  #6 
Jun 2005
Near Beetlegeuse
2^{2}·97 Posts 
Tony, I may have misread your post but according to your bottom line, if you start with
then you get: 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. 
20051011, 08:44  #7 
Feb 2004
France
3^{2}×103 Posts 
A family of different LLTlike primality tests for Mersennes ?
Hi Numbers,
About the third formula, if you say: and , then you see that: . So there is no miracle. Better, if you define: , then you produce the numbers: 7, 97, 31*607, ... that appear with the LLT and f_3. But, if you look at second formula: , 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 LLTlike test (PARI code): F5(q)=x=2; for(i=1,q,x=(2*x^21)%(2^q1);if(x==0,print(i))) Notice that the function mimics the look of Mersenne numbers: . About the first formula: , 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 LLTlike primality test for Mersenne numbers. f1(q)=x=1;for(i=1,q,x=(6*x*(x1)+2)%(2^q1);if(x==0,print(i))). It should be possible to prove that F_5 and f_1 are really LLTlike primality tests for Mersenne numbers, by using method described by P. Ribenboim in his book. I'll have a look. More comments ? Tony 
20051011, 21:06  #8  
Feb 2004
France
1110011111_{2} Posts 
Quote:


20051012, 13:22  #9 
Jun 2005
Near Beetlegeuse
2^{2}·97 Posts 
Tony,
I know this is going to sound trivially obvious, but all you have is (x+22)^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: (y2)^2 So the second sequence is just (x+22)^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. 
20051012, 15:00  #10 
"William"
May 2003
New Haven
2^{2}·593 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 LucasLehmer as a guide, it looks interesting to investigate the order of 3 mod Q  but I don't how. 
20051012, 16:44  #11  
Feb 2004
France
3^{2}×103 Posts 
Quote:
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: . This comes from a property of Lucas Sequences: . When n=2k. Tony 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
The best work for my CPU  MacMagnus  Information & Answers  57  20131122 16:27 
How to calculate work/effort for PRP work?  James Heinrich  PrimeNet  0  20110628 19:29 
No Work  Pilgrim  Information & Answers  1  20080131 18:53 
Out of Work?  birdman2584  Sierpinski/Riesel Base 5  12  20061122 00:06 
work to do...  guido72  Software  2  20020926 15:47 