ミラー・ラビン素数判定法

ミラー・ラビン素数判定法、またはラビン・ミラー素数判定法は、確率的素数判定法です。これは、フェルマー素数判定法やソロベイ・ストラッセン素数判定法と同様に、与えられた数が素数である可能性が高いかどうかを判定するアルゴリズムです。

これは、多項式時間で決定論的な素数判定法を探求する上で歴史的に重要な意義を持つ。その確率的変種は、最も単純かつ高速な判定法の一つとして、現在でも広く実用化されている。

ゲイリー・L・ミラーは1976年にこのテストを発見した。ミラーのテストは決定論的だが、その正しさは未証明の拡張リーマン予想に依存している。^{[ 1 ]}マイケル・O・ラビンは1980年にこれを修正して無条件の確率的アルゴリズムを得た。^{[ 2 ]}^{[ a ]}

数学的概念

フェルマー素数判定法やソロヴェイ・シュトラッセン素数判定法と同様に、ミラー・ラビン素数判定法は、素数に対して成り立つことが知られている特定の性質が、判定対象の数に対して成り立つかどうかをチェックする。

強力な素数

その性質は次のとおりです。 $n>2$ さあ、書こう $n-1$ として $2sd$ どこ $s$ は正の整数であり、 $d$ は奇数の正の整数です。整数を考えてみましょう。 $a$ 基底と呼ばれるもので、互いに素である。 $n$ 。それから、 $n$ は、以下の合同関係のいずれかが成り立つ場合、aの基礎となる強い素数であると言われます。

$a^{d}\equiv 1\!\!\!{\pmod {n}}$ 、または
$a^{2^{r}d}\equiv -1\!\!\!{\pmod {n}}$ 一部の人にとって $0\leq r<s$ 。

これは、まずチェックすることに簡略化されます。 $a^{d}\equiv 1{\pmod {n}}$ その後 $a^{2^{r}d}\equiv n-1{\pmod {n}}$ 連続する値に対して $r$ 。各値について $r$ 式の値は、前の値に対して得られた値を使用して計算できます。 $r$ モジュラスの下で二乗することにより $n$ 。

このテストの根底にある考え方は、 $n$ は奇素数であり、以下の2つの事実によりテストに合格します。

フェルマーの小定理により、 $a^{n-1}\equiv 1{\pmod {n}}$ （この性質だけで、素数と底の確率というより弱い概念が定義される） $a$ （フェルマー判定法の基礎となるもの）
1を法とする唯一の平方根 $n$ 1と-1です。

したがって、対偶により、 $n$ ベースに対する強い可能性の高い素数ではない $a$ 、それから $n$ 間違いなく複合的で、 $a$ は、 $n$ 。

しかし、この性質は素数の正確な特徴付けではありません。 $n$ 複合材料ではあるが、それでもベースに対する強力な可能性のあるプライムである可能性がある $a$ この場合、それは強い擬素数と呼ばれ、 $a$ 彼は嘘をつくのがうまい。

塩基の選択

合成数は、すべての基数に対して同時に強い擬素数となることはありません（すべての基数に対してフェルマー擬素数が存在するフェルマー素数判定法（カーマイケル数）とは対照的です）。しかし、証拠を見つける簡単な方法は知られていません。素朴な解決策としては、考えられるすべての基数を試すことですが、これは非効率的な決定論的アルゴリズムになります。ミラー判定法は、これよりも効率的な変種です（下記の 「ミラー判定法」の項を参照）。

別の解決策は、塩基をランダムに選択することです。これにより、高速な確率的テストが得られます。nが合成数である場合、ほとんどの塩基が証拠となるため、テストはnが合成数であることをかなり高い確率で検出します（下記の 「精度」の項を参照）。必要な数の独立に選択された塩基の結果を組み合わせることで、偽陽性の確率を任意に低い値まで迅速に低減できます。これがミラー・ラビン検定です。nが何らかの塩基の擬似素数である場合、別の塩基の擬似素数である可能性が高いため、多くの塩基を試すことには収穫逓減の法則があるようです。^{[ 4 ]}^{： §8}

$a$ $\equiv 1 (mod$ $n$ $)の場合、$ $a d$ $\equiv 1 (mod$ $n$ $)$ が自明に成り立つことに注意してください。これは、合同関係が指数法則と互換性があるためです。また、 $d$ が奇数であるため、 $a$ $\equiv -1 (mod$ $n$ $)の場合、$ $a$ $d$ $=$ $a$ $2$ $0$ $d$ $\equiv -1 (mod$ $n$ $)$ が自明に成り立ちます。これが、ランダムな $aが通常$ $1 <$ $a$ $<$ $n$ $- 1 の$ 範囲で選択される理由です。

任意に大きな $n を$ テストする場合、2、3、...、 $n - 2$ の数の間で証人と強い嘘つきの分布がわからないため、基底をランダムに選択することが不可欠です。^{[ b ]}

しかし、あらかじめ選択された少数の小さな塩基のセットを用いることで、事前に計算された最大値までのすべての複合語を確実に識別できます。この最大値は一般的に塩基の数に比べてかなり大きい値です。これにより、nが十分に小さい場合、非常に高速な決定論的テストが可能になります（下記の「少数の塩基セットに対するテスト」の項を参照）。

証明

nが素数である場合、1を法とするnの平方根は1と-1のみであることを証明します。

証拠

