代码来自维基百科的。

扩展欧几里得算法程序：

function extended_gcd(a, b)    s := 0;    old_s := 1    t := 1;    old_t := 0    r := b;    old_r := a    while r ≠ 0        quotient := old_r div r        (old_r, r) := (r, old_r - quotient * r)        (old_s, s) := (s, old_s - quotient * s)        (old_t, t) := (t, old_t - quotient * t)    output "Bézout coefficients:", (old_s, old_t)    output "greatest common divisor:", old_r    output "quotients by the gcd:", (t, s)

两段计算模乘逆元的程序分别如下：

function inverse(a, n)    t := 0;     newt := 1;        r := n;     newr := a;        while newr ≠ 0        quotient := r div newr        (t, newt) := (newt, t - quotient * newt)         (r, newr) := (newr, r - quotient * newr)    if r > 1 then return "a is not invertible"    if t < 0 then t := t + n    return t

function inverse(a, p)    t := 0;     newt := 1;        r := p;     newr := a;        while newr ≠ 0        quotient := r div newr        (r, newr) := (newr, r - quotient * newr)        (t, newt) := (newt, t - quotient * newt)     if degree(r) > 0 then         return "Either p is not irreducible or a is a multiple of p"    return (1/r) * t