Dario Alpern's ECM
 

Question: When the ECM test on Dario Alpern's webpage [url]http://www.alpertron.com.ar/ECM.HTM[/url] says that a certain number is prime, does that constitute a primality proof, or rather is the number probably prime?

For example it said that 10^1000+453 was prime, but it also said it performed pseudoprime tests.

When the number has up to about 844 digits, it uses the algorithm APRT-CLE, so if it is shows that it is prime, it is certainly, unless there is a bug in the applet.

For greater numbers it uses the Miller-Rabin algorithm, so you cannot be 100% sure that the number is prime or not.

This threshold is done because for numbers greater than 844 digits the APRT-CLE takes a lot of time.

I have downloaded Preda Mihaulescu primality cyclotomic method which is much faster than the one implemented in my applet, but it is very difficult to program. Furthermore I don't have any implementation so I can compare the intermediate results.

It is possible to program the Proth algorithm for numbers of the form a^b+1, but this is restricted to a few numbers (but it appears that is used a lot here because it is easy to determine if a big number of this form is prime or not).

Great, thanks for your help... pretty much every prime of current importance to me is therefore a proven prime.

Dario Alpern's ECM
 

[URL]http://www.alpertron.com.ar/ECM.HTM[/URL] does only Fermat tests instead of Miller-Rabin tests (the strong version).
"The pseudoprime tests used in functions [B]B[/B] and [B]N[/B] includes trial division by the 100 first primes and then up to 20 Rabin-Miller strong pseudoprime tests. So it has a very high probability to find a prime number."
Examples:
N(83828294550) -> 83828 294551 = 1231 x 6151 x 11071
N(245291853690) -> 245291 853691 = 1171 x 10531 x 19891
N(2152302898746) -> 2 152302 898747 = 6763 x 10627 x 29947

If it uses 20 Miller-Rabin tests, the smallest number which fails this tests, have at least 37 digits: [URL]http://mathworld.wolfram.com/StrongPseudoprime.html[/URL]

There are many small Carmichael numbers which fails on 20 (and more) Fermat tests.

Regard. Joe53

[QUOTE=joe53;344861][URL]http://www.alpertron.com.ar/ECM.HTM[/URL] does only Fermat tests instead of Miller-Rabin tests (the strong version).
"The pseudoprime tests used in functions [B]B[/B] and [B]N[/B] includes trial division by the 100 first primes and then up to 20 Rabin-Miller strong pseudoprime tests.
[/QUOTE]

(1) The term "pseudoprime" (sic) is being misused.
(2) Running 20 strong PRP (probable prime, not [i]pseudoprime[/i]!)
is pointless. A single strong PRP followed by a LL or Frobenius test
would be more effective.

[QUOTE]


So it has a very high probability to find a prime number."
Examples:
N(83828294550) -> 83828 294551 = 1231 x 6151 x 11071
N(245291853690) -> 245291 853691 = 1171 x 10531 x 19891
N(2152302898746) -> 2 152302 898747 = 6763 x 10627 x 29947

If it uses 20 Miller-Rabin tests, the smallest number which fails this tests, have at least 37 digits: [URL]http://mathworld.wolfram.com/StrongPseudoprime.html[/URL]

There are many small Carmichael numbers which fails on 20 (and more) Fermat tests.

Regard. Joe53[/QUOTE]

BFD. I can *prove* a 37-digit number prime almost as fast as 20
strong PRP tests.

Finally:


(3) Don't take mathworld as an authoritative text.

[QUOTE=joe53;344861][URL]http://www.alpertron.com.ar/ECM.HTM[/URL] does only Fermat tests instead of Miller-Rabin tests (the strong version).
"The pseudoprime tests used in functions [B]B[/B] and [B]N[/B] includes trial division by the 100 first primes and then up to 20 Rabin-Miller strong pseudoprime tests. So it has a very high probability to find a prime number."
Examples:
N(83828294550) -> 83828 294551 = 1231 x 6151 x 11071
N(245291853690) -> 245291 853691 = 1171 x 10531 x 19891
N(2152302898746) -> 2 152302 898747 = 6763 x 10627 x 29947

If it uses 20 Miller-Rabin tests, the smallest number which fails this tests, have at least 37 digits: [URL]http://mathworld.wolfram.com/StrongPseudoprime.html[/URL]

There are many small Carmichael numbers which fails on 20 (and more) Fermat tests.

Regard. Joe53[/QUOTE]

The B(n) and N(n) functions perform Miller Rabin tests but maybe there is an error in the implementation. I will check that in a few days.

It's frustrating that MathWorld continues to call them "pseudoprime tests."

Regardless of MathWorld's authority (or lack thereof), this "If it uses 20 Miller-Rabin tests, the smallest number which fails this tests, have at least 37 digits" doesn't even follow from what they say. It's a conjecture, not a proof.

