algorithm - モジュラー逆アルゴリズム

Question

重複の可能性:
スキームのモジュロ m の乗法逆数

x と y をペアとして解くためのコードを作成しました。ax + by = 1 を使用して、e モジュロ n の乗法逆数を求めるモジュラー逆数コードを作成する必要があります。

引用符

(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))))))

編集：以下の機能で問題が解決しました。

引用符

 (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))))))

Answer 1

これは拡張ユークリッド アルゴリズムを使用して剰余逆数を見つけます。

(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)))))))

Answer 2

拡張ユークリッド アルゴリズムを検討する