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

考虑扩展欧几里得算法

Answer 2

这使用扩展欧几里得算法来找到模逆：

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