邓从政

（凯里学院，贵州凯里 556011）

0 引言

素数是数论中被研究最广泛的一类数，除在同余理论、整除理论、不定方程理论及指数和原根这些基础问题经常用到之外，在密码学和编码学上也有广泛地应用，如椭圆曲线密码、RSA 密码、圆锥曲线密码三大公钥密码体制的加密和解密都依赖于大素数［1］.长期以来找出一个大整数范围内的所有素数是数论中被研究最广泛的一个课题，其中素数的数量、素数的分布、素数表的构造都依赖于现存找到的素数，古典筛法可以找出不超出给定的一个正整数范围内的所有素数，而且十分有效，它是构造素数表的一个实用方法［2］.本文通过Mobius函数及其独特性质从理论上证明古典筛法的有效性，为寻找素数提供一个简洁而实用的算法.

1 古典筛法原理

1.1 算术基本定理

一个不等于1 的正整数不是合数就是素数，素数只有1 和它本身两个素因数，而合数除了这两个因数之外还有其他的真因数，那么怎样把任意一个整数进行因数分解呢?对此我们有下面的唯一分解定理即算术基本定理［3］.

定理1（算术基本定理）设整数a≥2，那么a一定可表为若干素数的乘积，即a=p1p2...ps，其中pj(1 ≤j≤s)是素数，且在不计次序的意义下上述表法是唯一的.

推理1设整数a≥2，那么a一定可表为若干素数的乘积，即其中pj(1 ≤j≤s)是素数，且在不计次序的意义下上述表法是唯一的.

根据上述算术基本定理，我们可以得到一个寻找素数的算法，即古典筛法，也叫Eratosthenes筛法.再由最小自……