mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2018-07-30, 18:58   #1
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default 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
BrainStone is offline   Reply With Quote
Old 2018-07-30, 19:18   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by BrainStone View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-07-30, 19:22   #3
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38616 Posts
Default

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).
danaj is offline   Reply With Quote
Old 2018-07-30, 20:27   #4
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

1F16 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 View Post
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 View Post
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.
BrainStone is offline   Reply With Quote
Old 2018-07-30, 21:02   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by BrainStone View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-07-30, 22:08   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2018-07-30, 22:33   #7
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

111112 Posts
Default

Quote:
Originally Posted by danaj View Post
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.
BrainStone is offline   Reply With Quote
Old 2018-07-30, 22:50   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×11×41 Posts
Default

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
danaj is offline   Reply With Quote
Old 2018-07-31, 21:14   #9
BrainStone
 
BrainStone's Avatar
 
Nov 2017
Karlsruhe, Germany

31 Posts
Default

Quote:
Originally Posted by danaj View Post
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...
BrainStone is offline   Reply With Quote
Reply

Thread Tools


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

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

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