確かに、1と−1をnで割った平方根は常に1になります。あとは、 nで割った1の平方根が他に存在しないことを示すだけです。これは、ある体上の多項式は次数以上の根を持たないというより一般的な事実の特殊な場合であり、ここでは有限体Z / nZ上の多項式X² ⁻ 1に適用されています（この定理は、多項式に対するユークリッド除法の存在から導かれます）。以下に、より初等的な証明を示します。xがnで割った1の平方根であると仮定します。すると、次のようになります。

(x-1)(x+1)=x^{2}-1\equiv 0{\pmod {n}}.

つまり、n は積( x − 1)( x + 1)を割り切ります。ユークリッドの補題によれば、nは素数なので、因数x − 1またはx + 1 のいずれかを割り切ります。これは、 x がnを法として 1 または −1 と合同であることを意味します。

nが奇素数である場合、n はa を基数とする強い確率の素数であることを証明します。

証拠

nが奇素数で、n − 1 = 2 ^s dと書く場合（sは正の整数、dは奇数の正の整数）、フェルマーの小定理より次のようになる。

a^{2^{s}d}\equiv 1{\pmod {n}}.

数列の各項 $a^{2^{s}d},a^{2^{s-1}d},\dots ,a^{2d},a^{d}$ は前の項の平方根です。最初の項は 1 と合同なので、2 番目の項は 1 の平方根をn で割ったものです。前の補題により、これは 1 または −1 のいずれかをnで割ったものと合同です。これが −1 と合同であれば、これで終わりです。そうでなければ、これは 1 と合同なので、推論を繰り返すことができます。最終的に、いずれかの項が −1 と合同であるか、すべての項が 1 と合同であり、特に最後の項a ^dは合同です。

例

では、 $n=221$ 素数です。 $n-1{\text{ as }}2^{2}\times 55$ ということで、 $s=2{\text{ and }}d=55$ ランダムに番号を選択します $a$ そのため $2\leq a\leq n-2$ 。

言う $a=174$ :

${\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &174^{{2^{0}}55}{\text{ mod }}221\equiv 174^{55}\equiv 47{\text{. Since }}47\neq 1{\text{ and }}47\neq n-1{\text{, we continue.}}\\&174^{{2^{1}}55}{\text{ mod }}221\equiv 174^{110}\equiv 220=n-1\end{aligned}}$

以来 $220\equiv -1{\text{ mod }}n$ 221は素数か、174は221に対する強い嘘つきのどちらかです。別のランダムな値を試してみましょう。 $a$ 今回は $a=137$ :

${\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &137^{{2^{0}}55}{\text{ mod }}221\equiv 137^{55}\equiv 188{\text{. Since }}188\neq 1{\text{ and }}188\neq n-1{\text{, we continue.}}\\&137^{{2^{1}}55}{\text{ mod }}221\equiv 137^{110}\equiv 205\neq n-1\end{aligned}}$

したがって、137 は 221 の合成数の証拠であり、174 は実際には強い嘘つきでした。これは 221 の因数 (13 と 17) については何も教えてくれないことに注意してください。ただし、後のセクションの 341 の例では、これらの計算がnの因数を生成することがあることを示しています。

aの値を選択するための実践的なガイドについては、「少数の基底セットに対するテスト」を参照してください。

ミラー・ラビン検定

このアルゴリズムは擬似コードで次のように記述できます。パラメータk はテストの精度を決定します。ラウンド数が多いほど、結果の精度が高くなります。^{[ 6 ]}

入力 #1 : n > 2、素数判定対象の奇数 入力 #2 : k、実行する判定回数 出力: nが合成数と判定された場合は「 composite」 、それ以外の場合は「 probable prime」

s > 0 かつd odd > 0でn − 1 = 2 ^s dとなるようにする# n − 1から 2 のべき乗を因数分解するk回繰り返す : a ← random(2, n − 2) # nは常に 1 とn − 1 を 基数とする素数であるx ← a ^d mod n s回繰り返す: y ← x 2 ^mod n if y = 1 and x ≠ 1 and x ≠ n − 1 then # 1 を法とする非自明な平方根return “ composite ” x ← y if y ≠ 1 then return “ composite ” return “ probably prime ”

複雑

繰り返し二乗演算を使用すると、このアルゴリズムの実行時間は、 n桁の数に対して $O (k n 3)となり、$ kは実行されるラウンド数です。したがって、これは効率的な多項式時間アルゴリズムです。たとえばSchönhage–Strassen アルゴリズムのような FFTベースの乗算では、実行時間を $O($ $k$ $n$ $2$ $log$ $n$ $log log$ $n$ $) =$ $Õ$ $($ $k$ $n$ $2$ $)$ に短縮できます。

正確さ

素数判定の誤りは、合成数が素数であると判定される確率によって測定されます。試行する基数a の数が多いほど、判定の精度は向上します。nが合成数である場合、基数aのうちnに対して強い嘘をつく基数は最大で 1/4 であることが示されます。[ ²^]^[⁷^]^[⁸^]^その結果、nが合成数である場合、ミラー・ラビン判定をk回実行すると、 n が素数であると判定される確率は最大で 4 ⁻^kになります。

これは、最悪ケースのエラー限界が 2 ⁻^kであるSolovay–Strassen テストよりも改善されています。さらに、Miller–Rabin テストは、任意の合成数nに対して、 nの強い嘘つきの集合がnのEuler 嘘つきの集合の部分集合であり、多くのnに対して部分集合が適切であるという意味で、Solovay–Strassen テストよりも厳密に強力です。

