1

モジュロmの逆数のコードを記述しました。初期のケースのほとんどで機能しますが、一部では機能しません。コードは以下のとおりです。

(define (inverse x m)
    (let loop ((x (modulo x m)) (a 1))
      (cond ((zero? x) #f) ((= x 1) a)
            (else (let ((q (- (quotient m x))))
                    (loop (+ m (* q x)) (modulo (* q a) m)))))))

たとえば、（逆5 11）-> 9（逆9 11）-> 5（逆7 11）-> 8（逆8 12）-> #fの正しい値を示しますが、（逆5 12）を与えると5であるはずの#fを生成します。バグがどこにあるかわかりますか？

助けてくれてありがとう。

4

4 に答える 4

2

あなたが引用したアルゴリズムは、RichardCrandallとCarlPomeranceによる本PrimeNumbersのAlgorithm9.4.4です。本のテキストでは、アルゴリズムは素数と複合係数の両方で機能すると述べていますが、本の正誤表では、アルゴリズムは常に素数と複合係数で機能すると述べていますが、常にではありません。したがって、あなたが見つけた失敗。

あなたと同じように、私はアルゴリズム9.4.4を使用しましたが、問題を発見するまで、いくつかの結果に戸惑いました。

これが私が現在使用しているモジュラ逆関数です。これは、2つの引数が互いに素である限り、素数と合成の両方の係数で機能します。これは本質的に@OscarLopezが使用する拡張ユークリッドアルゴリズムですが、いくつかの冗長な計算が削除されています。#f必要に応じて、エラーをスローする代わりに戻るように関数を変更できます。

(define (inverse x m)
  (let loop ((x x) (b m) (a 0) (u 1))
    (if (zero? x)
        (if (= b 1) (modulo a m)
          (error 'inverse "must be coprime"))
        (let* ((q (quotient b x)))
          (loop (modulo b x) x u (- a (* u q)))))))
于 2012-10-27T13:43:29.683 に答える
1

正確にそのアルゴリズムである必要がありますか？そうでない場合は、ウィキブックスから取得したこれを試してください：

(define (egcd a b)
  (if (zero? a)
      (values b 0 1)
      (let-values (((g y x) (egcd (modulo b a) a)))
        (values g (- x (* (quotient b a) y)) y))))

(define (modinv a m)
  (let-values (((g x y) (egcd a m)))
    (if (not (= g 1))
        #f
        (modulo x m))))

期待どおりに機能します。

(modinv 5 11) ; 9
(modinv 9 11) ; 5
(modinv 7 11) ; 8
(modinv 8 12) ; #f 
(modinv 5 12) ; 5
于 2012-10-27T02:50:11.560 に答える
0

以下の2つの関数も役立ちます。

仮説

乗法逆数dを見つける方法は次のとおりです。e * d = 1（mod n）が必要です。これは、ある整数kに対してed + nk=1であることを意味します。したがって、一般方程式ax + by = 1を解く手順を記述します。ここで、aとbが与えられ、xとyは変数であり、これらの値はすべて整数です。この手順を使用して、dとkのed + nk=1を解きます。次に、kを破棄して、単にdを返すことができます。>>

(define (ax+by=1 a b)
        (if (= b 0)
            (cons 1 0)
            (let* ((q (quotient a b))
                   (r (remainder a b))
                   (e (ax+by=1 b r))
                   (s (car e))
                   (t (cdr e)))
           (cons t (- s (* q t))))))

この関数は、ax + by = 1の形式の方程式の一般的な解であり、aとbが与えられます。inverse-mod関数は、この解を使用して逆を返します。

 (define inverse-mod (lambda (a m) 
                  (if (not (= 1 (gcd a m)))
                      (display "**Error** No inverse exists.")
                      (if (> 0(car (ax+by=1 a m)))
                          (+ (car (ax+by=1 a m)) m)
                          (car (ax+by=1 a m))))))

いくつかのテストケースは次のとおりです。

(inverse-mod 5 11) ; -> 9 5*9 = 45 = 1 (mod 11)
(inverse-mod 9 11) ; -> 5
(inverse-mod 7 11) ; -> 8 7*8 = 56 = 1 (mod 11)
(inverse-mod 5 12) ; -> 5 5*5 = 25 = 1 (mod 12)
(inverse-mod 8 12) ; -> error no inverse exists
于 2012-10-29T13:49:47.663 に答える
0

これは、Schemeに直接翻訳されたそのページのHaskellコードだと思います。

(define (inverse p q)
  (cond ((= p 0) #f)
        ((= p 1) 1)
        (else
          (let ((recurse (inverse (mod q p) p)))
             (and recurse
                  (let ((n (- p recurse)))
                    (div (+ (* n q) 1) p)))))))

再帰から末尾再帰に変換しようとしているようです。そのため、状況があまり一致していません。

于 2012-10-27T02:41:13.947 に答える