Download presentation
Presentation is loading. Please wait.
1
博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love
Mathematics that the professor loved 徳山 豪 東北大学 Prime numbers that professors love 博士たちの愛する素数
2
素数の魅力 素数:1と自分以外の約数を持たない自然数 無数にあるか?どのくらいの頻度であるか? 素数の判定法はあるか? 因数分解の不思議
2,3,5,7,11,13,17,19,23,29,31,37. 無数にあるか?どのくらいの頻度であるか? 素数分布定理 素数の判定法はあるか? 因数分解の不思議 素数を法とする数の世界: 有限体の世界
3
古くて役に立つ数論 百五減算: 塵劫記(吉田光由、1627)
百五減算: 塵劫記(吉田光由、1627) 碁石がいくつかあります。7個づつに分けると2個余ります。5個づつに分けると1個余ります。3個づつに分けると1個余ります。 碁石はいくつありますか? ただし、碁石は最大で180個しかありません。
4
中国人剰余定理 (Chinese reminder theorem)
互いに素な数n1,n2,..nkの積nを考える。 ni未満の非負整数miを任意に与える。 ⇒ m≡mi (mod ni) i=1,2,..,k を満たすn未満の非負整数mは必ず1つだけ存在する 孫子(BC5世紀)に名前の由来があるらしい 百五計算と同等、ユークリッド(BC3世紀)の互助法を利用して計算できる。
5
数のべき乗の不思議 徳山が子供のころ見つけたこと 1から9までの数のべき乗の1の桁には面白いルールがある。 なぜだろう?
1から9までの数のべき乗の1の桁には面白いルールがある。 なぜだろう? 1 2 3 4 5 6 7 8 9 1 4 9 6 5 6 9 4 1 1 8 7 4 5 6 3 2 9 1 6 1 6 5 6 1 6 1
6
素数判定と乱数 与えられた数が素数であるかどうかの判定 フェルマテスト フェルマテストにパスしないものは素数でない
与えられた数が素数であるかどうかの判定 フェルマテスト p が素数なら、すべての数a < p について ap-1 –1 はpで割り切れる pが普通の数だと、確率1/2以下でしか成り立たない フェルマテストにパスしないものは素数でない パスしたら、素数か、「カーマイケル数」 素数のみを選び出すにはどうするか? ラビンテスト 少し簡単なバージョン(ここではこちらを紹介)
7
素数判定アルゴリズム ランダムにa<p を100個選ぶ。 a(p-1)/2 (mod p)を計算する
全部1になったら、素数でない テストにパスしたら、他の数のべき乗かどうか調べる べき乗になっているかどうかは手軽にわかる 全てパスすれば素数
8
フェルマの小定理 定理1: 自然数b<pに対して、bp-1のpでの剰余は1になる(1と合同という)
定理1: 自然数b<pに対して、bp-1のpでの剰余は1になる(1と合同という) 証明: (1+x)pを展開してみよう 定理2 b(p-1)/2は1または-1と合同である。また、-1になる数はp未満の自然数全体の半数である 証明: 1.方程式の解の数を考えよう x (p-1)/2 = 1 の解は(p-1)/2個しかない
9
フェルマの小定理が成立するのは 素数だけか?
オイラーの定理 任意の自然数nと、nと互いに素な自然数bに対して はオイラー関数 n以下の、nと互いに素な数の個数 オイラー関数の値がn-1になるのは素数だけ。 n = pqr なら(p-1)(q-1)(r-1)となる
10
フェルマの小定理が成立するのは 素数だけか?
奇数素数の積 n=pqrと、nと互いに素な自然数bに対して とすると、 n = 3 x 11 x 17 =561 だと?(カーマイケル数) 素数判定のアイデア: カーマイケル数だと、(n-1)/2乗で1になってしまう
11
素数判定アルゴリズムの正当性 中国人剰余定理を利用して証明しよう 定理 (素数判定定理) 奇数の合成数nが、素数のべき乗でないとき、
定理 (素数判定定理) 奇数の合成数nが、素数のべき乗でないとき、 a (n-1)/2 ≡ -1になるaが存在すれば、 a (n-1)/2 が1,-1以外になる数が存在する。 また、そのような数の個数は(n-1)/2以上 中国人剰余定理を利用して証明しよう
12
証明 a (n-1)/2 ≡ -1 mod n n = pe m = km 中国人剰余定理から、次のようなbが存在
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でもない
13
素数判定アルゴリズムの正当性 フェルマの小定理と素数判定定理から、 a (n-1)/2 のnでの剰余を計算して
1または-1でなければ、nは必ず合成数 毎回1なら、高い確率で素数でない 1とー1が混ざれば、高い確率で素数
14
素数判定アルゴリズムの正答率 素数であり、テストをパスしない確率は? 合成数であり、テストをパスしてしまう確率は?
素数であり、テストをパスしない確率は? 100個のaで全てa (p-1)/2 = 1 確率 1/2100 合成数であり、テストをパスしてしまう確率は? a で-1になるものがあり、100個のaで全て1かー1になる 確率1/2100
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.