CORRECTED Request mild improvement to mpz_gcdext

abbott abbott at
Tue Sep 29 13:13:40 CEST 2009


!!IMPORTANT!! Corrected version of message sent about an hour ago!

This is not really a bug.  It is possible to give better guarantees
about the values computed by mpz_gcdext.  In particular the cofactors (called
S and T in the documentation) can satisfy
   2*abs(S) <= abs(B)/G
   2*abs(T) <= abs(A)/G
with the only exceptions being when A or B is zero or abs(A) == abs(B).
The result is proved in Thm 4.3 in Shoup's book "A Computational Introduction
to Number Theory and Algebra".

I would like this improvement, though it is hardly essential.
Apparently gmp-4.2.4 happened to find the smallest cofactors whereas
gmp-4.3.1 does not.  The change in behaviour seems to be platform
independent (between MacOSX & Ubuntu, both on Intel processors).

Build info:
  ./configure --enable-cxx
  gcc version 4.0.1 (Apple Inc. build 5490)
  Darwin  Darwin Kernel Version 9.8.0: Wed Jul 15 16:55:01 PDT 2009; root:xnu-1228.15.4~1/RELEASE_I386 i386

Thanks, and sorry for the wrong message sent earlier
John Abbott
--- C source code for a case where cofactors are "too large"
--- This example is for the pair (257,255), but there are many others
--- e.g. (256,246)  gives gcd=2 and smallest cofactors are (-49,51).

#include <stdio.h>
#include "gmp.h"

int main()
  mpz_t A,B,S,T,G;
  mpz_gcdext(G,S,T,A,B); /* sets S= 128, T=-129 */
           /* could have instead S=-127, T= 128 */
  mpz_out_str(stdout, 10, S);
  mpz_out_str(stdout, 10, T);
  return 0;

More information about the gmp-bugs mailing list