默森的数

  17世纪,一个具有69位数字的数被法国数学家M·默森推测为素数.19842月,一批数学家成功地用计算机解决了这个历经三个世纪的古老谜题.在经过32小时又 12分钟之后,这一默森的数所包含的三个因子(下表列出)终于被发现.

 

  数的分解的技术使应用密码的人感到担忧,因为现代的许多密码系统,为了保持密码的可靠性而选用了一些位数很大而又难于分解的数作为设密的工具.

  分解一个数是指把数分为较小素数的乘积.这项工作对于较小的数可用小于它的素数来试除,因而比较简单.但对于较大的数,则需要其他办法.这是因为随着数的增大,前述方法的计算量将指数般地增加.对于一个有60位的数,即使用每秒运行10亿次的计算机,也要花上几千年.

  19851986年,R·西韦门和P·曼特哥美利发展了一种既快又廉价的方法.该法用在微电脑上与用在大型计算机上效果相当.他们新近完成了一个81位数的因子分解,用了八台微电脑,每台运行150小时.