CORRECTED Request mild improvement to mpz_gcdext

[abbott]

Hi,

!!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 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, 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_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;
}