Request mild improvement to mpz_gcdext

[abbott]

Hi,

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 abbottpb.dima.unige.it  Darwin Kernel Version 9.8.0: Wed Jul 15 16:55:01 PDT 2009; root:xnu-1228.15.4~1/RELEASE_I386 i386

Thanks,
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_init_set_si(A,257);
  mpz_init_set_si(B,255);
  mpz_init(S);
  mpz_init(T);
  mpz_init(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);
  printf("\n");
  mpz_out_str(stdout, 10, T);
  printf("\n");
  return 0;
}