Расширенный евклидов алгоритм на схеме

Question

Я пытаюсь написать код для расширенного алгоритма Евклида в схеме для реализации RSA.

Суть моей проблемы в том, что я не могу написать рекурсивный алгоритм, в котором выход внутреннего шага должен быть входом последовательного внешнего шага. Я хочу, чтобы он дал результат самого внешнего шага, но, как видно, он дает результат самого внутреннего шага. Я написал программу для этого (это немного грязно, но я не мог найти время для редактирования.):

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

))

Будем весьма благодарны за всевозможную помощь и советы. (PS Я добавил скриншот снимка, который нам дали, но я не вижу изображение. Если есть проблема, пожалуйста, дайте мне знать.)

Answer 1

Это диофантово уравнение, и его немного сложно решить. Я придумал итеративное решение, адаптированное из этого объяснения, но мне пришлось разбить проблему на части - во-первых, получить список факторов, применив расширенный евклидов алгоритм:

(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