普拉特证书

普拉特证书是一种基于费马小定理逆定理的素性证书。在普拉特（Pratt，1975）的工作之前，Lucas-Lehmer 检验一直被纯粹视为一种在很多时候有效的启发式方法（Knuth 1969）。普拉特（1975）表明，通过将 Lehmer 的素性启发式方法递归地应用于 的因子，可以使其成为一种非确定性过程。作为这一结果的推论，普拉特（1975）成为第一个证明由此产生的树意味着素因数分解属于复杂度类 NP 的人。

要生成普拉特证书，假设 是一个正整数，而 是 的素因子的集合。假设存在一个整数 （称为“证人”），使得 ，但当 是 之一时， (mod )。那么费马小定理逆定理指出 是素数（Wagon 1991，第 278-279 页）。

通过将费马小定理逆定理应用于 并递归地应用于 的每个声称的因子，可以生成给定素数的证书。换句话说，普拉特证书给出了数字 是乘法群 (mod ) 的原根的证明，这与 的阶为 这一事实一起，证明了 是一个素数。

上图给出了 素性的证书。短划线右边的数字是左边数字的证人。 对于 由 给出。由于 但 , , (mod 7919)，7 是 7919 的证人。素因子 是 2、37 和 107。2 是所谓的“自证人”（即，它被认为是素数而无需进一步证明），其余的证人显示为嵌套树。它们共同证明 7919 确实是素数。因为它需要 的因式分解，所以普拉特证书的方法最适合应用于小数字（或那些已知 的 易于分解的数字）。

对于小数字而言，普拉特证书的生成速度比其他类型的素性证书更快。Wolfram 语言函数ProvablePrimeQ[n] 在 Wolfram 语言包中PrimalityProving`因此，仅对于超过一定限制的数字（默认情况下为 ），才生成 Atkin-Goldwasser-Kilian-Morain 证书，而对于较小的数字则生成普拉特证书。