Request mild improvement to mpz_gcdext

abbott abbott at
Tue Sep 29 11:59:17 CEST 2009


This is not really a bug.  It is possible to give (slightly) 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)
   2*abs(T) <= abs(A)
with the only exceptions being when both A and B lie in the set {-1,0,1}.
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 smaller 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

John Abbott
--- C source code for a case where cofactors are "too large"
#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