mersenneforum.org Lucas and Fibonacci primes
 Register FAQ Search Today's Posts Mark Forums Read

 2017-06-11, 09:40 #1 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100101011000102 Posts Lucas and Fibonacci primes There were 64 known prime Lucas numbers (including PRPs) and many of them are packed in clusters. Unexpectedly, there is a huge gap after the last previously known prime. (And similarly in Fibonacci primes, - observe the gap between 1968721 and 2904353, not quite as large but still 1.5x ) As agreed with R. and H.Lifschitz, I started the search at n>1800000, and found one more (though they reported that no primes were found in the substantial range between - where they searched since 2009). L(2316773) is a PRP after L(1051849). The size of the gap makes one suspect that something is amiss (there may be another prime). Or not! ...Makes one think - the same could happen to Mersennes. Like, you know, a jump from 74,207,281 to >150,000,000. Attached Thumbnails
2017-06-11, 11:11   #2
paulunderwood

Sep 2002
Database er0rr

386610 Posts

Quote:
 Originally Posted by Batalov L(2316773) is a PRP
Code:
? n=2316773;N=fibonacci(n+1)-fibonacci(n-1);write("Lucas_2316773",N)
Code:
time ../../coding/gwnum/lucasPRP Lucas_2316773
Lucas testing on x^2 - 3*x + 1 ...
Is Lucas PRP!

real	51m50.458s
user	148m41.324s
sys	5m29.136s
I guess GIMPS is more fastidious about their RES64. Did R&H keep theirs for you to compare with? -- I guess you all used OpenPFGW.

2017-06-11, 17:24   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×3×5×11×29 Posts

Quote:
 Originally Posted by paulunderwood -- I guess you all used OpenPFGW.
Yes. (That's the Achilles' heel of this project.)

They have their sieve, and I have my sieve, and with regards to sieving -- PFGW itself is doing quite a good job: you can sieve to ~49-50 bits just by doing the proper command-line:
pfgw64 -V -N -k -l -f200"{2p}" -q"L(p)"
where
200 is optional.

Don't know anything about residues, they probably do. I only had one email exchange with them with an answer to 'how far did they test'. Verifying residues is of course possible.

 2017-06-12, 18:50 #4 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 24·191 Posts Please see the thread http://mersenneforum.org/showthread.php?t=21814 for the n-Fibonacci primes and the n-step Fibonacci primes. Last fiddled with by sweety439 on 2017-06-12 at 18:51
2017-06-20, 08:36   #5
paulunderwood

Sep 2002
Database er0rr

2·1,933 Posts

Quote:
 Originally Posted by paulunderwood Code: ? n=2316773;N=fibonacci(n+1)-fibonacci(n-1);write("Lucas_2316773",N)
This should be N=fibonacci(n+1)+fibonacci(n-1)

2017-06-20, 14:31   #6
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101011000102 Posts

Quote:
Originally Posted by paulunderwood
Quote:
 Originally Posted by paulunderwood Code: ? n=2316773;N=fibonacci(n+1)-fibonacci(n-1);write("Lucas_2316773",N)
This should be N=fibonacci(n+1)+fibonacci(n-1)
Wait, was the "-" form a "Is Lucas PRP!", too?!

2017-06-20, 14:33   #7
paulunderwood

Sep 2002
Database er0rr

2×1,933 Posts

Quote:
 Originally Posted by Batalov Wait, was the "-" form a "Is Lucas PRP!", too?!
Not likely! I think I screen-scraped the correct value and tested it, before using Pari/GP to write the file afresh with wrong value -- I am testing it now, but it was not Fermat 7-PRP

Last fiddled with by paulunderwood on 2017-06-20 at 14:53

 2017-06-20, 15:38 #8 paulunderwood     Sep 2002 Database er0rr 2×1,933 Posts Wow! The bad value is Lucas-PRP with respect to x^2-3*x+1. I am now testing the good value, which is using x^2-5*x+1.
 2017-06-20, 16:55 #9 paulunderwood     Sep 2002 Database er0rr 2×1,933 Posts Code: ../../coding/gwnum/lucasPRP Lucas_2316773 Lucas testing on x^2 - 5*x + 1 ... Is Lucas PRP! I checked F(2316773) (for that is what it is) and it is not Fermat 2-PRP, but it is Lucas PRP w.r.t. x^2-3*x+1
2017-06-28, 16:56   #10
Dr Sardonicus

Feb 2017
Nowhere

115758 Posts

Quote:
 Originally Posted by paulunderwood I checked F(2316773) (for that is what it is) and it is not Fermat 2-PRP, but it is Lucas PRP w.r.t. x^2-3*x+1
There is a simple explanation for this. It is analogous to the fun fact that, if p is prime, then Mp = 2p - 1 is a base-2 pseudoprime, whether Mp is prime or not.

In the present instance, the zeroes of the polynomial f = x^3 - 3*x + 1 are the squares of the zeroes of x^2 - x - 1. Consequently, if s = Mod(2*x - 3, f) [so that s is a square root of 5], then we may write

Mod(x, f)^n = Mod((L2*n + F2*n*s)/2, f).

Now, given a modulus N > 1, we see that Mod(x, f)^n == 1 (mod N) when L2*n == 2 (mod N) and F2*n == 0 (mod N).

Now let p be an odd prime number, and (5/p) = -1 (i.e. p == 3 or 7 (mod 10)). Then p remains prime in the ring R = Z[Mod(x, f)] (which is the maximal order of K = Q[Mod(x, f)]), and

r^p == r' (mod pR) for any r in R, where ' is conjugation in K/Q ["Frobenius automorphism"]. Consequently, we have

Fp+1 == 0 (mod pR) and Lp+1 == L1 = 2 (mod pR), so that Mod(x, f)p+1 == 1 (mod pR).

Now, we show that, if P = Fp, then Mod(x, f)P+1 == 1 (mod PR), whether P is prime or not, regardless of whether (5/P) = 1 or -1.

We also have (again assuming (5/p) = -1) Fp == -1 (mod p). This means [since P = Fp] that

p|(P + 1), so that P|FP+1. Therefore P|F2*(P+1) also. Now, in order to show that

Mod(x, f)P+1 == 1 (mod PR),

we only need to show that

L2*(P+1) == 2 (mod P).

Since P+1 is even, we have

(L(P+1))2 - 5*(FP+1)2 = 4, so that

(L(P+1))2 == 4 (mod P). Again, since P+1 is even, we have

L2*(P+1) = (L(P+1))2 - 2, whence

L2*(P+1) == 2 (mod P),

and the proof is complete.

Remarks: I drew a blank on L(P+1) (mod P), apart from its square being 4 (mod P). If P were prime, L(P+1) would be == -2 (mod P). If it turned out to be anything other than 2 or -2 (mod P), it would immediately give a factorization of P.

One has (5/p) = (5/Fp) = -1 when p == 7, 13, 23, 37, 47, or 53 (mod 60); 2316773 == 53 (mod 60).

Last fiddled with by Dr Sardonicus on 2017-06-28 at 16:57

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz And now for something completely different 42 2019-06-03 14:09 sweety439 And now for something completely different 17 2017-06-13 03:49 rogue And now for something completely different 5 2016-07-18 14:33 Raman Math 40 2010-07-19 03:30 geoff Factoring 13 2005-12-23 01:59

All times are UTC. The time now is 13:18.

Fri Oct 22 13:18:07 UTC 2021 up 91 days, 7:47, 1 user, load averages: 1.20, 1.41, 1.34

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.