普罗斯定理 普罗斯定理是數論的一個定理可以判斷普罗斯数是否是質數 如果p是普罗斯数也就是滿足kn  形式的數其中k為奇數且k  n那么如果对于某个整数a有 a  p          mod p  displaystyle apequiv pmod p 则p是素数此時p稱為普罗斯質數这是一个有实际用途的方法因为如果p是素数任何选定的a都有百分之的機會滿足這個關係式 若a是是模p的二次非剩余則上述定理的逆定理也成立因此有一種可以找a的方式就是在最小的質數中依序找a計算雅可比符号直到下式成立為止  a p     displaystyle leftfrac apright 蒙地卡羅演算法英语蒙地卡羅的素性测试是亂數演算法可能會產生偽陽性的結果不是素數的數卻通過素性测试根據普罗斯定理的演算法是拉斯維加斯算法其答案都是對的但要找到答案的時間則是隨機變化