玛娅文学

手机浏览器扫描二维码访问

第24章 四重奏（第3页）

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

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

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

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

巴希尔接着说：

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

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

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

“这47个数的两个因子都是素数吗？”

罗珊娜好奇地问道。

“你说到关键了，按照猜想，a+1可以是素数也可以是合数。如果我没记错，其中46个数都只有两个素因子，只有一个n的a+1是三因子合数，2a+1是个素数，这个n是由四个素因子组成的合数。”

罗珊娜终于听明白了，问道：

“四重奏指的是四个素因子？对于小于2^64所有整数进行费马检验，进位制从2至log（n），能通过检验的非卡迈克尔数的伪素数只有一个四因子合数。这个满足条件的最小的四因子合数到底是哪个数呀？”

巴希尔打开自己的电脑，从收藏夹中找到了包含47个数的表格，把那个唯一的四因子伪素数抄在了黑板上：

n=168562580058457201=103×307×9181×580624801

其中，a+1=103×307×9181=290312401。

“这就是log?（n）-费马检验的四重奏！”

巴希尔得意地说道。

哈米德赞许地看着巴希尔问道：

“你们给那个凯兹回复的内容就是这四个数字，对吧？”

巴希尔点头表示认可，罗珊娜若有所思地说道：

“回复这四个数字仅仅是解开了他出的谜题，为了使聊天进行下去，我们也需要起一个自带谜题的网名，考考他。”

“这个有意思。”

巴希尔将网名输入栏空着，在下面输入了聊天内容：

“103，307，9181，580624801”

巴希尔将键盘推给了罗珊娜，顽皮地做了一个请的动作。罗珊娜想了想，在网名栏中输入：

“O（√nln?（n））-黎曼猜想的三和弦。”