Extended Euclidean algorithm - 편집 역사

2017년 8월 11일 (금) 07:06에 Admin님의 편집

2017-08-11T07:06:38Z

2017-08-11T07:06:30Z

2017-08-11T07:03:41Z

2017-08-11T07:03:27Z

2017-08-11T07:02:37Z

2017-08-11T07:00:42Z

2017-08-11T07:00:26Z

2017-08-11T06:47:22Z

2017-08-11T06:47:05Z

2017-08-11T06:46:54Z

@@ 25번째 줄: / 25번째 줄: @@
 <pre>
 def invmult(a, n):
-   r, x, _ = exteuclid(a, n)
+    r, x, _ = exteuclid(a, n)
      # caution: if r>1, `a` is not invertible.
      if x<0:

@@ 8번째 줄: / 8번째 줄: @@
      # t0 := t_{i-1}
      # t1 := t_i
      q = m/n
      r = m%n
@@ 26번째 줄: / 25번째 줄: @@
 <pre>
 def invmult(a, n):
-    if a<n:
+   r, x, _ = exteuclid(a, n)
      # caution: if r>1, `a` is not invertible.
      if x<0:

@@ 38번째 줄: / 38번째 줄: @@
 </pre>
 오직 inverse만 구하기 위해서라면, <c> exteuclid</c>에서 <c>t</c>부분을 모두 지워도 된다.
 ref. [[0811_coprime_test|coprime test]]

@@ 37번째 줄: / 37번째 줄: @@
 #10154
 </pre>
 ref. [[0811_coprime_test|coprime test]]

@@ 21번째 줄: / 21번째 줄: @@
 #(2, -9, 47)
      </pre>
 [https://en.m.wikipedia.org/wiki/Modular_multiplicative_inverse Modular multiplicative inverse]는 다음으로 구한다.

@@ 27번째 줄: / 27번째 줄: @@
      if a<n:
          a += n
-     _, x, _ = exteuclid(a, n)
+     r, x, _ = exteuclid(a, n)
      if x<0:
          x += n

@@ 35번째 줄: / 35번째 줄: @@
 #10154
 </pre>
-ref. [[http://iph.kr/wiki/index.php/0811_coprime_test coprime test]]
+ref. [[0811_coprime_test|coprime test]]

@@ 35번째 줄: / 35번째 줄: @@
 #10154
 </pre>
-ref. [[http://iph.kr/wiki/index.php/0811_coprime_test|coprime test]]
+ref. [[http://iph.kr/wiki/index.php/0811_coprime_test | coprime test]]