20180730, 18:58  #1 
Nov 2017
Karlsruhe, Germany
31 Posts 
Good numbers to verify primality check
Hi, I'm currently writing code to play around with truncatable primes. Since some get fairly large I naturally want I decently fast and correct primality check.
Now I want to use some basic unit tests to make sure my method works. So what numbers could I throw at it? (Note I use GMP, so primes over 2^64 are possible) My idea was to test increasingly larger primes, and "tough" nonprimes or composite numbers which have two prime factors that are very close to eachother. While finding primes isn't that hard, how could I find good numbers for the negative test cases? P.S.: I hope that's the right subforum :D P.P.S.: Greetings @kimwalisch ;) Last fiddled with by BrainStone on 20180730 at 19:04 
20180730, 19:18  #2 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 

20180730, 19:22  #3 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
386_{16} Posts 
There are a number of lists of pseudoprimes to various tests here: Pseudoprime Statistics, Tables, and Data. If your test uses a base2 Fermat or MillerRabin test as many do, then using one of the Feitsma/Galway big databases is usual. They allow you to relatively quickly test *all* 64bit pseudoprimes. If your Fermat/MR test works properly, this just gives you the interesting remainders.
For larger inputs, it isn't entirely clear. I would suggest some of the large multibase Carmichael numbers, such as found in this test: 17pseudoprimes.t on line 291332. The other thing I have done is random input testing. Loop forever doing:  generate a random Nbit integer for some value of N you're testing  run your test  run another software's test  die verbosely if they do not match Run that for a few hours. Of course you want all those steps to be fast. To give you some idea, a little test I just did takes under 10 microseconds for N=128, which includes generating a random 128bit input followed by a deterministic primality test. Considering your primality test doesn't seem to really be the point of your exercise, maybe you could just use some existing code. WraithX has some nice portable BPSW code using GMP. I have some that is faster but isn't as amenable to plugging in. Paul Underwood has some GMP code using his test. There are plenty of other tests with GMP code available, and there is GMP code for primality proving using either BLS75, APRCL, or ECPP (the APRCL library from WraithX is again really easy to add to any project). 
20180730, 20:27  #4  
Nov 2017
Karlsruhe, Germany
1F_{16} Posts 
Quote:
I feel stupid now xD Yup that's a good idea. Twin primes might be a good idea as that makes sure the code doesn't stop one number short. Quote:
Thanks for these resources! Quote:
It surely is not, however I currently just use the plain old trial division up to the sqrt of the number to check. So I want to use some unit tests that when I later start to optimize the check that I don't accidentally break my code. 

20180730, 21:02  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
Just don't bring up another Fermat's little theorem equivalent (happened at least once on here). Last fiddled with by science_man_88 on 20180730 at 21:03 

20180730, 22:08  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
Trial division is going to be painfully slow for >64bit inputs.
If you have GMP, you could use the builtin mpz_probab_prime_p(n,trials) with something like 20+ for the number of trials. That's by far the easiest method, although not the fastest and that function has some known issues (that are mostly worked around by using a high number of trials). It should be decently fast for most composites regardless of the number of trials requested (it includes a bit of trial division, and most composites will get caught after the Fermat pretest or the first MR base, making the number of trials requested moot for almost all nonprime inputs). There is still a possiblity of it declaring a composite input to be prime, but with 20+ trials I wouldn't be too concerned unless you're relying on the result to be correct for adversarialgenerated inputs. If it turns out this is actually a bottleneck, you could look into other methods at that point. 
20180730, 22:33  #7  
Nov 2017
Karlsruhe, Germany
11111_{2} Posts 
Quote:
I know trial division is painfully slow. And from my tests \(mpz_probab_prime_p(n,trials)\) is decently fast, though I don't like probalistic results. From my research I stumbled across the AKS algorithm and even found some C implementations of it. When I get at the point of the trial division being too slow, I'll give AKS a shot. If anyone's interested I can post a link to my GitHub project. Nothing serious, just me messing around with primes and working a little with my good old friend C++, so I stay in practice. 

20180730, 22:50  #8 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×11×41 Posts 
AKS is included in MathPrimeUtil and MathPrimeUtilGMP if you'd like. The latter is orders of magnitude faster than I've seen anywhere else. It's still extraordinarily slow compared to other deterministic methods such as APRCL and ECPP, as mentioned on the Wikipedia page.
<opinion> But it's all fun to program, and AKS isn't terribly hard, but does require very careful reading of the paper and lots of unit testing. There are many broken implementations out there. My personal belief is that because of that, in practice AKS is less reliable than a well written and researched probabilistic test. This says nothing about the theory, just that nearly half the implementations I've found are broken in some way, which isn't good. </opinion> Last fiddled with by danaj on 20180730 at 22:51 
20180731, 21:14  #9  
Nov 2017
Karlsruhe, Germany
31 Posts 
Quote:
Yeah. I stumbled across the second and was thinking about updating the implementation to C++. Aka making use of the GMPC++ Wrapper GMPXX. I might also look into the other algorithms. Also I finally sussed out all compiling issues under Windows by using the fork MPIR. Took way too long... 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How do firsttime and doublecheck primality tests work?  ChemicalCat59  Information & Answers  9  20170323 11:14 
PRIMALITY PROOF for Wagstaff numbers!  AntonVrba  Math  96  20090225 10:37 
How to check completed numbers?  Ferdy  PrimeNet  1  20090112 19:33 
Need to verify if big numbers are integers  Crook  Software  11  20070613 13:41 
Two Primality tests for Fermat numbers  T.Rex  Math  2  20040911 07:26 