mersenneforum.org Good numbers to verify primality check
 Register FAQ Search Today's Posts Mark Forums Read

 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, 19:18   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

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.

 2018-07-30, 19:22 #3 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38616 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, 20:27   #4
BrainStone

Nov 2017
Karlsruhe, Germany

1F16 Posts

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.

2018-07-30, 21:02   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

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).

Last fiddled with by science_man_88 on 2018-07-30 at 21:03

 2018-07-30, 22:08 #6 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2·11·41 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.
2018-07-30, 22:33   #7
BrainStone

Nov 2017
Karlsruhe, Germany

111112 Posts

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.

 2018-07-30, 22:50 #8 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2×11×41 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. 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. Last fiddled with by danaj on 2018-07-30 at 22:51
2018-07-31, 21:14   #9
BrainStone

Nov 2017
Karlsruhe, Germany

31 Posts

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...

 Similar Threads Thread Thread Starter Forum Replies Last Post ChemicalCat59 Information & Answers 9 2017-03-23 11:14 AntonVrba Math 96 2009-02-25 10:37 Ferdy PrimeNet 1 2009-01-12 19:33 Crook Software 11 2007-06-13 13:41 T.Rex Math 2 2004-09-11 07:26

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

Sat Jul 4 22:36:15 UTC 2020 up 101 days, 20:09, 1 user, load averages: 1.47, 1.29, 1.20

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.