普罗斯定理
普羅斯定理是數論的一個定理，可以判斷普羅斯數是否是質數。
如果 p 是普羅斯數，也就是滿足 k2n + 1 形式的數，其中 k 為奇數，且 k < 2n，那麼如果對於某個整數 a，有

  
    
      
        
          a
          
            (
            p
            −
            1
            )
            
              /
            
            2
          
        
        ≡
        −
        1
        
          
          (
          mod
          
          p
          )
        
        
        
      
    
    {\displaystyle a^{(p-1)/2}\equiv -1 {\pmod {p}}\,\!}
  則 p 是素數。此時 p 稱為普羅斯質數。這是一個有實際用途的方法，因為如果 p 是素數，任何選定的 a 都有百分之 50 的機會滿足這個關係式。
若 a 是是模 p 的二次非剩餘，則上述定理的逆定理也成立，因此有一種可以找 a 的方式，就是在最小的質數中依序找 a，計算雅可比符號，直到下式成立為止

  
    
      
        
          (
          
            
              a
              p
            
          
          )
        
        =
        −
        1
      
    
    {\displaystyle \left ({\frac {a}{p}}\right)=-1}
  蒙地卡羅演算法的素性測試是亂數演算法，可能會產生偽陽性的結果（不是素數的數卻通過素性測試），根據普羅斯定理的演算法是拉斯維加斯算法，其答案都是對的，但要找到答案的時間則是隨機變化。