Modular inverse: Difference between revisions
→{{header|Oberon-2}}
Line 2,028:
q := ((-x) DIV (-y));
IF (-x) MOD (-y) # 0 THEN q := q + 1 END
END
END;
RETURN q
END euclidDiv;
(* I have added this unit test because, earlier, I posted a buggy
version of euclidDiv. *)
PROCEDURE testEuclidDiv;
VAR x, y, q, r : INTEGER;
BEGIN
FOR x := -100 TO 100 DO
FOR y := -100 TO 100 DO
IF y # 0 THEN
q := euclidDiv (x, y);
r := x - (q * y);
IF (r < 0) OR (ABS (y) <= r) THEN
(* A remainder was outside the expected range. *)
Out.String ("euclidDiv fails its test")
END
END
END
END
END testEuclidDiv;
PROCEDURE inverse (a, n : INTEGER) : INTEGER;
Line 2,044 ⟶ 2,063:
quotient := euclidDiv (r, newr);
tmp := newt; newt := t - (quotient * newt); t := tmp;
tmp := newr; newr := r - (quotient * newr); r := tmp
END;
IF r > 1 THEN
Line 2,051 ⟶ 2,070:
t := t + n
END;
RETURN t
END inverse;
BEGIN
testEuclidDiv;
Out.Int (inverse (42, 2017), 0);
Out.Ln
END modularInverseInOberon2.
</syntaxhighlight>
| |||