Расширенный евклидов алгоритм на схеме - PullRequest
Новая
       14

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

0 голосов
/ 28 октября 2018

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

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

(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 Я добавил снимок экрана с инструкциями, которые нам были даны, но я не вижу изображение. Если есть проблема, пожалуйста, дайте мне знать.)

1 Ответ

0 голосов
/ 28 октября 2018

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

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