xgcd bug

[Victor Shoup]

A user of NTL, which uses GMP, has found a bug in GMP's 
extended Euclidean algorithm.

The following program exhibits the bug.

----------------------------

#include <stdio.h>

#include <gmp.h>

main()
{
   mpz_t a, b, d, s, t;
   mpz_t t1, t2, t3;

   mpz_init(a);
   mpz_init(b);
   mpz_init(d);
   mpz_init(s);
   mpz_init(t);

   mpz_inp_str(a, stdin, 10);
   mpz_inp_str(b, stdin, 10);

   mpz_gcdext(d, s, t, a, b);

   fprintf(stdout, "a = ");
   mpz_out_str(stdout, 10, a);
   fprintf(stdout, "\n\n");
   fprintf(stdout, "b = ");
   mpz_out_str(stdout, 10, b);
   fprintf(stdout, "\n\n");

   fprintf(stdout, "d = ");
   mpz_out_str(stdout, 10, d);
   fprintf(stdout, "\n\n");
   fprintf(stdout, "s = ");
   mpz_out_str(stdout, 10, s);
   fprintf(stdout, "\n\n");
   fprintf(stdout, "t = ");
   mpz_out_str(stdout, 10, t);
   fprintf(stdout, "\n\n");

   /* check result */

   mpz_init(t1);
   mpz_init(t2);
   mpz_init(t3);

   mpz_mul(t1, a, s);
   mpz_mul(t2, b, t);
   mpz_add(t3, t1, t2);

   /* we should have t3 == d */

   fprintf(stdout, "d =? ");
   mpz_out_str(stdout, 10, t3);
   fprintf(stdout, "\n\n");
}

----------------------------

The bug only occurs on some inputs.
The only input that I know that triggers the bug is the following:

----------------------------


59920645307438980221005803724524637827300251654822384523300477678480104891292572792835391208763894723833707146488528393134606230081901027290513651007453961765652897859058228712461027983438802994103309315701848978161302047313137160006132626841608601409751131488670009662437615654507068754793067546147879251133

73829319816381062305606598578854535007237630621426149650903757993011007628882795598480270105355656970006715804302869566705915868574239210915129351455137304568435547279962769311474347777543630862319869465847872312646050881175252421341844833791337352408723930024676236055705368294682273588876110871556634526051

----------------------------

If you run the above program on the above inputs, the values
of s and t are wrong.

The platform where the bug occurs is:

  redhat linux 7.0
  gcc version 2.96 20000731
  Pentium II

I built gmp just using all the defaults.

I don't know if the bug occurs on other platforms.

Based on some other observations, it appears to me that the
bug already occurs in mpn_gcdext.
~

  -- Victor