20140107, 19:26  #1 
Jun 2012
152_{8} Posts 
APRCL as primality proof
There are a variety of small candidates (300+ digits) that are suitable candidates for APRCL (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 APRCL results!
Would this be a feasible idea, such that doublechecks 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  n^{1/3} is about 125 digits, so four or five medium sized ECM/P1 factors are needed. Last fiddled with by f1pokerspeed on 20140107 at 20:01 
20140107, 21:16  #2 
Aug 2006
5,987 Posts 
I thought APRCL didn't generate certificates, so it wouldn't be useful in this context.

20140107, 21:28  #3 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}·101 Posts 
Times for the example p372 on my idle 4770K with the example p372:
9.5s yafu APRCL (WraithX v1.0 I believe), no certificate 6.3s Pari 2.6.2 dev, APRCL, no certificate 6.1s ecppdj, ECPP certificate parsable by factordb's verifier (though factordb's front end only takes Primo certificates) 4.8s WraithX's newest APRCL 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 APRCL 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 APRCL 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 singledigit milliseconds for these numbers. Throw in another 10 MR tests with random bases and we're at ~13ms. For APRCL 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 oftreviewed) 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 20140107 at 22:16 Reason: Add Pari time 
20140107, 21:33  #4 
"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 
20140107, 21:57  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}×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.

20140107, 22:49  #6 
Jun 2012
106_{10} Posts 
Hmmm... interesting. I would think though that the overhead of APRCL 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 APRCL 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 surefire way to check if a number is prime. I would prefer a combination of APRCL and ECPP  at least adding the APRCL test would be another beneficial test that could help verify some numbers. 
20140108, 03:24  #7  
Aug 2006
1763_{16} Posts 
Quote:


20140108, 08:30  #8 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}·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 APRCL." 2. random person on the API says "P372 passed BPSW, Frobenius, and 10 randombase MR 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. 
20140108, 12:07  #9  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·3·7·89 Posts 
Quote:
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. 

20140108, 17:10  #10 
Aug 2006
1011101100011_{2} Posts 
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.

20140109, 14:15  #11  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·3·7·89 Posts 
Quote:
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 MillerRabin (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 trialdivided 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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime numbers test primality  with proof written in invisible ink  Godzilla  Miscellaneous Math  40  20181017 00:11 
500€ Reward for a proof for the Wagstaff primality test conjecture  Tony Reix  Wagstaff PRP Search  7  20131010 01:23 
Proof of Primality Test for Fermat Numbers  princeps  Math  15  20120402 21:49 
Primality searches and primality successes  marco_calabresi  Information & Answers  3  20090417 19:44 
PRIMALITY PROOF for Wagstaff numbers!  AntonVrba  Math  96  20090225 10:37 