本书是“世界数学名题欣赏丛书”之一。素数判定与大数分解问题在数论中占有重要地位,远古时代人们就十分重视它的研究。近年来,由于计算机科学的发展,使这一古老问题焕发了青春,形成了数论中的新分支-计算数论。本书完整的介绍了素数判定问题的全部历史和理论,阐明了它在纯数学研究和应用数学研究中的地位,及其在当代科学中的实用价值。
序言
一 数论中的基本算法
1.算法及其计算量的概念
2.数论中的基本算法
二 素性判别
1.素性判别的一般理论
2.一个经典的结果
3.费马小定理和卡米歇尔数
4.从努卡斯到威廉斯
5.素性判别与广义黎曼猜想
6.一种概率算法
7.目前最有效的艾德利曼——鲁梅利算法
8.一些特殊的素数及其判别
9.在计算机上实施素数判别的战略
三 大数分解
1.经典的方法
2.蒙特卡罗方法
3.连分数法
4.二次筛法
5.p-1法和p+1法
附录:广义黎曼猜想
参考文献
中英文人名表
《<数学中的小问题大定理>丛书(第三辑):素数判定与大数分解》:
继勒默和卜利尔哈特等人之后,威廉斯和加得等人注意到,有一部分自然数n,其n±1很不容易被分解,但是n2+1或n2±n+1的因子却容易分解出来,或者,对某些n,虽然n±1可以分解一些因子出来,但所分解出来的因子还不足以满足用上面讲述的方法作n的素性判别的条件,这时,就要设法利用n2+1或n2±n+1的因子来判别n的素性,威廉斯和加得等人对勒默和卜利尔哈特的工作作了仔细的研究后,发现可以利用一种推广的努卡斯序列(勒默对努卡斯序列的推广工作)来建立用n2+1,n2±n+1的因子作素性判别的方法,他们得到了很多结果,这些结果的形式同定理2.5到定理2.9相类似,只是将n-1相应地换成n2+1或n2±n+1,将诸如(P),(B),(B')等检验条件组相应地换成用推广的努卡斯序列表述的条件组,遗感的是,即使不加证明地叙述出这些结果也要占去大量篇幅,故此处略去不讲,有兴趣者可参见。
……