Bug#744302: mpz_invert yields wrong result

[Benjamin Eltzner]

Source: gmp
Version: 2:6.0.0+dfsg-2
Severity: important

Dear Maintainer,

while running the tests for the flint library I am working on packaging,
I found that mpz_invert yields a wrong result on a certain set of input
values. Essentially,

mpz_init(a);
mpz_init(b);
mpz_init(c);
mpz_set_str(a, "11150372594073014712837494417038049594572792", 10)
mpz_set_si(b, -1)
int x = mpz_invert(c, a, b)

yields c = 0 (ok) and x = 1 (not ok).

The documentation states::

int mpz_invert (mpz t rop, const mpz t op1, const mpz t op2)
  Compute the inverse of op1 modulo op2 and put the result in rop. If
  the inverse exists, the return value is non-zero and rop will satisfy
  0 < rop < |op2|. If an inverse doesn’t exist the return value is zero
  and rop is undefined. The behaviour of this function is undefined when
  op2 is zero.

As 11150372594073014712837494417038049594572792 mod -1 = 0
the inverse does not exist, and the return value should be zero. The
fact that !(rop > 0) is actually a clear sign that no inverse exists and
rop is thus undefined. Therefore the return value is clearly an error.

I have no idea, whether this bug is in the package or in the upstream
library. If it concerns upstream, I would be very glad if you forwarded
it and set me to CC.

Cheers, Benjamin


-- System Information:
Debian Release: jessie/sid
  APT prefers unstable
  APT policy: (600, 'unstable'), (1, 'experimental')
Architecture: amd64 (x86_64)
Foreign Architectures: i386

Kernel: Linux 3.13-1-amd64 (SMP w/2 CPU cores)
Locale: LANG=de_DE.UTF-8, LC_CTYPE=de_DE.UTF-8 (charmap=UTF-8)
Shell: /bin/sh linked to /bin/dash