このページは、当初 981225.html という名前で作られたものです。
前回出した課題その３にはいろいろなやり方があると思いますが、 一つの方法にそってヒントを出しておきます。 なお、以下に現われる関数名はいずれも一例です。
第一ステップ： 自然数 n, base, x に対し mod n での base の x 乗を返す関数 modpower を書きます。 base の x 乗を計算してから n で割ったあまりを求めるやり方だと、 9 の 11 乗を求める程度の計算で破綻をきたします。 9 の 11 乗は 8 の 11 乗より大きく、 8 の 11 乗は 2 の 33 乗に等しくて、 それは int 型におさまりきれない数だからです。 前回サンプルとして示した power を元に工夫してみてください。
第二ステップ： 上のステップで作った modpower を利用して、 素数 p と p 未満の自然数 a に対し a が p を法とする原始根であるかどうかを返す関数 isprimroot を書きます。 返す値は YES のとき 1, NO のとき 0 と #define しておけばよいでしょう。 is... という名前の関数が「〜かどうか」を返すものであること、 および YES が 0 以外で NO が 0 というのはＣ言語における慣習です。
第三ステップ： 上のステップで作った isprimroot を利用して、 素数 p に対し p を法とする最小の原始根を返す関数 primroot を書きます。
※ 第一ステップと第二ステップを合わせて一つのステップとすれば、 mod p での a の 2 乗の計算結果を利用して a の 3 乗が、 a の 3 乗を利用して a の 4 乗が計算できる。 上の方法で毎回新たに計算し直しているのはムダである。 ほかにも、 数学上の考察を利用すれば計算の手間が省けるところはあろうが、 今回の課題はとにかくきちんと動くものを書けばいいので、 わかりやすいように書けばそれでよろしい。
※ このようにいくつかの関数に分けて書く場合は、 おのおのの関数が何を計算するものなのかを説明するコメントをつけること。 そうでないと、何をしているのか見る側にはさっぱりわからない。
※ 各ステップごとにしかるべき main 関数をつけてコンパイル・実行し、 正しく動作することを確認すべきであることはいうまでもない。 なお、途中のステップの main 関数は提出するには及ばない。 提出されると混乱するかもしれないので、提出しないこと。