SICP 习题 （1.28）解题总结

SICP 习题 1.28 要求使用 Miller-Rabin检查来检测素数。

题目中说到Miller-Rabin检查是费马检查的一种变形，不过这种变形不会被Carmichael数欺骗。

上几题搞费马检查都已经苦死我了，现在还来费马检查的变形？变形金刚我就知道，擎天柱我很喜欢，大黄蜂也不错。对着习题1.28回忆了一段童年动画片以后，题目还是摆在那里纹丝不动，于是最终还是硬着头皮去看题目细节。

首先来看看这个变形，前面几道题的费马检查是判断（（a的n次方）对n求模）是否等于a，是的话n是素数的可能性就大，而这里所谓的变形就是判断（ （a 的(n-1)次方）对n求模）是否等于1，是的话n是素数的可能性就大。

就这个变形我都想了老半天，因为书中对这个变形的描述更加晦涩一些，书中是说“a的(n-1)次幂与1模n同余”，我当时就愣了好久，“与1模n同余”啥意思，1模啥不还是1吗？难道我哪里理解不对？

后来通过其它网上资料验证就是“a的(n-1)次幂对n求模等于1”的意思，搞这么复杂。

明确了这个变形后就简单一些了，因为我们之前已经定义了expmod过程，只需要调用下面的过程就可以计算“a的(n-1)次幂对n求模”了：

(expmod a (- n 1) n)

然后判断它是否等于1就好了。

于是很快修改了我的full-fermat-test过程的代码，注意，是修改了full-fermat-test的代码，就是那个对所有小于n大于1的数进行检查的那个过程，后来证实我这个行为带来了一系列其它问题。

我将代码

(define (fermat-try n a)
  (= (expmod a n n ) a))

改成了：

(define (fermat-try n a)
  (= (expmod a (- n 1) n ) 1))

然后就迫不及待地开始测试了，我测试了3000以内的所有整数，发现全部Carmichael数都落马！没有一个Carmichael数可以通过这种变形的费马检查！

结果太出乎我意料了！这个变形有这么神奇吗？

在惊奇过后就是怀疑，我想到了两个问题。

第一个问题是，这个变形从数学上来讲和原始的费马检查不是等价的吗？为什么一个不会被Carmichael数欺骗，而一个会被欺骗？

第二个问题是，既然这个变形已经这么厉害了，题目中后面的什么“非平凡平方根”的检测不是多余的吗？

对于第一个问题，我在网上也看到了一些人在讨论，最终没有看到讨论的结果。后来再查费马检查的资料就越看越远，都忘记自己原来是要干什么了。或许这就是数学的魅力，会吸引你不停地往前探索。但是，对于我现在的情况来讲，如果我一直探索下去，可能就没办法回来完成SICP的所有练习了。于是劝说自己先把题目做完，不在纠结于费马检查和它的变形之间的关系。不过我相信，只要有时间慢慢测试，慢慢想，应该是可以发现原始费马检查和变形费马检查之间的差别的。总之，它们不是完全等价的。留着日后有时间再看吧。

对于第二个问题，到是想一想就想明白了。因为我修改的是full-fermat-test过程，所以我测试的时候其实是对小于n大于1的数都做了这种变形的费马检查。

就如同之前的题目中说过的，对所有小于n大于1的数都进行费马检查在现实计算中是没有意义的，它消耗的时间远远大于最朴素的素数检查所需要的时间。

费马检查是一种“概率方法”，就是找几个（而不是找所有）小于n大于1的数进行费马检查，如果都通过就说明n是素数的可能性很大。

就目前考察的费马检查的变形而言，它也是一个“概率方法”，我们只能是找几个小于（n-1）大于1的数进行检查，不能去检查全部。

我们测试的时候发现所有Carmichael数都没有骗过变形的费马检查，其实是发现Carmichael数不能100%骗过变形的费马检查。以1105为例，就是说，从2到1104之间的数不是所有都满足“（ （a 的1104次方）对1105求模）等于1”。有部分满足，有部分不满足。

为了测试我的想法，我重新写了好几个过程，对3000以内的所有整数进行检查，分别进行“常规的费马检查”，“变形的费马检查”和“朴素的素数检查”。

对1105的检查结果如下：

Testing 1105

Number 1105 passed all the normal fermat test!!!!!!!!!!

Number 1105 failed the transform fermat test with 336 failures.

it it NOT a prime

1105是一个Carmichael数，测试发现，它通过了所有常规的费马检查，对常规的费马检查是“骗你没商量”。不过1105对变形的费马检查就没那么厉害了，1000多个检查数，有336个不能通过。当然，事实上1105不是一个素数。

可以看到，变形的费马检查比常规的费马检查严格一些。

不过，Carmichael数骗过变形的费马检查的可能性还是蛮高的，就像1105，大概有69%的机会骗过变形的费马检查。

所以，才需要像题目中说到一样，对“非平凡平方根”进行进一步检查。

那就继续完成题目的后半部分，就是要检查是否遇到了“1取模n的非平凡平方根”，按书上的说法，如果发现“1取模n的非平凡平方根”的话那n就不是素数。

哈，明白了，就是检查一下是否有“1取模n的非平凡平方根”而已，开始写代码吧。

额。。。，不过我有个问题，什么是“非平凡平方根”？

于是又去百度了一番，发现了“1取模n的平凡平方根”，注意，没有“非”字。

什么是“1取模n的平凡平方根”呢？就是1和(n-1)，因为这两个数的平方取模n肯定等于1，这个有数学证明，也不难，大家可以去证明。因为1和(n-1)太平常了，所以叫“平凡平方根”，对应的，如果发现有1和(n-1)以外的其它数，它的平方取模n也是等于1，这就叫“1取模n的非平凡平方根”。

明白了什么是“1取模n的非平凡平方根”，要写代码就不难了。

就是看a是不是等于1，是不是等于（n-1)，如果都不是，同时a的平方取模n等于1，那就是找到一个“1取模n的非平凡平方根”。

我定义的过程如下：

(define (nontrivial-square-root? n a)
    (and (not (= a 1))
         (not (= a (- n 1)))
         (= 1 (remainder (square a) n))))

然后调用过程如下：

(define (miller-rabin-try n a)
  (if (nontrivial-square-root? n a)
      (= (expmod a (- n 1) n) 1)
      #f))

这里没有完全按照题目的要求来做，题目是要求改进expmod方法，让它可以检测“非平凡平方根”。

作为传统的程序员，我总觉得expmod就应该只完成一个功能，检测“非平凡平方根”的工作应该交给别的过程来完成，于是我就将它们写成了两个过程，不知道在效率上会不会有问题，反正结果是对的。

最后通过Miller-rabin方法检测不同的数，这时被骗的可能性就很小了。

记住，Miller-rabin还是一个“概率方法”，一个数通过Miller-Rabin检查并不说明这个数一定是素数，只是说明这个数是素数的可能性很大。

就拿1105这个Carmichael数来说，对它做Miller-Rabin检测，1103次检测中有7次通过，虽然通过的概率很小，但是1105还是有可能通过Miller-Rabin检测的，而我们都知道，1105不是一个素数。

所以，保险的方法还是多做几次Miller-Rabin检测，充分降低被骗的可能性。