さらに、nの値が大きい場合、合成数が素数であると宣言される確率は、4 ^{− k}よりかなり小さくなることが多い。たとえば、ほとんどの数nの場合、この確率は 8 ^{− k}で制限される。nの値が大きいほど、この上限を無効にする数nの割合はなくなる。^[⁹^]したがって、平均的なケースでは 4 ⁻^kよりはるかに高い精度が得られ、この事実は素数を生成するために利用できる(下記参照)。ただし、暗号攻撃者が素数判定を回避するために慎重に選択された擬似素数を送る可能性があるため、確率分布が制御されていない素数を検証するために、このような改善された誤差範囲に頼るべきではない。 ^[^c^] このような状況では、最悪の場合の誤差範囲 4 ⁻^kのみに頼ることができる。

上記の誤差尺度は、 k回のテスト後に合成数が強い素数であると判定される確率であり、数学的には条件付き確率である。 $\Pr(M\!R_{k}\mid \lnot P)$ ここで、Pはテスト対象の数が素数である事象、 MR _kはk回のミラー・ラビン検定に合格する事象である。我々はしばしば、条件付き確率の逆数に関心を持つ。 $\Pr(\lnot P\mid M\!R_{k})$ : 強い素数であると宣言された数が実際には合成数である確率。これら 2 つの確率は、ベイズの法則によって関連付けられています。

{\begin{aligned}\Pr(\lnot P\mid M\!R_{k})&={\frac {\Pr(\lnot P\land M\!R_{k})}{\Pr(\lnot P\land M\!R_{k})+\Pr(P\land M\!R_{k})}}\\&={\frac {1}{1+{\frac {\Pr(M\!R_{k}\mid P)}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{\Pr(\lnot P)}}}}\\&={\frac {1}{1+{\frac {1}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{1-\Pr(P)}}}}\end{aligned}}

最後の式では、すべての素数が強い素数として正しく報告される（このテストには偽陰性がない）という事実を利用して式を簡略化しました。分母の左側を削除することで、単純な上限を導き出します。

\Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)

したがって、この条件付き確率は、上で議論した誤差尺度（4 ^{− k}で制限される）だけでなく、入力数値の確率分布にも関係しています。一般的には、前述のように、この分布は暗号学的攻撃者によって制御されるため未知であり、したがって、について多くを推測することはできません。 $\Pr(\lnot P\mid M\!R_{k})$ しかし、素数を生成するためにミラー・ラビン検定を使用する場合（下記参照）、分布は生成器自体によって選択されるため、この結果を利用できます。

複数のテストを組み合わせる

コールドウェル^{[ 11 ]}は、異なる基数に対する強力な確率素数テストが、追加の素数テストを提供する場合があることを指摘している。強力なテストがnを法とする1の2つ以上の平方根の存在をチェックするのと同様に、そのような2つのテストは、−1の2つ以上の平方根の存在をチェックできる場合がある。

確率素数判定の過程で、2 つの基数aとa ′に遭遇し、 $a^{2^{r}d}\equiv a^{\prime \,2^{r'}d}\equiv -1{\pmod {n}}$ r、r ′ ≥ 1の場合。これは、テストの一部として 2 つの平方根を計算したことを意味します。 $a^{2^{r-1}d}\equiv \pm a^{\prime \,2^{r'-1}d}{\pmod {n}}$ nが素数であれば、これは常に成り立つはずです。そうでなければ、−1の平方根が2つ以上見つかり、nが合成数であることが証明されます。

これはn ≡ 1 (mod 4)の場合にのみ可能であり、2 つ以上の基底aに対してa ^d ≢ ±1 (mod n )となるような確率素数テストに合格しますが、基本的なミラー・ラビンテストへの安価な追加です。

決定論的変種

ミラーテスト

ミラー・ラビンアルゴリズムは、ある一定の制限値以下のすべての可能なa値を試行することで決定論的にすることができます。制限値をnとすると、 $O(n)$ 回の試行が必要となり、実行時間は入力のサイズ $log n$ に対して指数関数的に増加します。実行時間を改善するには、テストの信頼性を維持しながら、制限値をできるだけ低くすることが課題となります。

テスト対象の数nが合成数である場合、 nと互いに素な強い嘘つきa は、群 ( Z / n Z )* の真部分群に含まれます。つまり、( Z / n Z )*を生成する集合からすべてのa をテストすると、そのうちの 1 つは上記の部分群の外にあり、したがってnが合成数であることの証拠となるはずです。一般化されたリーマン予想(ミラーは紛らわしいことに「拡張リーマン予想」と呼んでいます)が真であると仮定すると、この群は $O(($ $ln$ $n$ $)$ $2$ $)$ より小さい要素によって生成されることが知られており、これはすでにミラーによって指摘されています。^[¹^]ビッグ O 表記に含まれる定数は、エリック・バッハによって 2 に削減されました。^[¹²^]これにより、拡張リーマン予想を仮定すると決定論的な、ミラーテストとして知られる次の素数判定アルゴリズムが導き出されます。

入力：n > 2、素数判定対象の奇数 出力： nが合成数の場合は「composite」、それ以外の場合は「prime」

s > 0 かつd odd > 0 でn − 1 = 2 ^s dとなるようにする# n − 1から 2 のべき乗を因数分解するすべてのaが範囲 [2, min( n − 2, ⌊2(ln n ) ² ⌋)] にある場合: x ← a ^d mod n s回繰り返す: y ← x ² mod n y = 1 かつx ≠ 1 かつx ≠ n − 1の場合# 1 の法nの非自明な平方根を返す“ composite ” x ← y y ≠ 1の場合“ composite ” を返す“ prime ”を返す

