Extended Euclidian Algorithm in Scheme

Question

I'm trying to write a code for extended Euclidian Algorithm in Scheme for an RSA implementation.

The thing about my problem is I can't write a recursive algorithm where the output of the inner step must be the input of the consecutive outer step. I want it to give the result of the most-outer step but as it can be seen, it gives the result of the most inner one. I wrote a program for this (it is a bit messy but I couldn't find time to edit.):

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

))

All kinds of help and advice would be greatly appreciated. (P.S. I added a scrrenshot of the instructions that was given to us but I can't see the image. If there is a problem, please let me know.)

Answer 1

This is a Diophantine equation and is a bit tricky to solve. I came up with an iterative solution adapted from 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)))))

Second, go back and solve the equation:

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

Finally, put it all together and determine the correct signs of the solution:

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

For example:

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