Four modular inverse algorithms - magma implementation

Conclusion:
 Algorithm 2.20 = Algorithm 9.4.4  > Algorithm 2.22 > Algorithm 9.4.5
Here bigger means faster, less iteration rounds.
But for Mersenne number, still need some time to test.

// Algorithm 2.20,  from "prime number: a computational perspective" P465
// modular inverse for Mersenne number 2^q-1
SetSeed(2015);
q:=7;
p:=2^q-1;
x:=2^13+1; // Random()

a:=x; //bak
//initialize
u:=x;
v:=p;
x1:=1;
x2:=0;

k:=1;
//loop
while u ne 1 do
q:=v div u;
r:=v-q*u;
x:=x2-q*x1;

v:=u;
u:=r;
x2:=x1;
x1:=x;
        k:=k+1;
       printf "%o %o %o\n", x1, x2, u, v;
end while;

invp:= x1 mod p;
Verify:= invp*a mod p;

printf "interation=\n %o\n", k;
printf "inverse=\n %o\n", invp;
printf "x=\n %o\n", x;
printf "Verify=\n %o", Verify;

// Algorithm 2.22 Binary algorithm for inversion in Fp,  from "Guide to ECC" P41
// binary Extended Euclidean algorithm, modular inverse
SetSeed(2015);
q:=7;
p:=2^q-1;
x:=11; // Random()

//initialize
u:=x;
v:=p;
x1:=1;
x2:=0;

k:=1;
//loop
while (u ne 1) and (v ne 1) do
while u mod 2 eq 0 do
u:=u div 2;
if x1 mod 2 eq 0 then
x1:=x1 div 2;
else
x1:=x1+p;
x1:=x1 div 2;
end if;
end while;

while v mod 2 eq 0 do
v:=v div 2;
if x2 mod 2 eq 0 then
x2:=x2 div 2;
else
x2:=x2+p;
x2:=x2 div 2;
end if;
end while;

if (u gt v) or (u eq v) then
u:=u-v;
x1:=x1-x2;
else
v:=v-u;
x2:=x2-x1;
end if;

if u eq 1 then
invp:= x1 mod p;
else
invp:= x2 mod p;
end if;

        k:=k+1;
       printf "%o %o %o %o\n", u, v, x1, x2;
end while;

Verify:= invp*x mod p;

printf "interation=\n %o\n", k;
printf "inverse=\n %o\n", invp;
printf "x=\n %o\n", x;
printf "Verify=\n %o", Verify;

// Algorithm 9.4.4,  from "prime number: a computational perspective" P465
// modular inverse for Mersenne number 2^q-1

SetSeed(2015);
q:=7;
p:=2^q-1;
x:=11; // Random()

//initialize
a:=1;
z:=x mod p;

k:=1;
//loop
while z ne 1 do
q:=-(p div z);
z:=p+q*z;
a:=(q*a) mod p;

        k:=k+1;
       printf "%o %o %o\n", q, z, a;
end while;

invp:= a;
Verify:= invp*x mod p;

printf "interation=\n %o\n", k;
printf "inverse=\n %o\n", a;
printf "x=\n %o\n", x;
printf "Verify=\n %o", Verify;

// Algorithm 9.4.5,  from "prime number: a computational perspective" P466
// modular inverse for Mersenne number 2^q-1

SetSeed(2015);
q:=7;
p:=2^q-1;
x:=11; // Random()

//initialize
a:=1;
b:=0;
y:=x;
z:=p;

k:=1;
//Relational Reduction
//while k le 15 do
while k gt 0 do
 //find e
 e:=0;
 while (y mod 2) eq 0 do
  y:=y div 2;
  e:=e+1;
 end while;
 a:=a*2^(q-e) mod p;
 if y eq 1  then
  break;
 end if;

 tmp_a:=a;
 a:=a+b;
 b:=tmp_a;
 tmp_y:=y;
 y:=y+z;
 z:=tmp_y;

        k:=k+1;
       printf "%o %o %o %o\n", a, b, y, z;
end while;

invp:= a;
Verify:= invp*x mod p;

printf "interation=\n %o\n", k;
printf "inverse=\n %o\n", a;
printf "x=\n %o\n", x;
printf "Verify=\n %o", Verify;