フェルマー素数判定法
$ p\in\mathbb P\Rightarrow\,^{\forall a\in(\Z/p\Z)^*}\left\lbrack a^{p-1}\overset p\equiv1\right\rbrack
$ ^{\exist a\in(\Z/n\Z)^*}\left\lbrack a^{n-1}\overset n{\not\equiv}1\right\rbrack\Rightarrow n\not\in\mathbb P
アルゴリズム
入力: $ n\in\N\quad(n\ge3)
出力: $ nが合成数ならcomposite, さもなくば probably prime 動作
以下を$ k回繰り返す
1. $ a\in\,_{2\le}\N_{\le n-1} をランダムに選択
2. $ \gcd(a,n)\ne1なら composite を返す
3. $ a^{n-1}\overset n{\not\equiv}1なら composite を返す
probably prime を返す
評価