algorithm - SICP中费马检验的增长顺序

Question

Structure and Interpretation of Computer Programs 介绍的 fermat-test 过程具有 theta-of-log(n) 增长阶数，已由我验证以及许多其他人的实验。

令我困惑的是其定义中的 random 原始过程。这是否意味着 random 的增长顺序至多为 log(n) 的 theta？经过一些搜索工作，我仍然不确定是否可以编写一个增长阶数不超过 log(n) 的 theta 的伪随机数生成器。

代码如下:

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  ; Wait a second! What's the order of growth of `random`?
  (try-it (+ 1 (random (- n 1)))))

，其中 expmod 具有 theta-of-log(n) 增长顺序:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m)))) 

你能给我解释一下吗？

• 如果确实存在这样的伪随机数生成器，请告诉我它是如何工作的。
• 如果这样的伪随机数生成器不存在，请告诉我 fermat-test 如何仍然具有增长的 theta-of-log(n) 阶数。

Answer 1

费马小定理全文如下:

If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.

所以这里的想法是，给定一些数 n，我们选择任何数 a 使得 a < n 然后我们计算表达式 aⁿ % n == a。如果此表达式返回 false，则我们知道 n 不是素数。但是，如果此表达式返回真，则 很有可能 n 是素数。

根据这个定理，我们可以推导出上面列出的函数:

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

在您的帖子中，您已经明确表示您了解 Θ(lg n) 增长和渐近时间复杂度是从 expmod 函数派生的，因此我们只需要了解如何 random 在 Scheme 中工作以了解其增长顺序是否恒定。

在 Scheme 中，您可以 generate pseudorandom numbers using the random function .从Scheme文档中我们知道

The current implementation is a “subtract-with-carry” random-number generator, based on the algorithm from A New Class of Random Number Generators, George Marsaglia and Arif Zaman, The Annals of Applied Probability, Vol. 1, No. 3, 1991

如果您有兴趣阅读有关此特定实现的更多信息，you're more than welcome to read more about them ，但这里的重要部分是理解我们能够在恒定时间和恒定空间内生成伪随机数，因此此函数调用不会改变增长顺序。

顺便说一句，如果您真的有兴趣了解更多关于伪随机数生成器的信息，Scheme 文档指出，除了当前的通用算法之外，可能还有更好、更高效的生成器 —所以您可能还想查看其他生成器算法。