もう一人のY君

iPhoneアプリのレビューやアップデートレビューなどを書いています. たまに数学の記事も書きます.

もう一人のY君　MENU 　MENU

(数学)変則素数判定

数学

161023_06

　ちょっと捻った定理を使うと, 通常?の素数判定より手間が格段に少なくなります.

 

 

普通の？素数判定

　まずは良くある素数判定からです.

 

[定理1]

　正整数 { \displaystyle m\neq 1 } が素数であることの必要十分条件は, { \displaystyle m } が { \displaystyle \sqrt{m} } 以下の素因数を持たないことである.

[定理1の証明]

　素数は定義より真の約数を持たない数です, つまり

{ \displaystyle 1\lt a \lt m }

なる任意の自然数 { \displaystyle a } は { \displaystyle m } の約数ではありません.

 

　従って仮に { \displaystyle m } が素数でない, つまり合成数だとすると上記のような整数 { \displaystyle a } と対応する整数 { \displaystyle b } について

 

{ \displaystyle m=ab }

 

です, ここで { \displaystyle a\leq b } としても一般性を失いません.

　これより,

 

{ \displaystyle m \\ =ab \\ \geq a\times a \, =a^2  }

 

から

 

{ \displaystyle a\leq \sqrt{m} }

 

となります.

　つまり仮に { \displaystyle m } が合成数ならば, { \displaystyle m } の真の約数の少なくとも一つは必ず

 

{ \displaystyle 1\lt a \leq\sqrt{m} }

 

を満たす整数 { \displaystyle a } ということになります.

　然るにこのような { \displaystyle a } が存在しなければ, { \displaystyle m } は真の約数を持たない, つまり素数ということになります.

 

　逆の場合は上の議論を逆に辿れば導かれます. { \displaystyle \square }

 

 

定理1を用いた素数判定の手間数

　これを用いた素数判定は, つまり以下の方法となりますね.

 

[素数判定1]

　正整数 { \displaystyle m\neq 1 } が素数であるかを確かめるには,

{ \displaystyle 1\lt a\leq\sqrt{m} }

を満たす任意の素数 { \displaystyle a } が { \displaystyle m } を割りきらないことである.

 

　{ \displaystyle m } が小さいうちは大したことはありませんが, 大きくなるにつれ { \displaystyle \sqrt{m} } も比較的大きくなるため, これを満たす素数の数もかなり増えていきます.

 

　例えば { \displaystyle m=29 } の場合, { \displaystyle \sqrt{29}=5.38516\dots } ですから { \displaystyle 5 } 以下の素数について確認すれば十分です.

　この場合 対応する素数は { \displaystyle 2, 3, 5 } の3つですね.

 

　これが大きくなるとどうでしょう, 例えば { \displaystyle m=9957 } を考えると { \displaystyle \sqrt{9957}=99.78476\dots } ですから { \displaystyle 2 } から { \displaystyle 97 } までの { \displaystyle 25 } 個の素数について確認することになります, 面倒ですね.

 

 

　というわけで次が本題になります.

 

 

スポンサーリンク

 

変則素数判定

[定理2]

　正整数 { \displaystyle m \neq 1 } が { \displaystyle \sqrt[3]{m} } 以下の素因数を持たないならば, 次のいずれかが成り立つ.

  • { \displaystyle m } は素数
  • { \displaystyle m } は2つの素数の積

　「2つの素数」については, 同じ素数である場合を含みます.

 

[定理2の証明]

　対偶を用いて証明します.

　待遇を取ると

 

{ \displaystyle m } が3つ以上の素数の積ならば, { \displaystyle m } の素因数の中に { \displaystyle \sqrt[3]{m} } より大きいものが存在する

 

ですね.

 

　というわけで { \displaystyle m } が3つ以上の素数の積とします, つまり

 

{ \displaystyle m=pqr\dots } 

 

 です.

