ルーカス素数判定

計算数論において、ルーカステストは自然数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{ }}{\text{ ord}}(a)|(n-1). のときのみ。}$

したがって、 17 (mod 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 (mod 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
    の素因数を決定します。

    ループ1: k回繰り返す :[2, n − 1]
            の範囲でランダムにaを
        選ぶ。if then return complex else # 
                LOOP2: n −1のすべての素因数qについて:
                     if then if if if if if if if if if if if n −1のすべての素因数についてこの等式を確認したら、primeを返す。else LOOP2
                    を続行する。else # 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の部分因数分解のみを必要とするこの判定法の改良版である。
• 素数証明書