43 lines
969 B
Text
43 lines
969 B
Text
const func bigInteger: modInverse (in var bigInteger: a,
|
|
in var bigInteger: b) is func
|
|
result
|
|
var bigInteger: modularInverse is 0_;
|
|
local
|
|
var bigInteger: b_bak is 0_;
|
|
var bigInteger: x is 0_;
|
|
var bigInteger: y is 1_;
|
|
var bigInteger: lastx is 1_;
|
|
var bigInteger: lasty is 0_;
|
|
var bigInteger: temp is 0_;
|
|
var bigInteger: quotient is 0_;
|
|
begin
|
|
if b < 0_ then
|
|
raise RANGE_ERROR;
|
|
end if;
|
|
if a < 0_ and b <> 0_ then
|
|
a := a mod b;
|
|
end if;
|
|
b_bak := b;
|
|
while b <> 0_ do
|
|
temp := b;
|
|
quotient := a div b;
|
|
b := a rem b;
|
|
a := temp;
|
|
|
|
temp := x;
|
|
x := lastx - quotient * x;
|
|
lastx := temp;
|
|
|
|
temp := y;
|
|
y := lasty - quotient * y;
|
|
lasty := temp;
|
|
end while;
|
|
if a = 1_ then
|
|
modularInverse := lastx;
|
|
if modularInverse < 0_ then
|
|
modularInverse +:= b_bak;
|
|
end if;
|
|
else
|
|
raise RANGE_ERROR;
|
|
end if;
|
|
end func;
|