テストの正しさを保証するために、一般化リーマン予想の完全な力は必要ありません。偶数指数の部分群を扱っているので、二次ディリクレ指標に対するGRHの妥当性を仮定すれば十分です。^{[ 7 ]}

アルゴリズムの実行時間は、ソフトO表記では $Õ((log n) 4)$ (FFTベースの乗算を使用)です。^{[ 13 ]}

ミラーテストは実際には使用されていません。ほとんどの場合、確率的ミラー・ラビンテストまたはベイリー・PSW素数判定法を適切に使用すれば、十分な信頼性が得られ、処理速度もはるかに速くなります。また、ミラーテストは、未証明の仮定に依存しない結果を与えるAPR-CLやECPPなどの一般的に使用される証明方法よりも、実際には処理速度が遅くなります。決定論的な多項式時間アルゴリズムを必要とする理論的な目的においては、未証明の仮定に依存しないAKS素数判定法に取って代わられました。

少数の塩基セットに対するテスト

テストする数nが小さい場合、 $a < 2(ln n) 2 を$ すべて試す必要はありません。なぜなら、はるかに小さな潜在的な証人のセットで十分であることがわかっているからです。たとえば、Pomerance、Selfridge、Wagstaff ^{[ 4 ]}および Jaeschke ^{[ 14 ]}は、

n < 2,047の場合、 a = 2をテストすれば十分です。
n < 1,373,653の場合、 a = 2 と 3 をテストすれば十分です。
n < 9,080,191の場合、 a = 31 と 73 をテストすれば十分です。
n < 25,326,001 の場合、 a = 2、3、および 5 をテストすれば十分です。
n < 3,215,031,751の場合、 a = 2、3、5、および 7 をテストすれば十分です。
n < 4,759,123,141の場合、 a = 2、7、および 61 をテストすれば十分です。
n < 1,122,004,669,633の場合、 a = 2、13、23、および 1662803をテストすれば十分です。
n < 2,152,302,898,747の場合、 a = 2、3、5、7、11 をテストすれば十分です。
n < 3,474,749,660,383の場合、 a = 2、3、5、7、11、および 13 をテストすれば十分です。
n < 341,550,071,728,321の場合、 a = 2、3、5、7、11、13、17 をテストすれば十分です。
a = 19のテストを追加しても、前述の境界値は改善されません。

FeitsmaとGalwayによる2010年の研究^{[ 15 ]}^{では、 264}までのすべての基数2擬素数を列挙しており、これを拡張し（OEIS : A014233 を参照）、最初の結果は後にJiangとDengによって異なる方法で示されました^{[ 16 ]。}

n < 3,825,123,056,546,413,051の場合、 a = 2, 3, 5, 7, 11, 13, 17, 19, 23 をテストすれば十分です。
a = 29 および 31のテストを追加しても、前述の境界値は改善されません。
n < 2 ⁶⁴ = 18,446,744,073,709,551,616の場合、 a = 2、3、5、7、11、13、17、19、23、29、31、および 37 をテストすれば十分です。

ソレンソンとウェブスター^{[ 17 ]}は上記を検証し、64ビットを超える結果について正確な結果を計算している。

n < 318,665,857,834,031,151,167,461の場合、 a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 をテストすれば十分です。
n < 3,317,044,064,679,887,385,961,981の場合、 a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 をテストすれば十分です。

Zhang (2007) は、特定の整数に焦点を当てることで、例えばn < 1,543,267,864,443,420,616,877,677,640,751,301の場合、18 個の連続する素数で十分であるというさらなる予測を提供している。しかし、このことが上限までのすべての整数に対して成り立つことを証明するのは、かなり難しい。^{[ 18 ]}

上記の基準よりも効率的な（必要な基数が少ない）他の基準は、基数が連続しているという要件を取り除くことによって存在します。^{[ 11 ]}^{[ 19 ]}^{[ 20 ]}例えば、2つの基数a = 336,781,006,125 と 9,639,812,373,923,155 はn < 1,050,535,501 に十分であり、7つの基数はn < 2 ⁶⁴に十分です。Steve Worley らによるさらなる最適化では、N 未満の整数を部分集合に分割し、その部分集合のすべての要素を正しく評価する証人を事前に選択します。このようなテストでは、2^64 未満のすべての N に対して 2 つの証人のみを使用できます。^{[ 21 ]}

考えられるすべての入力サイズに対して、潜在的な証人のリストは小さい ( bビット数の場合は最大でb値)。しかし、有限個の基数ではすべての合成数に対応できません。Alford、Granville、および Pomerance は、最小の合成性証人が少なくとも $(ln$ $n$ $)$ $1/(3ln ln ln n$ $)$ $で$ あるような合成数n が無限に存在することを示しました。^[²²^]また、nより小さいすべての合成数がwより小さい合成性証人を持つような最小の数wは、オーダー $Θ$ $(log$ $n$ $log log$ $n$ $) であるべきだとヒューリスティックに主張しています。$

因子を見つけるためのバリエーション

上記のアルゴリズムに最大公約数の計算を挿入することで、 nが合成数であると判断するだけでなく、nの因数を得ることも可能になる場合がある。これは例えば、nが基数aの素数である可能性が高いが、基数aの強い素数ではない場合に起こる。^[²³^]^：¹⁴⁰²

x がnを法とする 1 の非自明な平方根である場合、

