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 都将满足上面的关系。这就引出了下面这个检查素数的算法：

对于给定的整数 n，随机任取一个 a < n 并计算出 an 取模 n 的余数。如果得到的结果不等于 a，那么 n 就肯定不是素数。如果它就是 a，那么 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 < n 都将满足以上关系。费马检测的方法是取多个随机出a < n并计算出a的n次方取模n的余数并判断是否满足费马小定理，如果这种随机检测的多种抽样结果都满足费马小定理，那么将断定n是一个素数。

实现费马检查的的方法：

;; 计算一个数的幂对另外一个数取模的结果
;; 
(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 < test_count; i++)
    {
        if (!fermat_test(n))
        {
            return FALSE;
        }
    }

    return TRUE;
}

int main()
{
    /*
    2012-11-05 by www.nowamagic.net
    */
    int a, b, c, d, rs;
    int base, exp, m;
    int opp;

    printf("\n1.求一个数的平方 \n2.计算一个数的幂对另一个数取模的结果  \n3.费马检测 ");
    printf("\n4.循环费马检测  \n5.留着 ");
    printf("\n0.退出 \n请选择你的操作：\n");
    while(opp != '0')
    {
        scanf("%d",&opp);
        switch(opp)
        {
        case 1:
            printf("请输入一个整数：");
            scanf("%d",&a);
            rs = square(a);
            printf("其平方为：%d\n", rs);
            break;

        case 2:
            printf("请分别输入底数，指数与另一个数：");
            scanf("%d",&base);
            scanf("%d",&exp);
            scanf("%d",&m);
            rs = expmod(base, exp, m);
            printf("其结果为：%d\n", rs);
            break;

        case 3:
            printf("请输入一个需要费马检测的数：");
            scanf("%d",&b);
            rs = fermat_test(b);
            printf("其结果为：%d\n", rs);
            break;

        case 4:
            printf("请输入一个需要费马检测的数n：");
            scanf("%d",&b);
            printf("请再输入一个循环到的数(1<= m < n)：");
            scanf("%d",&c);
            rs = is_prime(b, c);
            printf("其结果为：%d\n", rs);
            break;

        case 5:
            printf("预留位\n");
            break;

        case 6:

            break;

        case 0:
            exit(0);
        }
    }

    return 0;
}

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

概率方法

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

不幸的是，这一断言并不完全正确。因为确实存在着一些能骗过费马检查的整数：某些数 n 不是素数但却具有这样的性质，对任意整数 a < n，都有 an 与 a 模 n 同余。由于这种数极其罕见，因此费马检查在实践中还是很可靠的。也存在着一些费马检查的不会受骗的变形，它们也像费马方法一样，在检查整数 n 是否为素数时，选择随机的整数 a < n 并去检查某些依赖于 n 和 a 的关系。另一方面，与费马检查不同的是可以证明，对任意的数 n，相应条件对整数 a < n 中的大部分都不成立，除非 n 是素数。这样，如果 n 对某个随机选出的 a 能通过检查，n 是素数的机会就大于一半。如果 n 对两个随机选择的 a 能通过检查，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，欢迎访问原出处。