5 ms·
It's pretty easy. There are ways to test primarily such that constructing a counterexample would be an important mathematical result. https://en.wikipedia.org/
by alextgordon 11y ago
It's pretty easy. There are ways to test primarily such that constructing a counterexample would be an important mathematical result.
https://en.wikipedia.org/wiki/Baillie–PSW_primality_test https://en.wikipedia.org/wiki/Baillie–PSW_primality_test
> The power of the Baillie-PSW test comes from the fact that these lists of strong Fermat pseudoprimes and strong Lucas pseudoprimes have no known overlap. There is even evidence that the numbers in these lists tend to be different kinds of numbers.
- CamperBob2 11y agoIt might be "easy" but is it quick enough to be tolerated as part of a build?
- lorenzhs 11y agoThe primality test of the original number using gp that archgoon posted takes 6ms on my Sandy Bridge laptop, that's plenty fast. (The new number takes a minute to check, though, so that might really be too long)
- sdhsdh 11y agoMaxima's primep takes 360ms on the 1024-bit one for me, so seems quick enough to stick into the build. It sounds like the chance if it passing the test is around 10^-15 using the default values; which seems sufficient for a build test which is run many times.
- anderskaseorg 11y agoA primality certificate could be included that allows the prime to be verified quickly during the build. This certificate for the 2048-bit prime took 90 seconds to generate, and can be verified in 3 seconds. http://web.mit.edu/andersk/Public/socat-prime.pl http://web.mit.edu/andersk/Public/socat-prime.pl https://en.wikipedia.org/wiki/Primality_certificate https://en.wikipedia.org/wiki/Primality_certificate
- jldugger 11y agoIf this the alternative, it very well might be.
- leni536 11y agoJust build your sensitive hard coded primes in a separate object file. It rarely needs updating.