mpz_probab_prime_p and negative inputs

bodrato at bodrato at
Tue Mar 4 07:23:37 UTC 2014


Il Lun, 3 Marzo 2014 11:08 pm, Torbjorn Granlund ha scritto:
> nisse at (Niels Möller) writes:
>   It seems mpz_probably_prime_p considers negated primes to also be prime.

I agree they are.
On rings I usually take the following definition for primes:
p is prime if and only if p is not a unit, and p|ab implies p|a or p|b.

> In UFDs one disregards units, which is exactly what is done here.

This also means that (-3)*(-2) is the same prime factorization as 2*3.

>   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.

It'd give a nice way to obtain mpz_prevprime :-)

>   1. Document current behaviour.

We may write "Determine whether n is a prime element in the ring Z"

And document that mpz_nextprime "Set rop to the next positive prime number
greater than op."



More information about the gmp-devel mailing list