SICP：费马小定理与素数检测

SICP 1.2.6

费马小定理

关于费马小定理，读到注解的时候，还是有点震撼的。

皮埃尔?得?费马（1601-1665）是现代数论的奠基人，他得出了许多有关数论的重要理论结果，但他通常只是通告这些结果，而没有提供证明。费马小定理是在1640年他所写的一封信里提到的，公开发表的第一个证明由欧拉在1736年给出（更早一些，同样的证明也出现在莱布尼茨的未发表的手稿中）费马的最著名结果——称为费马的最后定理——是l637年草草写在他所读的书籍《算术》里（3世纪希腊数学家丢番图所著），还带有一句注释“我已经发现了一个极其美妙的证明，但这本书的边栏太小，无法将它写在这里”。 找出费马最后定理的证明成为数论中最著名的挑战。完整的解最终由普林斯顿大学的安德鲁?怀尔斯在1995年给出。

我知道费马等一些人都热衷于“纯数学”，那些被看起来毫无实用价值的“纯理论”，可这费马检查，却是全世界的服务器每秒中都要运行无数次的 RSA 算法的理论基石。就我自己而言，每天使用 SSH 的时候都要用到。而几位科学家把这这一切联系起来的过程，实在称得上是“玄妙”了。

费马小定理：

如果 n 是一个素数，a 是小于 n 的任意正整数，那么 a 的 n 次方与 a 模 n 同余。（两个数称为是模 n 的同余，如果它们除以 n 的余数相同。数 a 除以 n 的余数称为 a 取模 n 的余数，或简称为 a 取模 n）。

如果 n 不是素数，那么，一般而言，大部分的 a

对于给定的整数 n，随机任取一个 a

读起来理解不直观？那么我这么总结下吧。

假如a是一个整数，p是一个素数，那么 a^p = a (mod p)

如果a不是p的倍数，这个定理也可以写成 a^p-1 = 1 (mod p)

举个例子，67是一个素数，则2⁶⁶ mod 67 = 1。

费马检测

费马检测基于费马小定理，费马小定理：

如果n是一个素数，a是小于n的任意正整数，那么a的n次方与a模n同余。

但是如果n不是素数，一般来说大部分的 a

实现费马检查的的方法：

;; 计算一个数的幂对另外一个数取模的结果
;; 
(define (expmod base exp m)
        ;; 如果 exp 等于 0，那么返回0
  (cond ((= exp 0) 1)
        ;; 如果 exp 是偶数
        ((even? exp)
         ;; square(expmod(base (exp/2) m)) % m
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        ;; 如果不是偶数
        (else
         ;; (base * expmod(base(ex1 - 1) m)) % m
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

;; 费马检测
(define (fermat-test n)
  ;; 定义方法调用expmod
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

;; 快速求素数
(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

expmod 函数实现了求 base 的 exp次幂，然后再将结果余上m，得出来的结果再与a比较，如果相等，那么这个数可能为素数。

费马检测的C语言实现

由于 lisp 的语法太过奇葩，在这里贴一个 C/C++ 的实现吧：

#include "stdio.h"
#include "math.h"

#define TRUE 1
#define FALSE 0

typedef int Status;

int square(int n)
{
    return n*n;
}
/*---------------------------------------------------
计算一个数的幂对另一个数取模的结果,
确定是否素数所需的步数将具有θ(log n)的增长阶
---------------------------------------------------*/
int expmod(int base, int exp, int m)
{
    if (exp == 0)
    {
        return 1;
    }
    else if ((exp % 2) == 0)
    {
        return square(expmod(base, exp / 2, m)) % m;
    }
    else
    {
        return (base * (expmod(base, exp - 1, m))) % m;
    }
}

/*---------------------------------------------------
执行费马检查需要选取位于1和n-1之间（包含这两者）的数a，而后检查a的n次幂取模n的余数是否等于a.
---------------------------------------------------*/
Status fermat_test(int n)
{
    int a = rand() % n; /*a random int, less than n*/
    printf("本次随机值为%d\n", a);
    if( a == expmod(a, n, n) )
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}
/*
bool fermat_test(int n)
{
    // a is a random number in range (1~99)
    int a = rand() % (n - 1) + 1;
    return expmod(a, n, n) == a;
}
*/

Status fermat_prime(int n, int times)
{
    if (0 == times)
    {
        return TRUE;
    }
    else if( fermat_test(n) )
    {
        return fermat_prime(n, times-1);
    }
    else
    {
        return FALSE;
    }
}

Status is_prime(int n, int test_count)
{
    int i;
    // The result can be extremely reliable
    // when TEST_COUNT is big enough.
    for (i = 0; i 

费马检测是一个相对可靠的算法，而且在实现大数判断素数时可以提供相对高的效率来工作。下面看看费马检测概率问题。

概率方法

从特征上看，费马检查与我们前面已熟悉的算法都不一样。前面那些算法都保证计算的结果一定正确，而费马检查得到的结果则只有概率上的正确性。说得更准确些，如果数 n 不能通过费马检查，我们可以确信它一定不是素数。而 n 通过了这一检查的事实只能作为它是素数的一个很强的证据，但却不是对 n 为素数的保证。我们能说的是，对于任何数 n，如果执行这一检查的次数足够多，而且看到 n 通过了检查，那么就能使这一素数检查出错的概率减小到所需要的任意程度。

不幸的是，这一断言并不完全正确。因为确实存在着一些能骗过费马检查的整数：某些数 n 不是素数但却具有这样的性质，对任意整数 a 

能够证明，存在着使这样的出错机会达到任意小的检查算法，激发了人们对这类算法的极大兴趣，已经形成了人所共知称为概率算法的领域。在这一领域中已经有了大量研究工作，概率算法也已被成功应用于许多重要领域。

PS 1：能够骗过费马检查的数称为 Carmichael 数，我们对它们知之甚少，只知其非常罕见，在 100 000 000 之内有 255 个 Carmichael 数，其中最小的几个是 561、1105、1729、2465、2821 和 6601。在检查很大的数是否为素数时，所用选择是随机的。撞上能欺骗费马检查的值的机会比宇宙射线导致计算机在执行“正确”算法中出错的机会还要小。对算法只考虑第一因素而不考虑第二因素恰好表现出数学与工程的不同。

PS 2：概率素数检查的最惊人应用之一是在密码学的领域中。虽然完成 200 位数的因数分解现在在计算机上还是不现实的，但用费马检查却可以在几秒内判断这么大的数的素性。这一事实成为 Rivset、Shamir 和 Adleman (1977) 提出的一种构造“不可摧毁的密码”的技术基础，这一 RSA 算法已经成为提高电子通信安全性的一种使用广泛的技术。因为这项研究和其他相关研究的发展，素数研究这一曾被认为是“纯粹”数学的缩影，是仅仅因为其自身原因而被研究的课题，现在已经变成在密码学、电子资金流通和信息查询领域里有重要实际应用的问题了。

后话

本来想一篇文章搞定素数检测与费马小定理，但是发现这个素数检测是个大坑，里面还有很多东西挖据。既然开坑了，后面开个专题慢慢填坑吧。。。不断开坑，不断填坑，学到的东西会很多。
												
本文地址：http://www.nowamagic.net/librarys/veda/detail/2329，欢迎访问原出处。