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)
于是很快修改了我的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检测，充分降低被骗的可能性。
SICP 习题 （1.28）解题总结,布布扣,bubuko.com
原文：http://blog.csdn.net/keyboardota/article/details/19260375