L99-33、34
オイラーのトーシェント関数とは「正の整数nに対して、nと互いに素である1以上n以下の自然数の個数φ(n)を与える数論的関数φである!」……え? 数論的関数??
ちょっと何言ってるか分からない。
「自然数」「互いに素(タガイニソ)」はなんか聞いたことがあるようなないような気が……
ここでL99-33の単純な問題の意味を悟る。
「aとbが互いに素」とは、aとbを共に割り切る正の整数が1のみである。つまり、aとbの最大公約数が1であるということ。「互いに素」は英語でcoprimeという……、ふむ。そうL99-33の問題は単純な問題ではなく、「互いに素」かどうかと判定する関数でありました。
例えば、2と3を見てみると最大公約数は1なので「互いに素」と言えます。実際にL99-33のcoprime関数で判定してみると、
(defun coprime (a b)
(eql (gcd- a b) 1)) ;gcd- はL99-32で作成したもの
* (coprime 2 3)
T
そして次に出てくるギリシャ文字「φ」でありますが、ラッキーなことに私、読み方だけ知っていた。φはファイと読みます。なぜ知っているかと言いますと、一時期「ダヴィンチ・コード」系にハマっていて、象徴学とか記号といったものにすごく興味を持ち、図鑑まで買ったからです。
この図鑑はお手頃価格で面白いですよ。
話が逸れましたが、このことからオイラーのファイ関数とか単にオイラーの関数とも呼ばれているようです。
実際の数字でn=6としてやってみると、6と互いに素である1以上6以下の自然数の個数(φ(6))は、1、5で2個となります。それぞれの最大公約数をチェックしてみます。(チェックだけなので、Common Lispのもともと備わっているgcd関数を使いました)
* (gcd 1 6)
1
* (gcd 2 6)
2
* (gcd 3 6)
3
* (gcd 4 6)
2
* (gcd 5 6)
1
* (gcd 6 6)
6
以上のように、最大公約数が1になる「互いに素」なものは1と5だけです。なのでφ(6)=2となります。
OCamlのL99問題のドキュメントのところには、このオイラーのトーシェント関数は最も広く使用されている公開鍵暗号方式(RSA)の一つで重要な役割を果たしていると書かれています。RSA暗号について調べてみると、どうやら鍵生成時に使われているようです。実はすごく身近なものでした。
さて、実際の処理の流れは1以上ｎ以下の自然数を順番にｎと互いに素なのか見ていき、そうならばカウントに1加算する、といったもの。
Common Lispで書くと以下のようなものになりました。
(defun phi (n)
(labels ((count-coprime (acc d)
(if (< d n)
(count-coprime (if (coprime n d) (+ acc 1) acc) (+ 1 d))
acc)))
(if (= n 1)
1
(count-coprime 0 1))))
オイラーのトーシェント関数はまた、nの値が素数の場合、φ(p) = p - 1 が成り立つらしい。実際に上記のphi関数を使って、素数2、3、5、7を見てみると、
CL-USER> (phi 2)
1
CL-USER> (phi 3)
2
CL-USER> (phi 5)
4
CL-USER> (phi 7)
6
なっとる！ということで、とりあえずうまくいっているようです。