RR '- NN'= 1을 해결하는 유클리드 알고리즘. 파이썬 또는 푸티 쉐 스키마에서 Fermat 테스트를 구현하기위한 몽고메리 알고리즘의 모듈러 지수화

Question

이것은 Scheme을 사용하여 배우는 입문 프로그래밍 수업에서 개인적으로 어려운 문제이지만, Python 예제에 만족합니다.

은 이미 다음과 같은 방식으로 모듈 식 지수의 이진 방법을 구현했습니다 :

(define (pow base expo modu) 
    (if (zero? expo) 
     1 
     (if (even? expo) 
      (mod (expt (pow base (/ expo 2) modu) 2) modu) 
      (mod (* base (pow base (sub1 expo) modu)) modu)))) 

체즈 계획은 파이썬의 펑 (기본 엑스포 MODU)와 유사한 어떤 구현을 가지고 있지 않기 때문에이 필요합니다.

이제 모듈 식 곱셈을 해결하는 몽고메리 방법을 구현하려고합니다. '- NN'나는 RR를 해결하는 방법을 이해하기 위해 노력하고있어

Trying to solve: 
    (a * b) % N 
N = 79 
a = 61 
b = 5 
R = 100 
a' = (61 * 100) % 79 = 17 
b' = (5 * 100) % 79 = 26 
RR' - NN' = 1 

내가 R에 대한 답은 '64 수와 N해야한다'(81)를해야한다는 인식 = 1 :하지만, 예를 들어, 내가 가진 유클리드 알고리즘을 사용하여이 답을 얻는 방법을 이해하지 못합니다.

Answer 1

확장 된 유클리드 알고리즘은 다음과 같습니다

(define (euclid x y) 
    (let loop ((a 1) (b 0) (g x) (u 0) (v 1) (w y)) 
    (if (zero? w) (values a b g) 
     (let ((q (quotient g w))) 
     (loop u v w (- a (* q u)) (- b (* q v)) (- g (* q w))))))) 

따라서, 귀하의 예제에서,

> (euclid 79 100) 
19 
-15 
1 

당신은 my blog 더 많은 읽을 수 있습니다.