mpz_probab_prime_p and negative inputs

Torbjorn Granlund tg at
Mon Mar 3 22:08:42 UTC 2014

nisse at (Niels Möller) writes:

  It seems mpz_probably_prime_p considers negated primes to also be prime.
  E.g, for n == -29 it returns 2, meaning "definitely prime".
  Mathematically, I think -29 is usually considered neither prime, nor
  composite (its prime factorization is -1 * 29 and the "unit" factor -1
  kind-of doesn't count, since *if* we count it as a "real" factor, that
  breaks uniqueness of factorization: we get additional possible
  factorizations like -29 = (-1)^3 29, and 29 = (-1)^2 29.
In UFDs one disregards units, which is exactly what is done here.

  The behaviour is also a bit inconsistent with mpz_nextprime, which for
  input -29 returns the "standard" prime 2, not -23 which is the next
  larger number which is considered prime by mpz_probably_prime_p.
Oh, well.  Not sure if that's worth changing.

  The result of mpz_probably_prime_p for negative inputs is not
  clearly documented.
  Some options:
  1. Document current behaviour.
  2. Explicitly document that negative inputs are not allowed.
  3. Change mpz_probably_prime_p to consider all integers < 2 to be
  I'd lean towards (3), but I don't know if anyone depends on the current
I think the current behaviour makes sense, and people might reply on it,
so please don't change it.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list