$x 2 \equiv 1 (mod n)$ なので、 n は $x 2 - 1 = (x - 1)(x + 1)$ を割り切ることがわかります。
$x ≢ \pm1 (mod n)$ なので、 n は $x - 1$ も $x + 1$ も割り切れないことがわかります。

このことから、 $A = gcd(x - 1, n)$ と $B = gcd(x + 1, n)は$ nの非自明な（必ずしも素数ではない）因数であることが分かります（実際、nは奇数なので、これらの因数は互いに素であり、n = ABとなります）。したがって、因数分解が目的であれば、これらの最大公約数計算をアルゴリズムに組み込んでも、計算コストはほとんど増加しません。これにより、以下の擬似コードが得られます。追加または変更されたコードは強調表示されています。

入力 #1 : n > 2、素数かどうかをテストする奇数 入力 #2 : k、実行するテストのラウンド数 出力: nの非自明な因数mが見つかった場合は「（mの倍数） 」、それ以外の場合はnが合成数であると判明した場合は 「合成数」、 「おそらくプライム」そうでなければ

s > 0 かつd odd > 0でn − 1 = 2 ^s dとなるようにする# n − 1 から 2 のべき乗を因数分解するk回繰り返す : a ← random(2, n − 2) # nは常に 1 とn − 1 を基数とする素数であるx ← a ^d mod n s回繰り返す: y ← x 2 ^mod n if y = 1 and x ≠ 1 and x ≠ n − 1 then # 1を法とする非自明な平方根return (“の倍数”, gcd( x − 1, n )) x ← y if y ≠ 1 then return “合成数” return “おそらく素数”

これは確率的因数分解アルゴリズムではありません。なぜなら、基数aに対して擬似素数である数n（つまり、 $a$ $n$ $-1$ $\equiv 1 mod$ $n$ を満たす数n ）の因数しか見つけることができないからです。その他の数については、アルゴリズムは「合成数」という情報のみを返し、それ以上の情報は返しません。

例えば、n = 341、a = 2 を考えます $。n - 1 = 85 \times 4$ となります。すると、 $285 mod 341 = 32$ および $322 mod 341 = 1 となります。これは、$ nが擬似素数（基数 2）であるが、強い擬似素数（基数 2）ではないことを示しています。この段階で最大公約数を計算すると、341 の因数が見つかります。gcd $(32 - 1, 341) = 31 です$ 。実際、 $341 = 11 \times 31 です$ 。

同じ手法は、他の任意の値の平方根、特に§ 複数のテストの組み合わせで言及されている −1 の平方根にも適用できます。2 つの (成功した) 強力な素数判定テストで $x 2 \equiv -1 (mod n)$ および $y 2 \equiv -1 (mod n)$ が見つかり、かつ $x ≢ \pm y (mod n)$ である場合、 $gcd(x - y, n)$ および $gcd(x + y, n)は$ nの非自明な因数です。^{[ 11 ]}

例えば、 $n = 46,856,248,255,981$ は 2 と 7 の強い擬似素数ですが、テストを実行する過程で、

2^{(n-1)/2}\equiv 7^{(n-1)/2}\equiv -1{\pmod {n}},

2^{(n-1)/4}\equiv 34456063004337{\pmod {n}},{\text{ and}}

7^{(n-1)/4}\equiv 21307242304265{\pmod {n}}.

$これにより、gcd(34456063004337 - 21307242304265, n) = 4840261 という$ 因数が得られます。

可能性のある素数の生成

ミラー・ラビンテストは、テストに合格する整数が見つかるまでランダムに整数を抽出し続けることで、強力な素数候補を生成するために使用できます。このアルゴリズムはほぼ確実に終了します（各反復で素数を抽出する可能性があるため）。最上位ビットがセットされたbビットの強力な素数候補を生成する擬似コードは次のとおりです。

入力 #1 : b、結果のビット数 入力 #2 : k、実行するテストのラウンド数 出力: 強力な素数n

while True:入力nとkに対するミラー・ラビンテストの結果が「おそらく素数」であれば、範囲[ ^2b^-1 , 2b ^- 1] からランダムに 奇数nを選択する。

複雑

もちろん、最悪の場合の実行時間は無限大です。外側のループが終了しない可能性があるからです。ただし、その確率はゼロです。幾何分布によれば、期待される抽出回数は ${\tfrac {1}{\Pr(M\!R_{k})}}$ （以前の表記法を再利用）。

素数であればどれでもこのテストに合格するため、素数である確率は、テストに合格する確率の概算的な下限値を与える。範囲 [2 ^b⁻¹ , 1 ^b −1] から奇数を一様に抽出すると、次のようになる。

\Pr(M\!R_{k})>\Pr(1)={\frac {\pi \left(2^{b}\right)-\pi \left(2^{b-1}\right)}{2^{b-2}}}

ここで、π は素数計数関数です。πの漸近展開（素数定理の拡張）を用いると、 b が無限大に近づくときのこの確率を近似することができます。次のようになります。

\Pr(P)={\tfrac {2}{\ln 2}}b^{-1}+{\mathcal {O}}\left(b^{-3}\right)

{\tfrac {1}{\Pr(P)}}={\tfrac {\ln 2}{2}}b+{\mathcal {O}}\left(b^{-1}\right)

したがって、ジェネレーターが実行するミラー・ラビン・テストの回数は、 bに比例する回数以下であると予想できます。各ミラー・ラビン・テストの最悪ケースの複雑さを考慮すると（前述参照）、入力bとkを持つジェネレーターの期待実行時間は、 $O(k b 4)$ (またはFFT ベースの乗算を使用した $Õ(k b 3))$ に制限されます。

