普罗斯定理
如果p是普罗斯数,也就是滿足k2n + 1形式的數,其中k為奇數,且k < 2n,那么如果对于某个整数a,有
则p是素数。此時p稱為普罗斯質數。这是一个有实际用途的方法,因为如果p是素数,任何选定的a都有百分之50的機會滿足這個關係式。
若a是是模p的二次非剩余,則上述定理的逆定理也成立,因此有一種可以找a的方式,就是在最小的質數中依序找a,計算雅可比符号,直到下式成立為止
蒙地卡羅演算法的素性测试是亂數演算法,可能會產生偽陽性的結果(不是素數的數卻通過素性测试),根據普罗斯定理的演算法是拉斯維加斯算法,其答案都是對的,但要找到答案的時間則是隨機變化。
舉例
例如:
- 对于p = 3,21 + 1 = 3能被3整除,所以3是素数。
- 对于p = 5,32 + 1 = 10能被5整除,所以5是素数。
- 对于p = 13,56 + 1 = 15626 能被整除,所以13是素数。
- 对于p = 9,不存在a使得a4 + 1能被9整数,所以9不是素数。
截至2009年[update],已知最大的普罗斯質數是19249 · 213018586 + 1,是由十七或者破產所找到的,有3,918,990個數字,是已知不是梅森素数的素数中,數值最大的質數[1]。
歷史
法蘭西斯·普羅斯(1852–1879)在1878年發表了這個證明。