再開した。
今回の内容
1.2.6 例:素数判定
読んですぐにわからない内容が多かったので、紙とホワイトボードを駆使して理解を試みた。
まず素数判定として 1 から √n までの数で割っていく有名な手法についてだが、この時、1 ~ √n まででよいということをすぐに理解できなかったので、これについて考えた。
注釈44に
もし d が n の約数であれば、n/d も約数になります。しかし、d と n/d の両方とも √n より大きいということはありえません。
とある。言葉としてはこの通りだがすぐにはピンと来なかったので証明を試みた。(参加者が考えたもの)
n = a x b (a,b∈Z, a<=b, a,b>0)
a <= b
a x a <= a x b
a x a <= n
a <= √n
よって n の約数である a と b (a,b∈Z, a<=b, a,b>0) がある時、小さい方の約数 a は必ず √n 以下になる。
フェルマーテスト
n が素数で、a が n より小さい任意の正の整数であるとき、a の n 乗は法 n に関して a と合同である。
簡単に言い変えると
n が素数であるならば、任意の整数 a (a < n) を選んだとき、 an と a を n で割ったときの余りは等しくなる。
逆に言えば
任意の整数 a (a < n) を選んだとき、 an と a を n で割ったときの余りが等しいならば、n は素数である。
ただし、次の「確率的手法」で言われている通り、このフェルマーテストが失敗する (a^n と a が法 n に関して合同ではない) ならば n は素数ではないと言い切れるが、逆の場合は n が素数である確率が限りなく高いという意味になる (このテストを満しながらも素数ではない値がある<注釈47>)
以下でフェルマーテストの例を簡単に見てみる
n = 3 a = 2 a^n = 8 a % n = 2 a^n % n = 2
よって n は素数である (確率が非常に高い)
n = 4 a = 2 a^n = 16 a % n = 2 a^n % n = 0
よって n は素数ではない (確定)
質問・議論
P53 には、「ある数値の冪乗の、別のある数値を法とした剰余を求める手続き」のステップ数が指数 (a^n の n) に対して対数的に増加する (logn) とある。すなわち Θ(log n) というのはフェルマーテスト一回に必要な計算量であり、このフェルマーテストの精度を高めるために何度かフェルマーテストを行うことは考慮されていない。もし m 回ランダムに a を選択しフェルマーテストを行うならば計算量は Θ(m log n) となると考えられる。
今後について
- この章の練習問題 (1.21 ~ 1.28) をどの程度やるかを考え中