mpz_probab_prime_p and negative inputs
nisse at lysator.liu.se
Tue Mar 4 08:40:32 UTC 2014
bodrato at mail.dm.unipi.it writes:
>> 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
The isprime function in pari/gp gives
%7 = 1
%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
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.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel