Where ECPP is needed?

[nuggetprime]

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

[paulunderwood]

? 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

[paulunderwood]

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.)

[nuggetprime]

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

[paulunderwood]

Does Primo do some initial trial division to some limit before calculating elliptic curve information for primailty proofs?

[nuggetprime]

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

[Jens K Andersen]

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.

[nuggetprime]

Thanks.
Why it's then so needed to do an ECPP on every number which could not verified other?

[Jens K Andersen]

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).

[paulunderwood]

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".