20070404, 17:49  #1 
Mar 2007
Austria
2·151 Posts 
Where ECPP is needed?
Could anyone tell me a number bigger than 65536, which is Lucas and Fermat prp and 2Prp but not prime(a such one which really needs an ECPP)?
Thanks, nuggetprime 
20070404, 22:39  #2 
Sep 2002
Database er0rr
10724_{8} Posts 
Code:
? P=1;Q=1;for(n=65536,10^7,if(!isprime(n)&&Mod(2,n)^n==2&&Mod(Mod(1,n)*x,x^2P*x+Q)^(n1)==1,print("Fermat+Lucas pseudoprime is "n);break)) Fermat+Lucas pseudoprime is 219781 ? P=1;Q=1;for(n=65536,10^7,if(!isprime(n)&&Mod(2,n)^n==2&&Mod(3,n)^n==3&&Mod(Mod(1,n)*x,x^2P*x+Q)^(n1)==1,print("Fermat+Lucas pseudoprime is "n);break)) Fermat+Lucas pseudoprime is 252601 However the "Mod(Mod(1,n)*x,x^2P*x+Q)^(n1)==1" (with P=1 and Q=1) is more than just a Lucas test on the Fibonacci numbers, and so there will be smaller examples to your question. Perhaps someone here will supply them... For an example test that uses information about the discriminant see: http://www.trnicely.net/misc/bpsw.html Last fiddled with by paulunderwood on 20070404 at 23:17 
20070405, 08:39  #3 
Sep 2002
Database er0rr
2^{2}×7×163 Posts 
Ok, I might have goofed on this one. There seems to many definitions of"lucas pseudoprimes"  some labeled "strong" or "extra strong" or "LucasSelfridge". Some definitions require the jacobi symbol to be "1" and others do not. Some require the discriminant to be the smallest possible. "Strong" can be applied to the Fermat test too.
I think you are saying that since "Fermat+Lucas" (in some sense) has no counterexample why do people not use this and instead going to the trouble of an ECCP proof. The key word is "proof". Also, there are plenty of other methods for proving primes with 5 digits (Ed: This thread should be moved to the Misc. Math. section.) Last fiddled with by paulunderwood on 20070405 at 08:44 
20070405, 09:19  #4 
Mar 2007
Austria
2·151 Posts 
Thank you paulunderwood.
But Primo simply said at the numbers: #1: Candidate divisible by 271 #2: Candidate divisible by 41 Can you or anybody other tell me a (larger) number where Primo does an ECPP test and says that the ECPP test is failed. nuggetprime 
20070405, 23:17  #5 
Sep 2002
Database er0rr
2^{2}×7×163 Posts 
Does Primo do some initial trial division to some limit before calculating elliptic curve information for primailty proofs?

20070406, 09:27  #6 
Mar 2007
Austria
100101110_{2} Posts 

20070406, 13:34  #7 
Feb 2006
Denmark
2×5×23 Posts 
My experiments with Primo 3.0.1 show it trial factors to 65536 and then makes strong prp and Lucas tests, before attempting ECPP. (I don't know whether there are additional prp tests if Lucas is passed).
On 65521*(10^999+7) Primo says "Candidate divisible by 65521". On 65537*(10^999+7) it says "Candidate not strong pseudoprime to the base 2". (Note that many say "pseudoprime" about both prime and composite prp's, so "not pseudoprime" just means it failed a prp test) The accompanying test file Arnault.in contains a strong pseudoprime to 46 bases: N=803837457453639491257079614341942108138837688287558145837\ 48891752229742737653336521865023361639600454579150420236032\ 08766569966760987284043965408232928738791850869166857328267\ 76177102938969773947016708230428687109997439976544144845341\ 15587245063340927902227529622941498423068816854043264575340\ 18329786111298960644845216191652872597534901 Here Primo says "Candidate not Lucas strong pseudoprime for (P=1,Q=2)" It says the same for 3825123056546413051 which is strong psp to several bases. For 341550071728321 it says "Candidate not Lucas strong pseudoprime for (P=1,Q=6)". For 2390473*4183327 it says "Candidate not Lucas strong pseudoprime for (P=1,Q=3)" I don't think there is a known composite which passes the initial prp tests by Primo. If Marcel Martin finds out about one then I guess he would add a prp test which catches it in the first version thereafter. 
20070406, 13:39  #8 
Mar 2007
Austria
12E_{16} Posts 
Thanks.
Why it's then so needed to do an ECPP on every number which could not verified other? 
20070406, 16:07  #9 
Feb 2006
Denmark
2×5×23 Posts 
There probably exists composites which fool the initial prp tests in Primo. They are just very rare and haven't been discovered yet.
Mathematicians like things to be proven and that often requires a slow ECPP test for primes. Many sites including The Prime Pages only list proven primes, but prp's are accepted in some places. http://primes.utm.edu/notes/prp_prob.html says: PRP's are so often prime that Henri Cohen suggested they are "industrial grade primes" (not proven primes, but good enough for RSA encryption and similar tasks). 
20070406, 16:22  #10 
Sep 2002
Database er0rr
2^{2}·7·163 Posts 
2^3==2 (mod 3)
2^5==2 (mod 5) 2^7==2 (mod 7) 2^9==8 (mod 9) 2^11==2 (mod 11) 2^13==2 (mod 13) 2^15==8 (mod 15) 2^17==2 (mod 17) See the pattern? Yes, only for prime p, it looks like 2^p==2 (mod p)... 2^341==2 (mod 341) but 341==11*31 For Mersenne primes if you apply the LucasLehmer Theorem then it is beyond all doubt that the number tested will be prime or not. Not every (prime) number is of this special form i.e. 2^p1. For some numbers other theorems exist e.g Proth's Theorem, but, again, not every number is of this type. Also based on theorems, ECPP will test any number, but takes much longer to do (on your computer.) Now there are heuristics that suggest "Lucas+Fermat" pseudoprimes exist, but they are huge and extremely difficult to track down. A "Lucas+Fermat" test can be good enough for "industrial grade primes". Last fiddled with by paulunderwood on 20070406 at 16:35 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New ECPP record (currently: 73,269 digits)  mjm  Computer Science & Computational Number Theory  84  20230304 18:46 
ECPPDJ  danaj  Computer Science & Computational Number Theory  59  20201010 04:57 
ECPP on Windows?  CRGreathouse  Software  10  20150914 12:32 
Can I just leave this here? (ECPP)  trhabib  Miscellaneous Math  6  20110819 16:34 
new ECPP article  R. Gerbicz  GMPECM  2  20060913 16:24 