mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2014-01-07, 19:26   #1
f1pokerspeed
 
Jun 2012

2·53 Posts
Default 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
f1pokerspeed is offline   Reply With Quote
Old 2014-01-07, 21:16   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

I thought APR-CL didn't generate certificates, so it wouldn't be useful in this context.
CRGreathouse is offline   Reply With Quote
Old 2014-01-07, 21:28   #3
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22·227 Posts
Default

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
danaj is offline   Reply With Quote
Old 2014-01-07, 21:33   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41·229 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2014-01-07, 21:57   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22·227 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2014-01-07, 22:49   #6
f1pokerspeed
 
Jun 2012

2×53 Posts
Default

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.
f1pokerspeed is offline   Reply With Quote
Old 2014-01-08, 03:24   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111011000012 Posts
Default

Quote:
Originally Posted by f1pokerspeed View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2014-01-08, 08:30   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22·227 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2014-01-08, 12:07   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-01-08, 17:10   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2014-01-09, 14:15   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

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 2018-10-17 00:11
500€ Reward for a proof for the Wagstaff primality test conjecture Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
Primality searches and primality successes marco_calabresi Information & Answers 3 2009-04-17 19:44
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37

All times are UTC. The time now is 21:58.

Mon Apr 12 21:58:40 UTC 2021 up 4 days, 16:39, 1 user, load averages: 3.85, 3.48, 3.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.