mersenneforum.org APR-CL as primality proof
 Register FAQ Search Today's Posts Mark Forums Read

 2014-01-07, 19:26 #1 f1pokerspeed   Jun 2012 1528 Posts APR-CL as primality proof There are a variety of small candidates (300+ digits) that are suitable candidates for APR-CL (using YAFU, I can knock down a p372 in ~16 seconds, a reasonable speed increase vs. ECPP). However, I noticed that FactorDB doesn't accept APR-CL results! Would this be a feasible idea, such that double-checks would be accepted or something similar in order to ensure the primality of a number? Another point I should mention is that the N+/-1 tests are actually pretty annoying to make happen... considering that the numbers can actually be quite difficult to crack substantially - n1/3 is about 125 digits, so four or five medium sized ECM/P-1 factors are needed. Last fiddled with by f1pokerspeed on 2014-01-07 at 20:01
 2014-01-07, 21:16 #2 CRGreathouse     Aug 2006 5,987 Posts I thought APR-CL didn't generate certificates, so it wouldn't be useful in this context.
 2014-01-07, 21:28 #3 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32·101 Posts Times for the example p372 on my idle 4770K with the example p372: 9.5s yafu APR-CL (WraithX v1.0 I believe), no certificate 6.3s Pari 2.6.2 dev, APR-CL, no certificate 6.1s ecpp-dj, ECPP certificate parsable by factordb's verifier (though factordb's front end only takes Primo certificates) 4.8s WraithX's newest APR-CL v1.1, no certificate 4.3s Primo 4.1.0, 1 thread, certificate 1.5s Primo 4.1.0, 8 threads, certificate Revision 324 of yafu (the latest on svn) seems slower than my open source ECPP for this example, though WraithX's latest APR-CL released a couple weeks ago is faster. They're all slower than Primo, though Primo's big issue for automation or remote operation is the UI requirement. The problem IMO with APR-CL is that it offers no certificate, so there's no quick validation. If you don't have a certificate, you may as well run it through BPSW+Frobenius which can be done in single-digit milliseconds for these numbers. Throw in another 10 MR tests with random bases and we're at ~13ms. For APR-CL we have to trust the implementation and the computer it ran on. Arguably we have to trust that the person actually did any work at all and isn't a troll. For ECPP we have to trust the theorems (hard, but at least they've been out a long time and been oft-reviewed) and trust the verifier. I think verifiers are far easier to follow than the provers, and we have more than one available. Badly paraphrasing something I read from Marcel Martin, once you have a certificate, it doesn't matter if the prover was working, not working, or was a cat walking on the keyboard. Either the certificate is good or it isn't. Lastly, for the last 6 months or so, there have been some very busy people grabbing small numbers and proving them within a few hours of their appearing. Perhaps someone has managed to get a factordb <-> Primo automation setup. On a related subject, a couple months ago I had a couple computers grab small primes from factordb from 100 to 250 digits and then have my software create proofs. I found no numbers that didn't create a valid proof. Having a method to do a batch download of all the small numbers would make this more palatable vs. using the HTTP API using digit lengths and offsets. Last fiddled with by danaj on 2014-01-07 at 22:16 Reason: Add Pari time
 2014-01-07, 21:33 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·3,313 Posts On the backend, Factordb could also use gp APRCL implementation if it is "more trusted" Code: echo "isprime(" \$mynumber ",2)" |gp -q and catch 0 or 1 as the result.
 2014-01-07, 21:57 #5 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32×101 Posts Batalov, wouldn't that be basically factordb bumping up its threshold from 300 to some higher number? I thought factordb did something similar for numbers under 300 digits. I don't know the method used, but it doesn't export a certificate.
 2014-01-07, 22:49 #6 f1pokerspeed   Jun 2012 10610 Posts Hmmm... interesting. I would think though that the overhead of APR-CL is much smaller than having to verify a certificate.. considering that you have to upload the certificate to the server. Something to consider is that APR-CL is deterministic, therefore if a trusted implementation is found we can be absolutely sure that the result is true provided that the checking system also produces correct results. This means we could (technically) do away with certificates, that or use them as a second verification form (would this perhaps be redundant?). Although unlikely, there is a heuristic (Chen & Greene) for the BPSW test to have counterexamples - we don't truly know if BPSW is deterministic for this size of numbers. Therefore, we can't really say that BPSW - or the Frobenius test for that matter - is a sure-fire way to check if a number is prime. I would prefer a combination of APR-CL and ECPP - at least adding the APR-CL test would be another beneficial test that could help verify some numbers.
