Good numbers to verify primality check

BrainStone · 2018-07-30, 18:58

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" non-primes 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 ;)

science_man_88 · 2018-07-30, 19:18

Quote:

Originally Posted by BrainStone

While finding primes isn't that hard, how could I find good numbers for the negative test cases?

are we really that encephalithic ? multiply the close primes together in pairs.

danaj · 2018-07-30, 19:22

There are a number of lists of pseudoprimes to various tests here: Pseudoprime Statistics, Tables, and Data. If your test uses a base-2 Fermat or Miller-Rabin test as many do, then using one of the Feitsma/Galway big databases is usual. They allow you to relatively quickly test *all* 64-bit pseudoprimes. If your Fermat/M-R 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 multi-base Carmichael numbers, such as found in this test: 17-pseudoprimes.t on line 291-332.

The other thing I have done is random input testing. Loop forever doing:
- generate a random N-bit 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 128-bit 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, APR-CL, or ECPP (the APR-CL library from WraithX is again really easy to add to any project).

BrainStone · 2018-07-30, 20:27

Quote:

Originally Posted by science_man_88

are we really that encephalithic ? multiply the close primes together in pairs.

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:

Originally Posted by danaj

There are a number of lists of pseudoprimes to various tests here: Pseudoprime Statistics, Tables, and Data. If your test uses a base-2 Fermat or Miller-Rabin test as many do, then using one of the Feitsma/Galway big databases is usual. They allow you to relatively quickly test *all* 64-bit pseudoprimes. If your Fermat/M-R test works properly, this just gives you the interesting remainders.

Thanks for these resources!

Quote:

Originally Posted by danaj

Considering your primality test doesn't seem to really be the point of your exercise, ...

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.

science_man_88 · 2018-07-30, 21:02

Quote:

Originally Posted by BrainStone

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.

Don't feel bad everyone needs encephalithiasis ( crushing of brain stones) every now and then. You're screen name just helps with that joke ( brainstone= encephalith) .

Just don't bring up another Fermat's little theorem equivalent (happened at least once on here).

danaj · 2018-07-30, 22:08

Trial division is going to be painfully slow for >64-bit inputs.

If you have GMP, you could use the built-in 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 pre-test or the first M-R base, making the number of trials requested moot for almost all non-prime 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 adversarial-generated inputs.

If it turns out this is actually a bottleneck, you could look into other methods at that point.

BrainStone · 2018-07-30, 22:33

Quote:

Originally Posted by danaj

Trial division is going to be painfully slow for >64-bit inputs.

If you have GMP, you could use the built-in 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 pre-test or the first M-R base, making the number of trials requested moot for almost all non-prime 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 adversarial-generated inputs.

If it turns out this is actually a bottleneck, you could look into other methods at that point.

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.

danaj · 2018-07-30, 22:50

AKS is included in Math-Prime-Util and Math-Prime-Util-GMP 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 APR-CL 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>

BrainStone · 2018-07-31, 21:14

Quote:

Originally Posted by danaj

AKS is included in Math-Prime-Util and Math-Prime-Util-GMP if you'd like.

Yeah. I stumbled across the second and was thinking about updating the implementation to C++. Aka making use of the GMP-C++ 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...

2018-07-30, 18:58	#1
BrainStone 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" non-primes 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 2018-07-30 at 19:04

2018-07-30, 22:50	#8
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2²·227 Posts	AKS is included in Math-Prime-Util and Math-Prime-Util-GMP 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 APR-CL 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 2018-07-30 at 22:51

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How do first-time and double-check primality tests work?	ChemicalCat59	Information & Answers	9	2017-03-23 11:14
PRIMALITY PROOF for Wagstaff numbers!	AntonVrba	Math	96	2009-02-25 10:37
How to check completed numbers?	Ferdy	PrimeNet	1	2009-01-12 19:33
Need to verify if big numbers are integers	Crook	Software	11	2007-06-13 13:41
Two Primality tests for Fermat numbers	T.Rex	Math	2	2004-09-11 07:26

2018-07-30, 19:22	#3
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2²·227 Posts	There are a number of lists of pseudoprimes to various tests here: Pseudoprime Statistics, Tables, and Data. If your test uses a base-2 Fermat or Miller-Rabin test as many do, then using one of the Feitsma/Galway big databases is usual. They allow you to relatively quickly test all 64-bit pseudoprimes. If your Fermat/M-R 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 multi-base Carmichael numbers, such as found in this test: 17-pseudoprimes.t on line 291-332. The other thing I have done is random input testing. Loop forever doing: - generate a random N-bit 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 128-bit 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, APR-CL, or ECPP (the APR-CL library from WraithX is again really easy to add to any project).

2018-07-30, 22:08	#6
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2²·227 Posts	Trial division is going to be painfully slow for >64-bit inputs. If you have GMP, you could use the built-in 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 pre-test or the first M-R base, making the number of trials requested moot for almost all non-prime 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 adversarial-generated inputs. If it turns out this is actually a bottleneck, you could look into other methods at that point.