CORRECTED Request mild improvement to mpz_gcdext
abbott
abbott at dima.unige.it
Tue Sep 29 13:13:40 CEST 2009
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;
}
More information about the gmp-bugs
mailing list