5

これは、Scheme を使用して教えられたプログラミング入門クラスの個人的な課題ですが、Python の例も同様に満足しています。

次のように、スキームで剰余累乗のバイナリメソッドを既に実装しています。

(define (pow base expo modu)
  (if (zero? expo)
      1
      (if (even? expo)
          (mod (expt (pow base (/ expo 2) modu) 2) modu)
          (mod (* base (pow base (sub1 expo) modu)) modu))))

Chez スキームには python の pow (base expo modu) に似た実装がないため、これが必要です。

現在、剰余乗算を解くモンゴメリー法を実装しようとしています。例として、私は持っています：

Trying to solve:
    (a * b) % N
N = 79
a = 61
b = 5
R = 100
a' = (61 * 100) % 79 = 17
b' = (5 * 100) % 79 = 26
RR' - NN' = 1

RR' - NN' = 1 の解き方を理解しようとしています。R' の答えは 64 であり、N' は 81 である必要がありますが、ユークリッド アルゴリズムを使用してこの答えを得る方法がわかりません。 .

4

1 に答える 1

1

拡張ユークリッドの互除法は次のとおりです。

(define (euclid x y)
  (let loop ((a 1) (b 0) (g x) (u 0) (v 1) (w y))
    (if (zero? w) (values a b g)
      (let ((q (quotient g w)))
        (loop u v w (- a (* q u)) (- b (* q v)) (- g (* q w)))))))

したがって、あなたの例では、

> (euclid 79 100)
19
-15
1

あなたは私のブログでもっと読むことができます。

于 2012-11-13T01:24:22.500 に答える