CODEWITHSUNDEEP
primesraku
Sean
Sean

Reputation: 29790

How reliable is Raku's is-prime function?

The documentation for Raku's is-prime function says the following:

Returns True if this Int is known to be a prime, or is likely to be a prime based on a probabilistic Miller-Rabin test.

Returns False if this Int is known not to be a prime.

I do a lot of code golfing in Raku, and it's very convenient for many problems to have a built-in way to test for primality. For example, to obtain a lazy infinite sequence of prime numbers:

my @primes = grep &is-prime, ^Inf;

However, occasionally I've been bothered that the documentation says something other than "Returns True if this Int is prime, and False otherwise." In fact, the wording seems to admit of possible false positives or false negatives.

How reliable is is-prime, really?

Upvotes: 9

Views: 451

Answers (2)

deamentiaemundi
deamentiaemundi

Reputation: 5525

According to its source (rakudo-star-2023.02-01.tar.gz, SHA3-256 digest: a924ebcbb78f979511331ed2a841cba88529f6b43a13c9d04692a93fee93672a) it uses LibTomMath's mp_prime_is_prime function. If compiled out of the box for anything larger than 8-bit architectures, it uses the following tests for input N and t = 0:

  • is N even
  • is N a perfect square
  • trial division with the first 255 primes
  • two rounds of Miller-Rabin with bases two and three respectively
  • a strong Lucas test with the Selfridge parameters D = 5, P = 1 and Q = (1-D)/4
  • one Miller-Rabin test with a random base b <= N

For 8-bit architectures (be aware that LTM stopped supporting 8-bit!) it replaces the strong Lucas test with a Frobenius test written by Paul Underwood.

This function is safe for cryptographic purposes.

It has a compile-time variant to use Miller-Rabin tests only which is not, I repeat: NOT safe for cryptographic purposes! It uses MR tests with bases two and three after all of the preliminaries described in the list above and one MR test with a random base.

With input N <= 3317044064679887385961981 and t < 0 it uses the findings of Sorenson and Webster for a deterministic prime test up to and including 3317044064679887385961981.

(Note for transparency: I am the author of the described BPSW enhancement of mp_prime_is_prime in LibTomMath)

This function is a bit old (no 8-bit support anymore) and convoluted. There is a new pull request that replaces the strong Lucas test with an extra strong Lucas test with Baillie's parameters P = 3 and Q = 1 and the Frobenius-Underwood test has been made a compile time addition, placed after the extra strong Lucas test.

I don't know how Raku handles 3rd-party updates but the author of MoarVM is a regular at LibTomMath.

Upvotes: 4

Jack Gifford
Jack Gifford

Reputation: 300

Raku uses the Miller-Rabin primality test, a test where a potential prime is checked if it's likely to be prime in different bases, and the more bases it's likely to be prime in, the more likely it is to be actually prime. This has an accuracy of at least 1 − 4−k, where k is the number of iterations run. I wasn't able to find the actual number of iterations that Raku runs, probably very many. But regardless, the general sentiment around the Miller-Rabin primarily test is that it's good enough for practical usage, but don't use it for anything that is cryptographic or otherwise security-related.

I would personally say good enough for code golf, - it's a language feature, and if people wanted to be picky about it, then you could write your own version of Raku which is completely identical except with the primality test replaced with a true prime test.

Upvotes: 10

Related Questions