素數(shù)判定簡介

素數(shù)判定，判斷給定的正整數(shù)是否為素數(shù)。

又稱素性判定。這是一個古老而基本的數(shù)論問題，由于與密碼學的密切關系而成為當今計算數(shù)論的重要課題。一個古老的素性判定法是試除法。因為整數(shù)N＞1是素數(shù)的充分必要條件是它不能被任何不大于N1/2的素數(shù)整除，因而可用所有不大于N1/2的素數(shù)試除N來判定N是否為素數(shù)。這個方法的計算量不超過C×2(lnN)/2，式中C是一個正常數(shù)，因而這方法對大的N是不可行的。20世紀70年代以來人們基于同余理論、代數(shù)數(shù)論、橢圓曲線（見代數(shù)曲線）和概率論的結果提出了各種不同的素數(shù)判定方法和快速算法，借助于現(xiàn)代計算技術找出了許多大素數(shù)，其中有許多梅森素數(shù)（見梅森數(shù)），也有其他形式的素數(shù)。例如：2000年D.S.斯考脫發(fā)現(xiàn)169?719×2557?557＋1是167?847位素數(shù)，但不是梅森數(shù)。 2100433B

圓周上相鄰的質數(shù)域整數(shù)之和全部為素數(shù)的圓謂之素數(shù)圓。

基礎質數(shù)域通式=2[N 1]。基礎質數(shù)域最大倍數(shù)通式=4[N 1]。孿素對圈定于{4[N 1]}內。

如：[基礎質數(shù)域10]的素數(shù)圓[....10 3 8 5 6 74 9 2 1...]圈定的孿素對[13 11]在[20]內。2100433B

圓周整數(shù)序位無關質數(shù)域整數(shù)序位。