40 lines
571 B
Plaintext
40 lines
571 B
Plaintext
INT FUNC ModInverse(INT a,b)
|
|
INT t,nt,r,nr,q,tmp
|
|
|
|
IF b<0 THEN b=-b FI
|
|
IF a<0 THEN a=b-(-a MOD b) FI
|
|
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
|
|
OD
|
|
IF r>1 THEN
|
|
RETURN (-1)
|
|
FI
|
|
IF t<0 THEN
|
|
t==+b
|
|
FI
|
|
RETURN (t)
|
|
|
|
PROC Test(INT a,b)
|
|
INT res
|
|
|
|
res=ModInverse(a,b)
|
|
IF res>=0 THEN
|
|
PrintF("%I MODINV %I=%I%E",a,b,res)
|
|
ELSE
|
|
PrintF("%I MODINV %I has no result%E",a,b)
|
|
FI
|
|
RETURN
|
|
|
|
PROC Main()
|
|
Test(42,2017)
|
|
Test(40,1)
|
|
Test(52,-217)
|
|
Test(-486,217)
|
|
Test(40,2018)
|
|
RETURN
|