素數判定

又稱素性判定。這是一個古老而基本的數論問題，由於與密碼學的密切關係而成為當今計算數論的重要課題。一個古老的素性判定法是試除法。因為整數N＞1是素數的充分必要條件是它不能被任何不大於N1/2的素數整除，因而可用所有不大於N1/2的素數試除N來判定N是否為素數。這個方法的計算量不超過C×2(lnN)/2，式中C是一個正常數，因而這方法對大的N是不可行的。

20世紀70年代以來人們基於同餘理論、代數數論、橢圓曲線（見代數曲線）和概率論的結果提出了各種不同的素數判定方法和快速算法，藉助於現代計算技術找出了許多大素數，其中有許多梅森素數（見梅森數），也有其他形式的素數。例如：2000年D.S.斯考脱髮現169 719×2557 557＋1是167 847位素數，但不是梅森數。 ^[1]