1. 高校数学の美しい物語
  2. 素因数分解の難しさと素数判定

素因数分解の難しさと素数判定

更新日時 2021/03/07

素数について,理系なら知っておくべき知識について整理しました。

目次
  • 素因数分解の難しさ

  • 素数判定問題

  • フェルマーテスト

素因数分解の難しさ

  • 2以上の整数は,素数の積で表すことができます(素因数分解)。そして素因数分解の方法は一通りです(素因数分解の一意性・算術の基本定理)。

  • 素因数分解は非常に難しい
    例えば,13297×96479=128288126313297×96479=1282881263 という等式を考えてみます。左辺だけ与えられたとき右辺を計算するのは簡単ですが,右辺が与えられたときに左辺のように分解するのは非常に難しそうです。
    これくらいの数字なら現代のコンピュータを使えば一瞬ですが,例えば 100100 桁の数を素因数分解するのは,コンピュータを使っても天文学的な時間がかかると考えられています(50桁の数どうしのかけ算なら簡単)。

  • 現代の暗号(の一部)は素因数分解の難しさに基づいている
    大きい数(300桁程度)を公開しておき,その素因数分解を知っている人だけが暗号文を復号できるような仕組みがあります。→RSA暗号の仕組みと安全性

素数判定問題

素因数分解が難しい(多項式時間で解けない)ことは多くの人に信じられています(証明されてはいない)が,与えられた数が素数かどうか判定するだけなら多項式時間で解けます。

多項式時間についてはP≠NP予想の主張の解説を参照してください。

以下では,より単純で理解しやすいフェルマーテストという確率的な素数判定法について解説します。

フェルマーテスト

フェルマーの小定理の対偶から以下の定理が成立します:

定理

ある自然数 aa が存在して

an≢a(modn)a^{n}\not\equiv a \pmod{n}

が成り立てば nn は合成数。

この定理を用いて,与えられた数 nn が素数かどうかを高確率で判定できます!

例1

44 は合成数

a=2a=2 としてみると,24=16≢2(mod4)2^4=16\not\equiv 2\pmod{4}

例示のため小さい数で計算しましたが,a,na,n が大きい数でも合同式の性質を用いれば anmodna^n\bmod{n} を計算することは比較的容易なのでこの判定は高速です。

例2

77 は素数っぽい

a=2a=2 としてみると 27=1282(mod7)2^7=128\equiv 2\pmod{7}

a=3a=3 としてみると 37=3933233(mod7)3^7=3\cdot 9^3\equiv3\cdot2^3\equiv 3\pmod{7}

この結果から 77 が素数っぽいことが予想できます。

実際,ほとんどの合成数 nn と自然数 aa に対して an≢a(modn)a^n\not\equiv a\pmod{n} が成立することが知られているので,いくつかの aa に対して ana(modn)a^n\equiv a\pmod{n} が成立すれば nn は非常に高い確率で素数です。

しかし,残念ながら100%素数であるとは言えないのです。合成数なのにフェルマーテストでは素数のように振る舞ってしまういやなやつをフェルマー擬素数と言います。

フェルマーテストが気になった方は「カーマイケル数」などのキーワードで調べてみてください。

Tag:素数にまつわる覚えておくべき性質まとめ

人気記事
  1. 高校数学の美しい物語
  2. 素因数分解の難しさと素数判定