米勒-拉宾素性检验

米勒-拉宾素性检验是一种素数判定法则，利用随机化算法判断一个数是合数还是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。

首先介绍一个相关的引理。我们发现 ${\displaystyle 1^{2}modp}$ > 3, an odd integer to be tested for primality;Input #2: , a parameter that determines the accuracy of the testOutput: if is composite, otherwise

write  − 1 as 2· with  odd by factoring powers of 2 from  − 1WitnessLoop: repeat  times:   pick a random integer  in the range     ←  mod    if  = 1 or  =  − 1 then      continue WitnessLoop   repeat  − 1 times:       ← 2 mod       if  =  − 1 then         continue WitnessLoop   return return 

使用模幂运算，这个算法的时间复杂度是${\displaystyle O(k{\log }^3<!--\; \; -->n)}$ log2 log log  log log log ) = Õ( log2).

如果我们加入最大公因数算法到上述算法中，我们有时候可以得到 ${\displaystyle n}$ 的因数，而不仅仅是证明 ${\displaystyle n}$ 是一个合数。例如，若 ${\displaystyle n}$ 是一个基于${\displaystyle a}$ 的可能的素数，但不是一个大概率素数，则${\displaystyle gcd((a^{d}modn)-<!--\; -\; -->1,n)}$或${\displaystyle gcd((a^{2^{r}d}modn)-<!--\; -\; -->1,n)}$将得到 ${\displaystyle n}$ 的因数。如果因式分解是必要的，这一${\displaystyle GCDs}$算法可以加入到上述的算法中，代价是增加了一些额外的运算时间。

例如，假设 ${\displaystyle n=341}$，则${\displaystyle n-<!--\; -\; -->1=340=85\ast <!--\; \ast \; -->4}$.于是${\displaystyle 2^{85}mod341=32}$，这也告诉我们 ${\displaystyle n}$ 不是一个大概率素数，即 ${\displaystyle n}$ 是一个合数。如果这个时候我们求最大公因数，我们可以得到一个${\displaystyle n=341}$的因数：${\displaystyle gcd((2^{85}mod341)-<!--\; -\; -->1,341)=31}$.这时可行的，因为${\displaystyle n=341}$是一个基于2的伪素数，但不是一个“强伪素数”。

下面是根据以上定义而使用Magma语言编写的“米勒-拉宾”检验程序。