欧几里得算法用于解决RR' - NN' = 1问题。使用蒙哥马利算法进行模幂运算，以在Python或Petite Chez方案中实现费马测试。

Question

这是我在Scheme编程课上的个人挑战，涉及到IT技术相关内容。但如果使用Python进行示例展示，我同样感到非常高兴。

我已经按照以下方式在Scheme中实现了模幂二进制方法：

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

由于Chez Scheme没有类似于Python的pow（base expo modu）的实现，所以这是必要的。

现在我正在尝试实现Montgomery方法来解决模乘法问题。例如，我有：

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

我正在学习如何解决RR'-NN'=1的问题。我知道R'应该是64，N'应该是81，但不知道如何使用欧几里得算法来得出答案。

- Seth

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

您可以在我的博客中了解更多。

- user448810