mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2007-04-04, 17:49   #1
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2·151 Posts
Question 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
nuggetprime is offline   Reply With Quote
Old 2007-04-04, 22:39   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·11·17 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2007-04-05, 08:39   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

448810 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2007-04-05, 09:19   #4
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default

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
nuggetprime is offline   Reply With Quote
Old 2007-04-05, 23:17   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·11·17 Posts
Default

Does Primo do some initial trial division to some limit before calculating elliptic curve information for primailty proofs?
paulunderwood is offline   Reply With Quote
Old 2007-04-06, 09:27   #6
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
nuggetprime is offline   Reply With Quote
Old 2007-04-06, 13:34   #7
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

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.
Jens K Andersen is offline   Reply With Quote
Old 2007-04-06, 13:39   #8
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default

Thanks.
Why it's then so needed to do an ECPP on every number which could not verified other?
nuggetprime is offline   Reply With Quote
Old 2007-04-06, 16:07   #9
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

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).
Jens K Andersen is offline   Reply With Quote
Old 2007-04-06, 16:22   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·11·17 Posts
Default

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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New ECPP record (currently: 59,798 digits) mjm Computer Science & Computational Number Theory 74 2022-12-16 01:45
ECPP-DJ danaj Computer Science & Computational Number Theory 59 2020-10-10 04:57
ECPP on Windows? CRGreathouse Software 10 2015-09-14 12:32
Can I just leave this here? (ECPP) trhabib Miscellaneous Math 6 2011-08-19 16:34
new ECPP article R. Gerbicz GMP-ECM 2 2006-09-13 16:24

All times are UTC. The time now is 11:26.


Fri Feb 3 11:26:58 UTC 2023 up 169 days, 8:55, 1 user, load averages: 0.61, 0.81, 0.82

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