素数的判定sushu de panding

确定一个给定的正整数n是不是素数，最简单的方法是，先求出n ，然后用不大于n的所有素数去除n，若都不能整除，则n是一个素数.例如，要确定191是不是素数，先求出191≈13.7，用不大于13. 7的素数2, 3, 5, 7, 11,13去除191，结果都不能整除，由此可知191是素数.如果n是一个非常大的整数，这时不超过n的全体素数，已经不能通过查手边的素数表得出，那么可以使用电子计算机.给它编一个程序，用所有不大于n的正奇数去除n，当然这是非常耗费时间的工作.
第一个判定一个整数是素数的充分必要条件是威尔逊定理，但由于它的计算量太大，很不实用. 费尔马定理提供了判定素数的一个必要条件 (参照 “费尔马定理”)，但不是充分的，即其逆命题不成立，这只须举出一个反例就够了.例如，2341≡1 (mod341)，且(2,341)=1，但341=11·31不是素数. 称这样的整数为伪素数，已经证明了伪素数有无穷多个.
对于费尔马定理之逆，在适当补充条件之后，就可以构成判定素数的充分条件. 第一个这种类型的充分条件是鲁卡斯在1876年提出，由D. N.莱梅1927年简化的下述定理：
设n是一个正整数，若存在整数a，使得

a^n-1≡1(modn)

并且a^(n-1)/q≢1(modn)对n-1的所有素因数q都成立，则n是一个索数.
例 判定一个大整数1009是一个素数. 令n=1009,a=11，经过计算可知，11¹⁰⁰⁸≡1 (mod1009)，因为1008=2⁴·3²·7，即1008的素因数只有2,3,7.现在计算下面三个同余式

11^1008/2 =11⁵⁰⁴≡-1(mod1009),
11^1008/3 =11³³⁶≡ 374(mod1009),
11^1008/7 = 11¹⁴⁴ =935(mod1009).

这三个同余式的右端都不同余于1 (mod1009)，因此由上述定理可知，1009是素数.
最近，一个相当有效的素数判定法，已经由阿德尔曼等人提出(可参看L. M. Adleman,Annals of Mathe-matics,117 (19831,173—206).
由于对莫森素数有特别的判定法，它有可能判定特别大的莫森数是素数，这就是鲁卡斯在1876年提出，1930年经莱梅改进的鲁卡斯-莱梅判定法：
令p是一个素数，并令Mp=2^p-1表示莫森数，用下面的方式定义一个序列：
令r₁＝4，对k≥ 2，令r_k≡Tk-₁²-2 (modMp),0≤T_ke，则M_p是素数，当且仅当r_p-1≡0 (modM,).例如莫森素数M₂₁₆₀₉₁，就是主要用这个方法找出来的.