正確さ

この乱数発生器の誤差尺度は、合成数を出力する確率である。

条件付き確率（前のセクションで示したもの）と漸近挙動の関係を利用して、 $\Pr(P)$ （先ほど示したように）この誤差尺度には、おおまかな上限値を与えることができる。

\Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)\leq 4^{-k}\left({\tfrac {\ln 2}{2}}b-1+{\mathcal {O}}\left(b^{-1}\right)\right).

したがって、 bが十分に大きい場合、この誤差尺度は以下より小さくなります。 ${\tfrac {\ln 2}{2}}4^{-k}b$ しかし、もっと優れた境界値が存在する。

^{ミラー・ラビン検定自体の誤差範囲が 4 − k}よりはるかに小さいことが多いという事実を利用して(前述参照)、Damgård、Landrock、Pomerance は、さまざまなクラスのパラメータbとkに対して、ジェネレータのいくつかの誤差範囲を導出した。^{[ 9 ]}これらの誤差範囲により、実装者は望ましい精度に対して適切なk を選択できる。

これらの誤差限界の1つは 4 ^{− k}であり、これはすべてのb ≥ 2 に対して成り立ちます (著者らはb ≥ 51 の場合のみ示しましたが、Ronald Burthe Jr. は残りの値 2 ≤ b ≤ 50で証明を完了しました^{[ 24 ]} )。ここでも、この単純な限界はbの値が大きい場合に改善できます。たとえば、同じ著者らによって導出された別の限界は次のとおりです。

\left({\frac {1}{7}}b^{\frac {15}{4}}2^{-{\frac {b}{2}}}\right)4^{-k}

これは、b ≥ 21 およびk ≥ b /4の場合に成り立つ。b ≥ 32になるとすぐに、この上限は 4 ^{− k}より小さくなる。

注記

↑ ミラー・ラビン検定は、 1967 年という早い時期にMM アルチュホフによって発見されたと誤って言われることが多いが、アルチュホフの論文^{[ 3 ]} (特に彼の定理 E )を読むと、彼が実際に発見したのはソロベイ・ストラッセン検定であることがわかる。
↑ 例えば、1995年にアルノーは、307未満のすべての基数が強い嘘つきである397桁の合成数を提示しました。この数は、特定の基数2、3、5、7、11でミラー・ラビンテストを実装したMaple関数によって素数であると報告されました。 ^[⁵^]isprime()
↑ 例えば、2018年にAlbrechtらは、 OpenSSLやGNU GMPなどの多くの暗号ライブラリに対して、これらのライブラリが素数であると宣言した合成数を構築することに成功し、それによって、それらが敵対的なコンテキストを念頭に置いて実装されていないことを実証した。^{[ 10 ]}

参考文献

