mersenneforum.org Where ECPP is needed?
 Register FAQ Search Today's Posts Mark Forums Read

 2007-04-04, 17:49 #1 nuggetprime     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 2-Prp but not prime(a such one which really needs an ECPP)? Thanks, nuggetprime
 2007-04-04, 22:39 #2 paulunderwood     Sep 2002 Database er0rr 107248 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^2-P*x+Q)^(n-1)==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^2-P*x+Q)^(n-1)==1,print("Fermat+Lucas pseudoprime is "n);break)) Fermat+Lucas pseudoprime is 252601 The second has a base-3 fermat test too. However the "Mod(Mod(1,n)*x,x^2-P*x+Q)^(n-1)==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 2007-04-04 at 23:17
 2007-04-05, 08:39 #3 paulunderwood     Sep 2002 Database er0rr 22×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 "Lucas-Selfridge". 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 2007-04-05 at 08:44
 2007-04-05, 09:19 #4 nuggetprime     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
 2007-04-05, 23:17 #5 paulunderwood     Sep 2002 Database er0rr 22×7×163 Posts Does Primo do some initial trial division to some limit before calculating elliptic curve information for primailty proofs?
2007-04-06, 09:27   #6
nuggetprime

Mar 2007
Austria

1001011102 Posts

Quote:
 Originally Posted by paulunderwood Does Primo do some initial trial division to some limit before calculating elliptic curve information for primailty proofs?
Yes. I think up to about 300.

nuggetprime

 2007-04-06, 13:34 #7 Jens K Andersen     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.
 2007-04-06, 13:39 #8 nuggetprime     Mar 2007 Austria 12E16 Posts Thanks. Why it's then so needed to do an ECPP on every number which could not verified other?
 2007-04-06, 16:07 #9 Jens K Andersen     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).
 2007-04-06, 16:22 #10 paulunderwood     Sep 2002 Database er0rr 22·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 Lucas-Lehmer 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^p-1. 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 2007-04-06 at 16:35

 Similar Threads Thread Thread Starter Forum Replies Last Post mjm Computer Science & Computational Number Theory 84 2023-03-04 18:46 danaj Computer Science & Computational Number Theory 59 2020-10-10 04:57 CRGreathouse Software 10 2015-09-14 12:32 trhabib Miscellaneous Math 6 2011-08-19 16:34 R. Gerbicz GMP-ECM 2 2006-09-13 16:24

All times are UTC. The time now is 10:34.

Thu Mar 30 10:34:50 UTC 2023 up 224 days, 8:03, 0 users, load averages: 0.75, 0.75, 0.75