The Laws of Cryptography:
The Extended GCD Program
With Debug Output

by Neal R. Wagner

NOTE: This site is obsolete. See book draft (in PDF):

For reference, here is the program again:

```
// ExtGCD: Extended GCD (long version)
public class ExtGCD {

public static long[] GCD(long x, long y) { // assumes not 0 or negative
long[] u = new long[3];
long[] v = new long[3];
long[] t = new long[3];
// at all stages, if w is any of the 3 vectors u, v or t, then
//   x*w[0] + y*w[1] = w[2]  (this is verified by "check" below)
// u = (1, 0, u); v = (0, 1, v);
u[0] = 1; u[1] = 0; u[2] = x; v[0] = 0; v[1] = 1; v[2] = y;
System.out.println("q\tu[0]\tu[1]\tu[2]\tv[0]\tv[1]\tv[2]");

while (v[2] != 0) {
long q = u[2]/v[2];
// t = u - v*q;
t[0] = u[0] -v[0]*q; t[1] = u[1] -v[1]*q; t[2] = u[2] -v[2]*q; check(x, y, t);
// u = v;
u[0] = v[0]; u[1] = v[1]; u[2] = v[2]; check(x, y, u);
// v = t;
v[0] = t[0]; v[1] = t[1]; v[2] = t[2]; check(x, y, v);
System.out.println(q + "\t"+ u[0] + "\t" + u[1] + "\t" + u[2] +
"\t"+ v[0] + "\t" + v[1] + "\t" + v[2]);
}
return u;
}

public static void check(long x, long y, long[] w) {
if (x*w[0] + y*w[1] != w[2]) {
System.out.println("*** Check fails: " + x + " " + y);
System.exit(1);
}
}

public static void main(String[] args) {
long[] u = new long[3];
long x = Long.parseLong(args[0]);
long y = Long.parseLong(args[1]);
u = ExtGCD.GCD(x, y);
System.out.println("\ngcd(" + x + ", " + y + ") = " + u[2]);
System.out.println("(" + u[0] + ")*" + x + " + " +
"(" + u[1] + ")*" + y + " = " + u[2]);
}
}
```
Here is a sample run (with a few extra tabs inserted by hand):

```% java ExtGCD 123456789 987654321
q               u[0]    u[1]    u[2]            v[0]            v[1]            v[2]

0               0       1       987654321       1               0               123456789
8               1       0       123456789       -8              1               9
13717421        -8      1       9               109739369       -13717421       0

gcd(123456789, 987654321) = 9
(-8)*123456789 + (1)*987654321 = 9

% java ExtGCD 1122334455667788 99887766554433
q               u[0]            u[1]            u[2]            v[0]            v[1]            v[2]

11              0               1               99887766554433  1               -11             23569023569025
4               1               -11             23569023569025  -4              45              5611672278333
4               -4              45              5611672278333   17              -191            1122334455693
4               17              -191            1122334455693   -72             809             1122334455561
1               -72             809             1122334455561   89              -1000           132
8502533754      89              -1000           132             -756725504178   8502533754809   33
4               -756725504178   8502533754809   33              3026902016801   -34010135020236 0

gcd(1122334455667788, 99887766554433) = 33
(-756725504178)*1122334455667788 + (8502533754809)*99887766554433 = 33

% java ExtGCD 384736948574637 128475948374657
q       u[0]            u[1]            u[2]            v[0]            v[1]            v[2]

2       0               1               128475948374657 1               -2              127785051825323
1       1               -2              127785051825323 -1              3               690896549334
184     -1              3               690896549334    185             -554            660086747867
1       185             -554            660086747867    -186            557             30809801467
21      -186            557             30809801467     4091            -12251          13080917060
2       4091            -12251          13080917060     -8368           25059           4647967347
2       -8368           25059           4647967347      20827           -62369          3784982366
1       20827           -62369          3784982366      -29195          87428           862984981
4       -29195          87428           862984981       137607          -412081         333042442
2       137607          -412081         333042442       -304409         911590          196900097
1       -304409         911590          196900097       442016          -1323671        136142345
1       442016          -1323671        136142345       -746425         2235261         60757752
2       -746425         2235261         60757752        1934866         -5794193        14626841
4       1934866         -5794193        14626841        -8485889        25412033        2250388
6       -8485889        25412033        2250388         52850200        -158266391      1124513
2       52850200        -158266391      1124513         -114186289      341944815       1362
825     -114186289      341944815       1362            94256538625     -282262738766   863
1       94256538625     -282262738766   863             -94370724914    282604683581    499
1       -94370724914    282604683581    499             188627263539    -564867422347   364
1       188627263539    -564867422347   364             -282997988453   847472105928    135
2       -282997988453   847472105928    135             754623240445    -2259811634203  94
1       754623240445    -2259811634203  94              -1037621228898  3107283740131   41
2       -1037621228898  3107283740131   41              2829865698241   -8474379114465  12
3       2829865698241   -8474379114465  12              -9527218323621  28530421083526  5
2       -9527218323621  28530421083526  5               21884302345483  -65535221281517 2
2       21884302345483  -65535221281517 2               -53295823014587 159600863646560 1
2       -53295823014587 159600863646560 1               28475948374657 -384736948574637 0

gcd(384736948574637, 128475948374657) = 1
(-53295823014587)*384736948574637 + (159600863646560)*128475948374657 = 1
```

Revision date: 2002-01-02. (Please use ISO 8601, the International Standard.)