1 2ミラー、ゲイリー L. (1976)、「リーマンの予想と素数判定法」、Journal of Computer and System Sciences、13 (3): 300–317、doi : 10.1145/800116.803773、S2CID 10690396
1 2 Rabin, Michael O. (1980), "素数判定のための確率的アルゴリズム", Journal of Number Theory , 12 (1): 128–138 , doi : 10.1016/0022-314X(80)90084-0
↑ Artjuhov, MM (1966–1967)、「小フェルマーの定理に関連する数の素数性に関するいくつかの基準」、Acta Arithmetica、12：355–364、MR 0213289
1 2 Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (1980 年 7 月). "The pseudoprimes to 25 ⋅ 10 ⁹ " (PDF) . Mathematics of Computation . 35 (151): 1003– 1026. doi : 10.1090/S0025-5718-1980-0572872-7 .
↑ F. Arnault (1995 年 8 月) 「いくつかの基数に対する強い擬素数であるカーマイケル数の構成」 . Journal of Symbolic Computation . 20 (2): 151– 161. doi : 10.1006/jsco.1995.1042 .
↑コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。「31」。アルゴリズム入門(第 3版)。 MIT プレスとマグロウヒル。ページ968–971。ISBN 0-262-03384-4。
1 2 Schoof, René (2004)、「4つの素数判定アルゴリズム」(PDF)、アルゴリズム的数論：格子、数体、曲線、暗号、ケンブリッジ大学出版局、ISBN 978-0-521-80854-5
↑ Sloane, N. J. A. (編). "数列A329759 (k の強い擬似素数の証拠の数が phi(k)/4 に等しい奇数の合成数 k)" .オンライン整数列百科事典. OEIS Foundation.
1 2 Damgård, I. ; Landrock, P. & Pomerance, C. (1993), "Average case error estimates for the strong probable prime test" (PDF) , Mathematics of Computation , 61 (203): 177– 194, Bibcode : 1993MaCom..61..177D , doi : 10.2307/2152945 , JSTOR 2152945
↑ Martin R. Albrecht; Jake Massimo; Kenneth G. Paterson; Juraj Somorovsky (2018 年 10 月 15 日). Prime and Prejudice: Primality Testing Under Adversarial Conditions (PDF) . ACM SIGSAC Conference on Computer and Communications Security 2018. Toronto: Association for Computing Machinery . pp. 281– 298. doi : 10.1145/3243734.3243787 .
1 2 3 Caldwell, Chris. 「素数の発見と素数性の証明 — 2.3: 強力な確率的素数性と実用的なテスト」。The Prime Pages 。 2019年2月24日取得。
↑ Bach, Eric (1990), "素数判定および関連問題に対する明示的な境界", Mathematics of Computation , 55 (191): 355–380 , Bibcode : 1990MaCom..55..355B , doi : 10.2307/2008811 , JSTOR 2008811
↑ Zhang, Zhenxiang (2010-04-01). "ミラーの素数定理の一般化の有効性について" . Journal of Complexity . 26 (2): 200– 208. doi : 10.1016/j.jco.2010.01.002 . ISSN 0885-064X .
↑ Jaeschke, Gerhard (1993年10月)、「複数の基底に対する強い擬素数について」(PDF)、Mathematics of Computation、61 (204): 915–926、doi : 10.2307/2153262、JSTOR 2153262
↑ Feitsma, Jan (2013年4月25日). Galway, William (編). "擬素数と関連データの表" .サイモンフレーザー大学実験構成数学センター. 2024年11月22日取得.
↑ Jiang, Yupeng; Deng, Yingpu (2014). "最初の8つの素数基底に対する強い擬似素数" . Mathematics of Computation . 83 (290): 2915– 2924. doi : 10.1090/S0025-5718-2014-02830-5 . S2CID 33599405 .
↑ Sorenson, Jonathan; Webster, Jonathan (2015). "Strong Pseudoprimes to Twelve Prime Bases". Mathematics of Computation . 86 (304): 985–1003 . arXiv : 1509.00864 . Bibcode : 2015arXiv150900864S . doi : 10.1090/mcom/3134 . S2CID 6955806 .
↑ Zhang, Zhenxiang (2007 年 10 月 1 日). "10^{36}$ までの 2 種類の強い擬素数" (PDF) . Mathematics of Computation . 76 (260): 2095– 2108. doi : 10.1090/S0025-5718-07-01977-1 .
↑ Zhang, Zhenxiang & Tang, Min (2003年10月)、「複数の基底に対する強力な擬素数の発見 II」（PDF）、Mathematics of Computation、72（44）：2085–2097、Bibcode：2003MaCom..72.2085Z、doi：10.1090/S0025-5718-03-01545-X
↑ Sloane, N. J. A. (編). "数列A014233 (n 番目の素数以下の基数に対するミラー・ラビン素数判定で合成数であることが明らかにならない最小の奇数)" .オンライン整数列百科事典. OEIS Foundation.
↑ Izykowski, Wojciech. "ミラー-ラビン素数判定の決定論的変種" . 2019年2月24日取得。
↑ Alford, WR ; Granville, A. ; Pomerance, C. (1994), "信頼できる証人を見つけることの難しさについて", Algorithmic Number Theory (PDF) , Lecture Notes in Computer Science, vol. 877, Springer-Verlag, pp. 1– 16, doi : 10.1007/3-540-58691-1_36 , ISBN 978-3-540-58691-3
↑ Robert Baillie; Samuel S. Wagstaff, Jr. (1980 年 10 月). "Lucas Pseudoprimes" (PDF) . Mathematics of Computation . 35 (152): 1391– 1417. doi : 10.1090/S0025-5718-1980-0583518-6 . MR 0583518 .
↑ Burthe Jr., Ronald J. (1996), "Further investigations with the strong probable prime test" (PDF) , Mathematics of Computation , 65 (213): 373– 381, Bibcode : 1996MaCom..65..373B , doi : 10.1090/S0025-5718-96-00695-3

外部リンク

ワイスタイン、エリック W. 「ラビンミラーの強力な擬似素数検定」。マスワールド。
決定論的バージョンの対話型オンライン実装（アルゴリズムをステップバイステップで実行）
アプレット（ドイツ語）
C# でのミラー・ラビン素数判定
JavaScriptで任意精度演算を使用したミラー・ラビン素数判定

[4] ミラー・ラビン検定は、 1967 年という早い時期にMM アルチュホフによって発見されたと誤って言われることが多いが、アルチュホフの論文^{[ 3 ]} (特に彼の定理 E )を読むと、彼が実際に発見したのはソロベイ・ストラッセン検定であることがわかる。

[7] 例えば、1995年にアルノーは、307未満のすべての基数が強い嘘つきである397桁の合成数を提示しました。この数は、特定の基数2、3、5、7、11でミラー・ラビンテストを実装したMaple関数によって素数であると報告されました。 ^[⁵^]isprime()

[13] 例えば、2018年にAlbrechtらは、 OpenSSLやGNU GMPなどの多くの暗号ライブラリに対して、これらのライブラリが素数であると宣言した合成数を構築することに成功し、それによって、それらが敵対的なコンテキストを念頭に置いて実装されていないことを実証した。^{[ 10 ]}

[miller-1] 1 2ミラー、ゲイリー L. (1976)、「リーマンの予想と素数判定法」、Journal of Computer and System Sciences、13 (3): 300–317、doi : 10.1145/800116.803773、S2CID 10690396

[rabin-2] 1 2 Rabin, Michael O. (1980), "素数判定のための確率的アルゴリズム", Journal of Number Theory , 12 (1): 128–138 , doi : 10.1016/0022-314X(80)90084-0

[3] Artjuhov, MM (1966–1967)、「小フェルマーの定理に関連する数の素数性に関するいくつかの基準」、Acta Arithmetica、12：355–364、MR 0213289

[PSW-5] 1 2 Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (1980 年 7 月). "The pseudoprimes to 25 ⋅ 10 ⁹ " (PDF) . Mathematics of Computation . 35 (151): 1003– 1026. doi : 10.1090/S0025-5718-1980-0572872-7 .

