5sushudingli.pdfVIP

第 5 章 素数分布的初等结果 素数性质的研究不仅是数论中最为重要的内容在和之一，而且在公钥密码学中也占有很 重要得地位．前几章我们已经对素数的某些性质进行了探讨，这一章我们仍然讨论素数的其它 性质及素数在整数中的分布问题-即素数定理，将介绍算术数列中素数分布的一个主要结果— 即算术序列中的素数定理．这一章的内容及结果在密码学中有非常广泛的应用，如整数的素分 解是许多公钥密码算法安全的理论依据．素数定理、算术序列中的素数定理分别说明了整数中、 算术序列中素数分布的平均概率，为概率算法寻找素数提供理论依据． §1 素数的基本性质与分布的主要结果介绍 本节我们简要介绍一下有关素数性质的几个结论以及素数分布的两个重要结果-素数定 理与算术序列中的素数定理，对于前面已经介绍过的有关素数的性质和定理，在此仅给出简单 回顾． 性质 1 （算术基本定理）对于任一大于 1 的整数 n ，有以下的素分解 a1 ar n p p 1 r ． p ,p , 其中 1 r 是不同的素因子，如果不考虑素因子的顺序，这种分解是唯一的． 性质 1 说明了整数与素数之间的一种关系，实际上就是整数能表示成素数的乘积的形式， 大整数的素分解是一个困难问题，在公钥密码学中，大量的密码算法就是建立在整数分解问题 的基础之上． 另外关于算术基本定理的描述，还有一个分析等价形式，即 定理 1 算术基本定理等价于 1 −1 ∞ 1 (1 ) s 1 =− ∏ s ∑ s ， ． （1） p p n 1 n 这就是著名的 Euler 恒等式． 关于素数分布，我们已经在 1章 1 节证明了素数有无穷多个，即 性质 2 素数有无穷多个， 即 lim ( ) π x ∞ →x ∞ 其中π(x ) 表示不超过 x 的素数的个数． 关于π(x ) 的主项估计已经有了精确的结果，这就是著名的素数定理，也称为不带余项估 计的素数定理． 定理 2 （素数定理） ９２ x (π)x ～ ,x →∞． （2） ln x 关于素数定理，早在 1800 年Legendre 已经提出一个精确的估计： x (π)x ～ ，x →∞． ln 1.08366x − x x du x du 另外，容易