Presentation is loading. Please wait.

Presentation is loading. Please wait.

博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love

Similar presentations


Presentation on theme: "博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love"— Presentation transcript:

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


Download ppt "博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love"

Similar presentations


Ads by Google