ルーカス素数判定

Algorithm for checking if a number is prime

計算数論において、ルーカステストは自然数nの素数性テストであり、 n −1の素因数が既に分かっていることを必要とする。 ^{[1] [2]これは}nが素数であることを簡潔に証明するプラット証明書の基礎である。

概念

nを正の整数とする。1 <  a  <  nを満たす整数aが存在するとすると、

${\displaystyle a^{n-1}\ \equiv \ 1{\pmod {n}}\,}$

そしてn  − 1のあらゆる素因数qに対して

${\displaystyle a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}\,}$

nは素数です。そのような数a が存在しない場合は、nは1、2、または合成数のいずれかになります。

この主張が正しい理由は、次のとおりです。最初の同値性がaに当てはまる場合、 aとnは互いに素であると推論できます。a が2 番目のステップも通過する場合、群( Z / n Z )*内のaの位数はn −1に等しくなります。これは、群の位数がn −1 であることを意味します (群のすべての要素の位数は群の位数を割り切るため)。つまり、nは素数です。逆に、nが素数の場合、 nを法とする原始根、つまり群 ( Z / n Z )* の生成元が存在します。このような生成元の位数は |( Z / n Z )*| =  n −1 であり、両方の同値性はこのような原始根に対して当てはまります。

最初の同値が成立しないa  <  nが存在する場合、 aはnの合成性のフェルマーの証拠と呼ばれることに注意してください。

例

例えば、n = 71とします。するとn  − 1 = 70となり、70の素因数は2、5、7です。a =17  <  nとなるようにランダムに選びます。ここで以下を計算します。

${\displaystyle 17^{70}\ \equiv \ 1{\pmod {71}}.}$

すべての整数aに対して、

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}\ {\text{ if and only if }}{\text{ ord}}(a)|(n-1).}$

したがって、 17（71を法とする）の乗法は必ずしも70とは限りません。なぜなら、70の因数も上記のように成り立つ可能性があるからです。そこで、70をその素因数で割った値を調べてみましょう。

${\displaystyle 17^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 17^{14}\ \equiv \ 25\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 17^{10}\ \equiv \ 1\ \equiv \ 1{\pmod {71}}.}$

^{残念ながら、17 10} ≡ 1 (mod 71)となります。つまり、71 が素数かどうかはまだわかりません。

もう一度ランダムaを試してみます。今回はa  = 11 を選択します。ここで以下を計算します。

${\displaystyle 11^{70}\ \equiv \ 1{\pmod {71}}.}$

繰り返しますが、これは11の乗法順序（71を法とする）が70であることを示すものではありません。70の因数も成り立つ可能性があるからです。そこで、70をその素因数で割った値を確認してみましょう。

${\displaystyle 11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{10}\ \equiv \ 32\ \not \equiv \ 1{\pmod {71}}.}$

したがって、11 の乗法順序 (mod 71) は 70 であり、したがって 71 は素数です。

(これらのモジュラー指数演算を実行するには、バイナリ指数演算や加算連鎖指数演算などの高速指数演算アルゴリズムを使用できます)。

アルゴリズム

このアルゴリズムは、次のように擬似コードで記述できます。

アルゴリズムlucas_primality_test の入力は次のとおりです : n > 2、素数かどうかをテストする奇数。 k、テストの精度を決定するパラメーター。 出力: nが素数の場合はprime、そうでない場合は合成数または合成数の可能性があります。n −1 の素因数を決定します。 LOOP1: k回繰り返す :[2, n − 1] の範囲でランダムにaを 選ぶ。if then return compound else # LOOP2: n −1のすべての素因数qについて: if then if if if if if if we check this equality for all prime factors of n −1 then return prime else else continue LOOP2 else # continue LOOP1  ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$       ${\displaystyle \color {Gray}{a^{n-1}\equiv 1{\pmod {n}}}}$  ${\displaystyle a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}}$         ${\displaystyle \color {Gray}{a^{\frac {n-1}{q}}\equiv 1{\pmod {n}}}}$   複合を返す可能性があります。

参照

• このテストの名前の由来となったエドゥアール・リュカス
• フェルマーの小定理
• ポックリントン素数判定、 n  − 1の部分因数分解のみを必要とするこの判定の改良版
• 素数証明書

注記

1. リチャード・クランドール、カール・ポメランス（2005年）『素数：計算論的視点』（第2版）シュプリンガー、173ページ。ISBN 0-387-25282-7。
2. Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 Lectures on Fermat Numbers: From Number Theory to Geometry . CMS Books in Mathematics. Vol. 9. Canadian Mathematical Society/Springer. p. 41. ISBN 0-387-95332-9。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Lucas_primality_test&oldid=1280473548"