mpz_probab_prime_p and negative inputs

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> Ciao,

>> nisse at lysator.liu.se (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.

I think the conventions for the *particular* ring Z are a bit different
from a general ring (where, for a start, you don't have an obvious
division into positive and negative elements).

I can't resist searching for authoritative definitions:

Knuth's TAoCP (1.2.1, exercise 5) says "A prime number is an integer > 1
that has no exact divisors other than 1 and itself".

Graham, Knuth, and Patashnik's "Concrete mathematics" says "A positive
integer p is called prime if it has just two divisors, namely 1 and p".
Hence no clear guidance on when, if ever, negative integers are called
"prime".

The isprime function in pari/gp gives 

  ? isprime(29)
  %7 = 1
  ? isprime(-29)
  %8 = 0

Cohen's "A course in computational number theory" doesn't define
explicitly what "prime number" means, as far as I can find, but I think
the term is used in a way excluding negative numbers. For example (page
5), "... when N = p is a prime, and then R = F_p the finite field with p
elements.", where it makes no sense with a negative number of elements.

The prime number FAQ
(http://primes.utm.edu/notes/faq/negative_primes.html) answers the
question "Can negative numbers be prime?" as follows:

  Answer one: No.
  
  By the usual definition of prime for integers, negative integers can not
  be prime.
  
  By this definition, primes are integers greater than one with no
  positive divisors besides one and itself. Negative numbers are excluded.
  In fact, they are given no thought.

  Answer two: Yes

  [followed by a discussion on units and associates]

  Answer three: It doesn't matter

  In more general number fields the confusion above disappears. That is
  because most of these fields are not principal ideal domains and
  primes then are represented by ideals, not individual elements. Looked
  at this way (-3), the set of all multiples of -3, is the same ideal as
  (3), the set of multiples of 3.

  -3 and 3 then generate exactly the same prime ideal. 

I think it would make sense for GMP to follow answer one and the "usual
definition", and I was a bit suprprised to find that it doesn't. I don't
have a strong opinion, though. For now, I think I'll consider the
behaviour for negative inputs undocumented, and I see no urgent need for
any changes. If the function is added to mini-gmp (any opinions on
that?), it should follow gmp's behaviour, whatever that is.

>>   1. Document current behaviour.
>
> We may write "Determine whether n is a prime element in the ring Z"

If the current behaviour really is desired, I think the docs should be a
bit more explicit about it.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.