SICP中Fermat测试的增长顺序

Question

该fermat-test所提交的程序计算机程序的结构与解释都有增长,已经由我和许多其他人的实验验证的论旨的日志(n)的顺序.

令我困惑的是random它定义中的原始程序.这是否意味着增长的顺序random最多为log(n)的θ？经过一些搜索工作后,我仍然不确定是否可以编写一个伪随机数生成器,其增长顺序不超过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有一个log-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仍然具有log-of-log(n)增长顺序.

Answer 1

费马的小定理如下:

如果ñ是一个素数及一个是小于任意正整数ñ,然后一个上升到第n个功率为全等一个模ñ.

因此,这里的想法是给予一定的数量ñ,我们选择的任何数量的一个这样一个<N ,然后我们计算表达式一^ñ%N ==一.如果该表达式返回false,那么我们就知道这ñ不是素数.但是,如果这个表达式返回true,然后有一个很好的机会,这ñ是素数.

根据这个定理,我们能够推导出你上面列出的函数:

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

在你的帖子中,你已经明确表示你理解Θ(lg n)增长和渐近时间复杂度是从expmod函数中得出的,所以我们只需要了解randomScheme中的工作方式,以了解它的增长顺序是否恒定或不.

在Scheme中,您可以使用该random函数生成伪随机数.从Scheme文档中,我们知道这一点

当前的实现是基于来自A New Class of Random Number Generators,George Marsaglia和Arif Zaman,The Annals of Applied Probability,Vol.24,No.2,pp.1998的算法的"带有减法"随机数发生器.1991年第1号,第3号

如果您有兴趣阅读有关此特定实现的更多信息,欢迎您阅读更多有关它们的信息,但这里的重要部分是了解我们能够在恒定时间内以恒定空间生成伪随机数,因此通过此函数调用使增长顺序保持不变.

快速地说,如果你真的有兴趣了解更多关于伪随机数生成器的信息,那么Scheme文档提出了一个建议,除了它当前的通用算法之外,可能还有更好更高效的生成器 - 所以你可能会想要查看其他生成器算法.