第24章 四重奏 (2/3)

天记录给我们吧。”

    “没有聊天记录，只有一个网名，log⁡(n)-费马检验的四重奏。”哈米德忍不住笑着说道。

    “有意思，巴希尔，这是你的强项，应该是一个关于数论的谜题吧？”罗珊娜对巴希尔眨了一下眼睛，充满期待地看着他。

    巴希尔边思考，边给罗珊娜讲解。

    费马是著名的业余数学家，他被全世界记住和熟悉，主要是因为看似简单的费马大定理，困扰了数学界将近300年，直到1995年才被证明。

    而费马小定理虽然没有那么高的知名度，但其对于数论和密码学的贡献是毫不逊色的，可以说是研究素数的基础。

    所有的素数都满足费马小定理，但反过来，满足费马小定理的整数却不一定是素数，这些不是素数的整数被称为伪素数。

    现代密码学离不开素数，密码编制者可以任意使用两个很大的已知素数A和B，可以很容易得到乘积C。

    发送密码的人只需发出C，就是我们熟悉的所谓“公钥”。

    截获C的任何人想要知道A或B，除非有密码本，否则，就需要用非常大的计算量，进行困难的整数分解。

    当C足够大时（比如2^1024），整数分解需要数月甚至数年的计算时间，也就达到了保密的目的。

    为了确保A和B是素数（否则，分解难度会指数级减小），素数判定问题就成为数论和密码学研究的一个紧迫的课题。

    使用计算机检验一个大整数n是否是素数，有很多种方法。无论哪一种方法的目标都是尽可能缩短检验时间。

    密码学中使用的整数n特别大，即使用计算机，计算次数也不能与n相关（位数会挤爆内存），最多只能与log⁡(n)相关。

    2002年，三位数学家证明了在多项式时间log^12⁡(n)之内，后来优化为log^7.5⁡(n)，可以对任意整数n进行确定性的素性检验。

    该检验方法以三位数学家的姓氏首字母命名为AKS检验法。

    遗憾的是该检验方法消耗的计算机内存过大，无法上机实用。只能停留在论文层面。

    目前，应用于军事、通讯、金融的密码，底层的素性检验程序使用的是概率检验法。

    比较流行的算法是基于米勒-拉宾检验的复合算法。

    由于费马伪素数数量太多了，不能仅使用费马小定理进行素性检验用于加密。

    巴希尔的介绍让哈米德昏昏欲睡，他连忙收住话头，指着那个奇怪的网名说：

    “作为数论研究，有些数学爱好者仍然利用费马检验，探寻整数的极为有趣的性质。比如我曾经看到过一个有意思的猜想。”巴希尔接着说：

    “对任意整数n从二进制到log⁡(n)向下取整进位制，进行费马检验，能够通过检验的伪素数除卡迈克尔数之外，必有n=(a+1)(2a+1)的形式。”

    “有爱好者在互联网发帖，公布了2^64以内的47个伪素数，均满足上述猜想。”

    “其中最小的n=242017633321201=11000401×22000801。”

    “这47个数的两个因子都

本章未完，请点击下一页继续阅读