Your proofs are faster than mine, but I see the point (mine take 2-3 milliseconds for 37 digits, Pari takes about 5 milliseconds, 20 M-R's are under 0.2 milliseconds, a strong BPSW is maybe 0.06 milliseconds). APRCL should be reasonably fast at this size also.

For prev_prime / next_prime I'd think you'd prefer to not be proving every candidate. Skip forward/back with mod-6 or mod-30, prune with some trial/gcd, then run something like strong BPSW. The initial trial and SPSP-2 will prune most possibilities quickly.

I do agree that something other than 20 PRP tests seems smarter (I'm ignoring vagaries of Javascript implementation and programmer time however). Strong or extra-strong BPSW, and throw in an extra Miller-Rabin with random base if you want. Ought to be 3 to 7 times faster.

[Now digressing even more, I think SymPy is on track to stop using M-R with the first 46 primes for their isprime, and go to strong BPSW. I still need to get cracking on getting Perl 6 to not use the first 100 (!) prime bases, and more importantly change the API before its frozen. This mostly just shows that this is a common trend.]

I've just fixed the error. I expected to use the prime bases 5, 7, 11, 13, ... but the initial base assignment was inside the loop so it was doing 20 times a Miller-Rabin test with base 5.

From an external request, I also added hexadecimal input. If you type 0x45, the applet will factor the number 69. In a few days I will also add hexadecimal output.

There still is an error in the program - in the Miller-Rabin test.
My first test number is strong PRP for the first 150 prime bases, ONLY! (And not Lucas probable prime, not pass BPSW):
[code]
2504564851231996223418611498583553580586431162725714036294663419005627942030045018144967085826016995812748308972856014960994030057096300272690934546847718913274308904632162037753108744756079484071197757334474410667077275268095650646955133107287726653142089063491101528203219286279619714745365476456016263876476506935633902632378276445418807506643579691598485378380707876204179521868647423847956174718793857337275560326966743283833603259339320266954292802259534246253628396748505321522751546284902630334444060405092248083998624231344891540701484875133564504847404605998928272819163447443703835478321841022013831138852193839499198235152203734163783925867691241340516136948911294063782761240713332883707486122030071233696262539897861764349350102562679795879652984483644711085101952997260985769555028200212433179592354351467963621580674595217679045289986395851940360535530808265791863676735166100444465385760336851651312776349197351443263637225179385994064241024523629682623814114793546441523513505946466820080716059467[/code]
It's number's 3 prime factor with format: N= (n+1)(37n+1)(41n+1).
My second test number is strong PRP for all the 168 prime bases below 1000, ONLY! (And not Lucas probable prime, not pass BPSW):
[code]
2809386136371438866496346539320857607283794588353401165473007394921174159995576890097633348301878401799853448496604965862616291048652062065394646956750323263193037964463262192320342740843556773326129475220032687577421757298519461662249735906372935033549531355723541168448473213797808686850657266188854910604399375221284468243956369013816289853351613404802033369894673267294395882499368769744558478456847832293372532910707925159549055961870528474205973317584333504757691137280936247019772992086410290579840045352494329434008415453636962234340836064927449224611783307531275541463776950841504387756099277118377038405235871794332425052938384904092351280663156507379159650872073401637805282499411435158581593146712826943388219341340599170371727498381901415081480224172469034841153893464174362543356514320522139692755430021327765409775374978255770027259819794532960997484676733140078317807018465818200888425898964847614568913543667470861729894161917981606153150551439410460813448153180857197888310572079656577579695814664713878369660173739371415918888444922272634772987239224582905405240454751027613993535619787590841842251056960329294514093407010964283471430374834873427180817297408975879673867[/code]

(...added them to factordb, for quick reference:
[URL]http://factordb.com/index.php?id=1100000000622774203[/URL]
[URL]http://factordb.com/index.php?id=1100000000622774494[/URL] )

joe53, those are great examples -- better than the old Arnault ones good to the first 46 and 62 prime bases. One of the key points in my opinion from his 1993-1995 papers was that he showed a method for constructing numbers that pass M-R tests to the first N bases. So any primality test using a bunch of M-R tests to the first few prime bases seems like a bad plan (and it is so common). Using uniform random bases [2,n-1] at least would avoid those fixed numbers (though GMP is an example where the random sequence is fixed so not much better).

[quote]My first test number is strong PRP for the first 150 prime bases, ONLY! (And not Lucas probable prime, not pass BPSW)[/quote]Just to clear up the "ONLY" word, it is a strong pseudoprime to the first 150 prime bases, not to the 151st, but after that it's a mix. As you point out, neither one are Lucas-Selfridge standard or strong pseudoprimes, nor extra-strong or almost-extra-strong pseudoprimes ("almost" being Pari's fast V-only method), hence BPSW isn't fooled.