质数的判定
舒云水
课本第3页的例1及例1后面的探究问题是“质数的判定”
问题，它有丰富的数学背景，下面给读者做一个简单介绍﹒质数有无穷多个﹒大约在2300年前欧几里得就证明了存在着无穷多个质数﹒尽管如此，迄今为止还没有发现质数的模型或产生质数的有效公式﹒因而寻找大的质数必须借助计算机一个一个地找﹒寻找大质数是数论研究的重要课题之一﹒目前找到的最大质数是梅森质数1
243112609 ，它有12978189位数，如果用普通字号将这个巨数连续写下来，它的长度可超过50公里！
读者可能会产生一个疑问：找大质数有什么用？现在最好的密码是用质数制造的，极难破译﹒
人们一直在寻找检验一个数是否为质数的方法，最近一些年有了巨大进步﹒你或许会说，检验质数有什么难？确实，看一个数是不是质数，有一种非常自然而直接的方法，这就是我们常用的试除法，即课本例1所用的算法﹒这一方法对检验不太大的数是挺实用的﹒但若数字太大，它就变得十分笨拙﹒假设你在一个快速计算机上实用高效的程序进行试除﹒对于一个10位数字的数，运行程序几乎瞬间就能完成﹒对于一个20位的数就麻烦一点了，需要两个小时﹒对于一个50位的数，则需要100亿年﹒这已经大得不可想象﹒前面讲过最好的密码是用质数制造的，它是用介于60位到100位之间的两个质数制造的，这种计算正是制造这种密码的需要﹒当今庞大的国际数
据通讯网络能安全运行，就得益于这种密码﹒
如何确定一个100位的数是否为质数呢？数学家做了许多努力，在1980年左右找到了目前可用的最好方法﹒数学家阿德勒曼，鲁梅利，科恩和伦斯特拉研究出一种非常复杂的方法﹒现在以他们的名字的第一个字母命名为ARCL检验法﹒在上面提到的那类计算机上进行ARCL检验，对20位的数只需10秒钟，对50位的数用15秒，100位的数用40秒﹒如果要检查1000位的数，一个星期也就够了﹒可以相信，随着人们对质数的判定算法的研究不断深入及计算机技术的迅猛发展，我们会找到更好更快地检验一个大数是否为质数的方法，发现更多更大的质数﹒。