# Is Z.nextprime in zarith the NEXT probable prime?

I’m dabbling with ocaml (once again) and use Project Euler as a playground.
Since I might happen upon “large” numbers while poking the problems, I am using zarith.

The documentation on zarith latest · OCaml Package states:

Returns the next prime greater than the argument. The result is only prime with very high probability.

I understand that `Z.nextPrime` is really `Z.next_probable_prime`. I could not find more details about the “next” part, though: Is it possible for `Z.nextprime` to miss primes? If so, does anybody know what the smallest missed prime would be?

Curious,
s.

`Z.nextPrime` internally calls out[1] to `mpz_nextprime`[2] which internally just increments up from your current number until it finds a number that passes the Miller-Rabin probabilistic primailty check.

The relevant property of the Miller Rabin test here is that it will never produce a false negative – if it returns false (that is, states that a number is not prime), then due to how the test works, that number must be composite. (There is, on the other hand, a chance of false positives, where it may state that a result is prime when it is in fact composite).

Anyway, this means that `nextprime` will never miss primes. It may return “early” in its search and produce a value that is not-prime, but in that case, you can be certain that this value is smaller than the next prime.

2 Likes

Thank you for confirming my suspicions. My math and C skills have gotten rusty over the years