[Arnault397Digit-6] F. Arnault (1995 年 8 月) 「いくつかの基数に対する強い擬素数であるカーマイケル数の構成」 . Journal of Symbolic Computation . 20 (2): 151– 161. doi : 10.1006/jsco.1995.1042 .

[8] コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。「31」。アルゴリズム入門(第 3版)。 MIT プレスとマグロウヒル。ページ968–971。ISBN 0-262-03384-4。

[schoof-9] 1 2 Schoof, René (2004)、「4つの素数判定アルゴリズム」(PDF)、アルゴリズム的数論：格子、数体、曲線、暗号、ケンブリッジ大学出版局、ISBN 978-0-521-80854-5

[10] Sloane, N. J. A. (編). "数列A329759 (k の強い擬似素数の証拠の数が phi(k)/4 に等しい奇数の合成数 k)" .オンライン整数列百科事典. OEIS Foundation.

[damgård-landrock-pomerance-11] 1 2 Damgård, I. ; Landrock, P. & Pomerance, C. (1993), "Average case error estimates for the strong probable prime test" (PDF) , Mathematics of Computation , 61 (203): 177– 194, Bibcode : 1993MaCom..61..177D , doi : 10.2307/2152945 , JSTOR 2152945

[12] Martin R. Albrecht; Jake Massimo; Kenneth G. Paterson; Juraj Somorovsky (2018 年 10 月 15 日). Prime and Prejudice: Primality Testing Under Adversarial Conditions (PDF) . ACM SIGSAC Conference on Computer and Communications Security 2018. Toronto: Association for Computing Machinery . pp. 281– 298. doi : 10.1145/3243734.3243787 .

[prime-pages-14] 1 2 3 Caldwell, Chris. 「素数の発見と素数性の証明 — 2.3: 強力な確率的素数性と実用的なテスト」。The Prime Pages 。 2019年2月24日取得。

[15] Bach, Eric (1990), "素数判定および関連問題に対する明示的な境界", Mathematics of Computation , 55 (191): 355–380 , Bibcode : 1990MaCom..55..355B , doi : 10.2307/2008811 , JSTOR 2008811

[16] Zhang, Zhenxiang (2010-04-01). "ミラーの素数定理の一般化の有効性について" . Journal of Complexity . 26 (2): 200– 208. doi : 10.1016/j.jco.2010.01.002 . ISSN 0885-064X .

[17] Jaeschke, Gerhard (1993年10月)、「複数の基底に対する強い擬素数について」(PDF)、Mathematics of Computation、61 (204): 915–926、doi : 10.2307/2153262、JSTOR 2153262

[18] Feitsma, Jan (2013年4月25日). Galway, William (編). "擬素数と関連データの表" .サイモンフレーザー大学実験構成数学センター. 2024年11月22日取得.

[19] Jiang, Yupeng; Deng, Yingpu (2014). "最初の8つの素数基底に対する強い擬似素数" . Mathematics of Computation . 83 (290): 2915– 2924. doi : 10.1090/S0025-5718-2014-02830-5 . S2CID 33599405 .

[20] Sorenson, Jonathan; Webster, Jonathan (2015). "Strong Pseudoprimes to Twelve Prime Bases". Mathematics of Computation . 86 (304): 985–1003 . arXiv : 1509.00864 . Bibcode : 2015arXiv150900864S . doi : 10.1090/mcom/3134 . S2CID 6955806 .

[21] Zhang, Zhenxiang (2007 年 10 月 1 日). "10^{36}$ までの 2 種類の強い擬素数" (PDF) . Mathematics of Computation . 76 (260): 2095– 2108. doi : 10.1090/S0025-5718-07-01977-1 .

[22] Zhang, Zhenxiang & Tang, Min (2003年10月)、「複数の基底に対する強力な擬素数の発見 II」（PDF）、Mathematics of Computation、72（44）：2085–2097、Bibcode：2003MaCom..72.2085Z、doi：10.1090/S0025-5718-03-01545-X

[23] Sloane, N. J. A. (編). "数列A014233 (n 番目の素数以下の基数に対するミラー・ラビン素数判定で合成数であることが明らかにならない最小の奇数)" .オンライン整数列百科事典. OEIS Foundation.

[24] Izykowski, Wojciech. "ミラー-ラビン素数判定の決定論的変種" . 2019年2月24日取得。

[25] Alford, WR ; Granville, A. ; Pomerance, C. (1994), "信頼できる証人を見つけることの難しさについて", Algorithmic Number Theory (PDF) , Lecture Notes in Computer Science, vol. 877, Springer-Verlag, pp. 1– 16, doi : 10.1007/3-540-58691-1_36 , ISBN 978-3-540-58691-3

[baillie-26] Robert Baillie; Samuel S. Wagstaff, Jr. (1980 年 10 月). "Lucas Pseudoprimes" (PDF) . Mathematics of Computation . 35 (152): 1391– 1417. doi : 10.1090/S0025-5718-1980-0583518-6 . MR 0583518 .

[burthe-27] Burthe Jr., Ronald J. (1996), "Further investigations with the strong probable prime test" (PDF) , Mathematics of Computation , 65 (213): 373– 381, Bibcode : 1996MaCom..65..373B , doi : 10.1090/S0025-5718-96-00695-3

[ 1 ]

[ 2 ]

[ a ]

[ 4 ]

[ b ]

[ 6 ]

7

8

[

[

[ 11 ]

[

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]。

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[

[

[ 24 ]

[ 3 ]

[

[ 10 ]