普罗斯定理

普罗斯定理是数论的一个定理，可以判断普罗斯数是否是质数。

如果p是普罗斯数，也就是满足k2ⁿ + 1形式的数，其中k为奇数，且k < 2ⁿ，那么如果对于某个整数a，有

${\displaystyle a^{(p-1)/2}\equiv -1{\pmod {p}}\,\!}$

则p是素数。此时p称为普罗斯质数。这是一个有实际用途的方法，因为如果p是素数，任何选定的a都有百分之50的机会满足这个关系式。

若a是是模p的二次非剩余，则上述定理的逆定理也成立，因此有一种可以找a的方式，就是在最小的质数中依序找a，计算雅可比符号，直到下式成立为止

${\displaystyle \left({\frac {a}{p}}\right)=-1}$

蒙地卡罗算法（英语：蒙地卡羅）的素性测试是乱数算法，可能会产生伪阳性的结果（不是素数的数却通过素性测试），根据普罗斯定理的算法是拉斯维加斯算法，其答案都是对的，但要找到答案的时间则是随机变化。