博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love 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)を計算する 全部1になったら、素数でない テストにパスしたら、他の数のべき乗かどうか調べる べき乗になっているかどうかは手軽にわかる 全てパスすれば素数

フェルマの小定理 定理１： 自然数ｂ＜ｐに対して、ｂｐ－１のｐでの剰余は１になる（１と合同という） 定理１：　自然数ｂ＜ｐに対して、ｂｐ－１のｐでの剰余は１になる（１と合同という） 証明：　（１＋ｘ）ｐを展開してみよう 定理２　　ｂ（p-1）/2は１または－１と合同である。また、－１になる数はｐ未満の自然数全体の半数である 証明：　１．方程式の解の数を考えよう 　　　ｘ (p-1)/2 = 1 の解は(p-1)/２個しかない

フェルマの小定理が成立するのは 素数だけか？ オイラーの定理 　任意の自然数ｎと、ｎと互いに素な自然数ｂに対して 　　　　　　はオイラー関数 ｎ以下の、ｎと互いに素な数の個数 　オイラー関数の値がｎ－１になるのは素数だけ。 　n = pqr なら(p－１)(q－１)(r－１)となる

フェルマの小定理が成立するのは 素数だけか？ 　奇数素数の積　ｎ＝ｐｑｒと、ｎと互いに素な自然数ｂに対して 　　とすると、 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 のｎでの剰余を計算して 　 １または-１でなければ、ｎは必ず合成数 　　毎回１なら、高い確率で素数でない 　　１とー１が混ざれば、高い確率で素数

素数判定アルゴリズムの正答率 素数であり、テストをパスしない確率は？ 合成数であり、テストをパスしてしまう確率は？ 　素数であり、テストをパスしない確率は？ 　１００個のaで全てa (p-1)/2 = 1 確率　1/２100 合成数であり、テストをパスしてしまう確率は？ 　a で-１になるものがあり、１００個のaで全て１かー１になる 確率1/２100