1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
//Euclid's extended algorithm to calculate inverse of n modulo p
function [ans]=mod_inv(n,p)
p_ = p
q = []
m = []
i=1
r = 1
while r>=0
if i<3
m(i,1) = i-1
else
m(i,1) = m(i-2,1) - m(i-1,1)*q(i-2,1)
if m(i,1)<0
m(i,1) = m(i,1)+p_
end
m(i,1) = modulo(m(i,1),p_)
end
if r==0
break
end
q(i,1) = int(p/n)
r = modulo(p,n)
p = n
n = r
i = i+1
end
ans = m(i,1)
endfunction
|
