21 lines
529 B
Plaintext
21 lines
529 B
Plaintext
function mul_inv(integer a, n)
|
|
if n<0 then n = -n end if
|
|
if a<0 then a = n - mod(-a,n) end if
|
|
integer t = 0, nt = 1,
|
|
r = n, nr = a;
|
|
while nr!=0 do
|
|
integer q = floor(r/nr)
|
|
{t, nt} = {nt, t-q*nt}
|
|
{r, nr} = {nr, r-q*nr}
|
|
end while
|
|
if r>1 then return "a is not invertible" end if
|
|
if t<0 then t += n end if
|
|
return t
|
|
end function
|
|
|
|
?mul_inv(42,2017)
|
|
?mul_inv(40, 1)
|
|
?mul_inv(52, -217) /* Pari semantics for negative modulus */
|
|
?mul_inv(-486, 217)
|
|
?mul_inv(40, 2018)
|