2014-01-08, 03:24   #7
CRGreathouse

Aug 2006

176316 Posts

Quote:
 Originally Posted by f1pokerspeed Although unlikely, there is a heuristic (Chen & Greene) for the BPSW test to have counterexamples - we don't truly know if BPSW is deterministic for this size of numbers. Therefore, we can't really say that BPSW - or the Frobenius test for that matter - is a sure-fire way to check if a number is prime.
It's all but certain that there are infinitely many BPSW pseudoprimes. We know there are none below 2^64.

 2014-01-08, 08:30 #8 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32·101 Posts I didn't mean to imply BPSW etc. counted as a proof -- I meant that if we're going to take someone's word for it ("Trust me, I'm from the NSA and I say this number is definitely prime!"), that is worth as little or less than running a suite of probabilistic tests. You have the following scenario: 1. random person on the API says "P372 passed APR-CL." 2. random person on the API says "P372 passed BPSW, Frobenius, and 10 random-base M-R tests." IMO the chance that the random person did something wrong or is lying to us is greater than the chance that the number really passed BPSW + other tests but is actually composite. So they're both equally meh in terms of proof. Some people would argue that the chances of misinformation are so high we shouldn't bother, and just stick with certificates which offer a reasonably fast way of making sure they're not wrong, plus we get a double check for only 1/20 - 1/300 th of the work. Verifying the certificate for the number above took the same computer 0.37s with either my verifier or Primo with one thread. Most of the work is independent between steps -- Primo with 8 threads indicated it was verified in 0.04s. The P18689 I recently finished took Primo a little under 3 months with 12 threads on a 3930K. Verification with Primo took ~6 hours (also 12 threads, otherwise idle machine). My single threaded verifier took 64 hours (on a different machine with other jobs running). That's a very long time, but much less than generating the proof.
2014-01-08, 12:07   #9
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·3·7·89 Posts

Quote:
 Originally Posted by CRGreathouse I thought APR-CL didn't generate certificates, so it wouldn't be useful in this context.
It doesn't. Sort of.

The code can emit a "certificate". But is is merely output values from
the various stages of the algorithm. Verifying such a "certificate"
takes as long as generating it in the first place. And it is a lot of data.

2014-01-08, 17:10   #10
CRGreathouse

Aug 2006

10111011000112 Posts

Quote:
 Originally Posted by R.D. Silverman It doesn't. Sort of. The code can emit a "certificate". But is is merely output values from the various stages of the algorithm. Verifying such a "certificate" takes as long as generating it in the first place. And it is a lot of data.
Right, that matches my understanding. Actually the way I usually think about it is that it has a certificate of length 0, and the verification is more expensive than the verification for ECPP or the like.

2014-01-09, 14:15   #11
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·3·7·89 Posts

Quote:
 Originally Posted by CRGreathouse Right, that matches my understanding. Actually the way I usually think about it is that it has a certificate of length 0, and the verification is more expensive than the verification for ECPP or the like.
The biggest problem with APR-CL (in my opinion) is knowing when
an implementation is correct. The final stages of the algorithm involve
dividing the candidate by a set of trial divisors. These divisors are
computed from Gauss (or Jacobi) sums.

Before entering the final stages the algorithm first subjects the candidate
to a series of prp tests. The first prp tests are the ordinary Miller-Rabin
(or Frobenius etc.) tests. Only if these tests show the number to be a
prp does the algorithm proceed. But once it does proceed it is virtually
certain that the number is prime. It then subjects the candidate to a
sequence of (what are essentially) prp tests over cyclotomic rings.

If a composite gets through the first stages (and I have never seen one
do this) it is finally trial-divided by the set of divisors.

Note now the chance for a programming error. If the number is prime,
and the set of trial divisors is computed INCORRECTLY, the number
will still be reported as prime, because none of the test divisors will
actually divide the number [i.e. this is true regardless of whether they
are correct].

I have never seen a composite get to the trial divisor stage and have
a factor found. I don't even know how to construct a test case which
would cause this to happen.

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Miscellaneous Math 40 2018-10-17 00:11 Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23 princeps Math 15 2012-04-02 21:49 marco_calabresi Information & Answers 3 2009-04-17 19:44 AntonVrba Math 96 2009-02-25 10:37

All times are UTC. The time now is 00:36.

Thu Sep 29 00:36:31 UTC 2022 up 41 days, 22:05, 0 users, load averages: 0.63, 0.85, 0.98