"Extended Euclidean algorithm"의 두 판 사이의 차이
ph
잔글 |
잔글 |
||
| (같은 사용자의 중간 판 12개는 보이지 않습니다) | |||
| 8번째 줄: | 8번째 줄: | ||
# t0 := t_{i-1} | # t0 := t_{i-1} | ||
# t1 := t_i | # t1 := t_i | ||
| − | |||
q = m/n | q = m/n | ||
r = m%n | r = m%n | ||
| 21번째 줄: | 20번째 줄: | ||
#(2, -9, 47) | #(2, -9, 47) | ||
</pre> | </pre> | ||
| + | as you can notice, this uses recursion, but the [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm wiki]’s pseudo code does not. | ||
| + | |||
| + | [https://en.m.wikipedia.org/wiki/Modular_multiplicative_inverse Modular multiplicative inverse]는 다음으로 구한다. | ||
| + | <pre> | ||
| + | def invmult(a, n): | ||
| + | r, x, _ = exteuclid(a, n) | ||
| + | # caution: if r>1, `a` is not invertible. | ||
| + | if x<0: | ||
| + | x += n | ||
| + | return x | ||
| + | #test | ||
| + | #print invmult(234242, 11117) #coprime | ||
| + | #10154 | ||
| + | </pre> | ||
| + | 오직 inverse만 구하기 위해서라면, <c> exteuclid</c>에서 <c>t</c>부분을 모두 지워도 된다. | ||
| + | |||
| + | ref. [[0811_coprime_test|coprime test]] | ||
2017년 8월 11일 (금) 16:06 기준 최신판
python code is as follows,
def exteuclid(m, n, s0=1, s1=0, t0=0, t1=1):
# s0 := s_{i-1}
# s1 := s_i
# t0 := t_{i-1}
# t1 := t_i
q = m/n
r = m%n
s = s0 - q*s1
t = t0 - q*t1
if r==0:
return n, s1, t1
else:
return exteuclid(n, r, s1, s, t1, t)
#test
#print exteuclid(240, 46)
#(2, -9, 47)
as you can notice, this uses recursion, but the wiki’s pseudo code does not.
Modular multiplicative inverse는 다음으로 구한다.
def invmult(a, n):
r, x, _ = exteuclid(a, n)
# caution: if r>1, `a` is not invertible.
if x<0:
x += n
return x
#test
#print invmult(234242, 11117) #coprime
#10154
오직 inverse만 구하기 위해서라면, exteuclid에서 t부분을 모두 지워도 된다.
ref. coprime test