44 lines
1.0 KiB
Plaintext
44 lines
1.0 KiB
Plaintext
MODULE ModularInverse;
|
|
FROM InOut IMPORT WriteString, WriteInt, WriteLn;
|
|
|
|
TYPE Data = RECORD x : INTEGER;
|
|
y : INTEGER
|
|
END;
|
|
|
|
VAR c : INTEGER;
|
|
ab : ARRAY [1..5] OF Data;
|
|
|
|
PROCEDURE mi(VAR a, b : INTEGER): INTEGER;
|
|
VAR t, nt, r, nr, q, tmp : INTEGER;
|
|
|
|
BEGIN
|
|
b := ABS(b);
|
|
IF a < 0 THEN a := b - (-a MOD b) END;
|
|
t := 0; nt := 1; r := b; nr := a MOD b;
|
|
WHILE (nr # 0) DO
|
|
q := r / nr;
|
|
tmp := nt; nt := t - q * nt; t := tmp;
|
|
tmp := nr; nr := r - q * nr; r := tmp;
|
|
END;
|
|
IF (r > 1) THEN RETURN -1 END;
|
|
IF (t < 0) THEN RETURN t + b END;
|
|
RETURN t;
|
|
END mi;
|
|
|
|
BEGIN
|
|
ab[1].x := 42; ab[1].y := 2017;
|
|
ab[2].x := 40; ab[2].y := 1;
|
|
ab[3].x := 52; ab[3].y := -217;
|
|
ab[4].x := -486; ab[4].y := 217;
|
|
ab[5].x := 40; ab[5].y := 2018;
|
|
WriteLn;
|
|
WriteString("Modular inverse");
|
|
WriteLn;
|
|
FOR c := 1 TO 5 DO
|
|
WriteInt(ab[c].x, 6); WriteString(", ");
|
|
WriteInt(ab[c].y, 6); WriteString(" = ");
|
|
WriteInt(mi(ab[c].x, ab[c].y),6);
|
|
WriteLn;
|
|
END;
|
|
END ModularInverse.
|