Scheme 中的扩展欧几里德算法

Question

我正在尝试为 RSA 实现的 Scheme 中的扩展欧几里德算法编写代码。

我的问题是我无法编写递归算法，其中内部步骤的输出必须是连续外部步骤的输入。我希望它给出最外层步骤的结果，但可以看出，它给出了最内层步骤的结果。我为此编写了一个程序（有点乱，但我没时间编辑。）：

(define ax+by=1                     
  (lambda (a b)                     
    (define q (quotient a b))
    (define r (remainder a b))

    (define make-list (lambda (x y)
       (list x y)))

(define solution-helper-x-prime (lambda (a b q r)
   (if (= r 1) (- 0 q) (solution-helper-x-prime b r (quotient b r) (remainder b r)))
))

(define solution-helper-y-prime (lambda (a b q r)
   (if (= r 1) (- r (* q (- 0 q) )) (solution-helper-y-prime b r (quotient b r) (remainder b r))
 ))

(define solution-first-step (lambda (a b q r)
  (if (= r 1) (make-list r (- 0 q))
        (make-list (solution-helper-x-prime b r (quotient b r) (remainder b r)) (solution-helper-y-prime b r (quotient b r) (remainder b r))))
                          ))
  (display (solution-first-step a b q r)) 

))

我们将不胜感激各种帮助和建议。（P.S。我添加了给我们的说明的截图，但我看不到图像。如果有问题，请告诉我。）

Answer 1

这是一个丢番图方程，求解起来有点棘手。我想出了一个改编自 this explanation, but had to split the problem in parts - first, obtain the list of quotients by applying the extended Euclidean algorithm:

的迭代解决方案

(define (quotients a b)
  (let loop ([a a] [b b] [lst '()])
    (if (<= b 1)
        lst
        (loop b (remainder a b) (cons (quotient a b) lst)))))

其次，回去解方程：

(define (solve x y lst)
  (if (null? lst)
      (list x y)
      (solve y (+ x (* (car lst) y)) (cdr lst))))

最后，将它们放在一起并确定解决方案的正确符号：

(define (ax+by=1 a b)
  (let* ([ans (solve 0 1 (quotients a b))]
         [x (car ans)]
         [y (cadr ans)])
    (cond ((and (= a 0) (= b 1))
           (list 0 1))
          ((and (= a 1) (= b 0))
           (list 1 0))
          ((= (+ (* a (- x)) (* b y)) 1)
           (list (- x) y))
          ((= (+ (* a x) (* b (- y))) 1)
           (list x (- y)))
          (else (error "Equation has no solution")))))

例如：

(ax+by=1 1027 712)
=> '(-165 238)
(ax+by=1 91 72)
=> '(19 -24)
(ax+by=1 13 13)
=> Equation has no solution

Scheme 中的扩展欧几里德算法

Extended Euclidian Algorithm in Scheme

algorithm

math

recursion

scheme

diophantine