素数判定

素数判定（英语：primality test），判断给定的正整数是否为素数。又称素性判定。这是一个古老而基本的数论问题，由于与密码学的密切关系而成为当今计算数论的重要课题。一个古老的素性判定法是试除法。

因为整数N＞1是素数的充分必要条件是它不能被任何不大于N^1/2的素数整除，因而可用所有不大于N^1/2的素数试除N来判定N是否为素数。这个方法的计算量不超过C×2^(lnN)/2，式中C是一个正常数，因而这方法对大的N是不可行的。20世纪70年代以来人们基于同余理论、代数数论、椭圆曲线（见代数曲线）和概率论的结果提出了各种不同的素数判定方法和快速算法，借助于现代计算技术找出了许多大素数，其中有许多梅森素数，也有其他形式的素数。例如：2000年D.S.斯考脱发现169 719×2^557 557＋1是167 847位素数，但不是梅森数。