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

例如，它给出了正确的值 (inverse 5 11) -> 9 (inverse 9 11) -> 5 (inverse 7 11) -> 8 (inverse 8 12) -> #f 但是当我给出 (inverse 5 12) 它产生#f，而它应该是5。你能看到错误在哪里吗？

谢谢你的帮助。

4

4 回答 4

2

您引用的算法是 Richard Crandall 和 Carl Pomerance的Prime Numbers一书中的算法 9.4.4。在本书的正文中，他们声明该算法适用于素模数和复合模量，但在他们书中的勘误表中，他们正确地指出该算法始终适用于素数模量，并且主要但并非总是适用于复合模量。因此，您发现了失败。

和你一样，我使用了算法 9.4.4，并且对我的一些结果感到困惑，直到我发现了问题。

这是我现在使用的模反函数，它适用于素模和复合模，只要它的两个参数互质即可。它本质上是@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

它必须是那个算法吗？如果没有，试试这个，取自wikibooks：

(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

下面这两个功能也可以为您提供帮助。

理论

下面是我们如何找到乘法逆 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 回答