Document

Mathematics that the professor loved
徳山豪
東北大学
Prime numbers that professors love
博士たちの愛する素数
素数の魅力
• 素数：１と自分以外の約数を持たない自然数
– 2，3，5，7，11，13，17，19，23，29，31，37．
• 無数にあるか？どのくらいの頻度であるか？
– 素数分布定理
• 素数の判定法はあるか？
• 因数分解の不思議
• 素数を法とする数の世界：有限体の世界
古くて役に立つ数論
• 百五減算：塵劫記（吉田光由、１６２７）
碁石がいくつかあります。７個づつに分けると２個
余ります。５個づつに分けると１個余ります。３個
づつに分けると１個余ります。碁石はいくつあ
りますか？ただし、碁石は最大で１８０個しか
ありません。
中国人剰余定理
（Chinese reminder theorem)
互いに素な数n1,n2,..nkの積ｎを考える。
ni未満の非負整数miを任意に与える。
⇒
m≡mi (mod ni) i=1,2,..,k を満たすｎ未満の
非負整数ｍは必ず１つだけ存在する
孫子（BC５世紀）に名前の由来があるらしい
百五計算と同等、ユークリッド（BC３世紀）の
互助法を利用して計算できる。
数のべき乗の不思議
• 徳山が子供のころ見つけたこと
• １から９までの数のべき乗の１の桁には面白
いルールがある。なぜだろう？
• １２３４５６７８９
• １４９６５６９４１
• １８７４５６３２９
• １６１６５６１６１
• １２３４５６７８９
素数判定と乱数
•
与えられた数が素数であるかどうかの判定
– フェルマテスト
• p が素数なら、すべての数a < p について
• ap-1 –1 はpで割り切れる
• ｐが普通の数だと、確率1/2以下でしか成り立たない
– フェルマテストにパスしないものは素数でない
– パスしたら、素数か、「カーマイケル数」
– 素数のみを選び出すにはどうするか？
• ラビンテスト
• 少し簡単なバージョン（ここではこちらを紹介）
素数判定アルゴリズム
•
•
•
•
•
ランダムにa<p を１００個選ぶ。
a（p-1）/2 (mod p)を計算する
結果が１またはp-1でなければ素数でない
全部1になったら、素数でない
テストにパスしたら、他の数のべき乗かどうか
調べる
– べき乗になっているかどうかは手軽にわかる
• 全てパスすれば素数
フェルマの小定理
• 定理１：自然数ｂ＜ｐに対して、ｂｐ－１のｐでの
剰余は１になる（１と合同という）
– 証明：（１＋ｘ）ｐを展開してみよう
• 定理２ｂ（p-1）/2は１または－１と合同である。
また、－１になる数はｐ未満の自然数全体の半
数である
– 証明：１．方程式の解の数を考えよう
ｘ (p-1)/2 = 1 の解は(p-1)/２個しかない
フェルマの小定理が成立するのは
素数だけか？
• オイラーの定理
任意の自然数ｎと、ｎと互いに素な自然数ｂに対して
 ( n)
b  1 (modn)
 (n) はオイラー関数
ｎ以下の、ｎと互いに素な数の個数
オイラー関数の値がｎ－１になるのは素数だけ。
n = pqr なら(p－１)(q－１)(r－１)となる
フェルマの小定理が成立するのは
素数だけか？
奇数素数の積ｎ＝ｐｑｒと、ｎと互いに素な自然数ｂ
に対して  (n)  LCM ( p  1, q  1, r  1) とすると、
b
 ( n)
 1 (modn)
n = 3 x 11 x 17 ＝５６１だと？(カーマイケル数）
素数判定のアイデア：カーマイケル数だと、(n-1)/２
乗で１になってしまう
素数判定アルゴリズムの正当性
• 定理 (素数判定定理）
奇数の合成数ｎが、素数のべき乗でないとき、
a (n-1)/2 ≡ -１になるaが存在すれば、
a (n-1)/2 が1,-1以外になる数が存在する。
また、そのような数の個数は(n-1)/2以上
中国人剰余定理を利用して証明しよう
証明
• a (n-1)/2 ≡ -１ mod n
• n = pe m = km
• 中国人剰余定理から、次のようなｂが存在
•
•
b ≡ a mod k
b ≡ 1 mod m
• b (n-1)/2 ≡ -1 mod k
• b (n-1)/2 ≡ 1 mod m
• b (n-1)/2 mod n は1でも-1でもない
素数判定アルゴリズムの正当性
•
フェルマの小定理と素数判定定理から、
a (n-1)/2 のｎでの剰余を計算して
1.
１または-１でなければ、ｎは必ず合成数
2.
毎回１なら、高い確率で素数でない
3.
１とー１が混ざれば、高い確率で素数
素数判定アルゴリズムの正答率
•
素数であり、テストをパスしない確率は？
– １００個のaで全てa (p-1)/2 = 1
– 確率 1/２100
• 合成数であり、テストをパスしてしまう確率は
？
– a で-１になるものがあり、１００個のaで全て１か
ー１になる
– 確率1/２100

Download Report