　もし { \displaystyle m } のすべての素因数が { \displaystyle \sqrt[3]{m} } より大きいと仮定すると,

 

{ \displaystyle m=pqr\dots \\ \geq pqr \\ \gt \bigl( \sqrt[3]{m} \bigr)^3 \\ =m }

 

となります.

　しかしこれは { \displaystyle m\gt m } で矛盾しています.

 

　従って「{ \displaystyle m } のすべての素因数が { \displaystyle \sqrt[3]{m} } より大きい」が間違っていることになります.

　よって { \displaystyle m } の素因数の少なくとも1つは { \displaystyle \sqrt[3]{m} } 以下であることが分かります. { \displaystyle \square }

 

　この定理2より, { \displaystyle \sqrt[3]{m} } 以下の素数まで調べれば, ある程度の判定が済むということになります.

　当然ですが定理の通り2つの素数の積の可能性があるため完璧ではありません.

　とはいえ { \displaystyle \sqrt{m} } 以下の素数と { \displaystyle \sqrt[3]{m} } 以下の素数では段違いですね.

 

 

検証

　実際に適当な数を使って確かめてみましょう.

 

  • { \displaystyle m=7171=71\times 101 }

　明らかに { \displaystyle 71 } で割れるのがバレバレですが分かってない体で.

　{ \displaystyle \sqrt{7171}=84.68175\dots }, { \displaystyle \sqrt[3]{7171}=19.28382\dots } ですから, 前者では83以下の素数, 後者では { \displaystyle 19 } 以下の素数で確かめることになります.

　前者は23個, 後者は8個で済みます.

 

　とはいえ後者で8個の判定で分かることは「素数であるか或いは2つの素数の積」ですから, 「2つの素数の積」であるかどうかを確かめるために別の検証をしなければなりません.

 

　考えられる手法としては, 定理2より

 

「{ \displaystyle \sqrt[3]{m} } 以下の素因数で割り切れるか」

 

ですね.

 

　これをいくつまでやるべきか…というのも難しい話ですが.

 

 

定理2のデメリット

　というわけでここで気になるのは省略した { \displaystyle \sqrt[3]{m}\lt a\leq \sqrt{m} } の部分です.

　その範囲に素因数が存在するかが問題になってくるわけですが, これがなかなか難しいのです.

 

　2つの数を例に挙げてみましょう.

 

　まず先程の { \displaystyle m=7171 } については(結果論ですが) { \displaystyle \sqrt{7171}=84.68175\dots } ですから{ \displaystyle 83 } から降順に確かめればある程度早めに素因数 { \displaystyle 71 } を確認することができます.

 

　しかしこれが { \displaystyle m=4747=47\times 101 } となると話は違います.

　{ \displaystyle \sqrt{4747}=68.89848\dots }, { \displaystyle \sqrt[3]{4747}=16.80634\dots } なのでまず { \displaystyle 13 } 以下の素因数があるかを確認するわけですが, その後2つの素数による積かどうかを確かめるには, { \displaystyle \sqrt{4747} } より大きい素数の中で一番小さい { \displaystyle 17 } からにしろ { \displaystyle \sqrt[3]{4747} } 以下で一番大きい { \displaystyle 67 } から降順に調べるにしてもやや手数が多いことが分かります.

 

　或いは { \displaystyle m=2929=29\times 101 } となれば { \displaystyle \sqrt{2929}=54.12024\dots }, { \displaystyle \sqrt[3]{2929}=14.30781\dots } となって, これは { \displaystyle \sqrt{m} } の方から昇順に調べた方が早いのは明らかです.

 

 

〆

　そもそもこの程度で効率よく素数判定ができれば, RSA暗号なんて存在しないんですね, 現実は中々都合よくいかないものです.

 

　せめて { \displaystyle \sqrt[3]{m} } から昇順に調べるのか, { \displaystyle \sqrt{m} } から降順に調べるのが早いのか…が分かれば多少でも効率を挙げられるんですけどね.

 

 

thetheorier