SICP中费马检验的增长顺序

Question

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

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

代码如下：

(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。如果这个表达式 return 为假，那么我们知道 n 不是质数。但是，如果这个表达式 return 为真，那么 很有可能 n 是素数。

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

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

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

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

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，但这里的重要部分是了解我们能够在常数时间内生成具有常数 [=52= 的伪随机数], 因此本次函数调用不会改变增长顺序。

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

SICP中费马检验的增长顺序

The order of growth of the Fermat test in SICP

random

algorithm

scheme

sicp

time-complexity