- 課題
- 次の２つの関数を完成せよ。
- elementorder(a, m) : a mod m の（乗法）位数を計算する関数
- primitiveroot(p) : 素数 p を法とする原始根をひとつ求める関数
（ 講義中 [3] で述べた単純なアルゴリズムでよい。）
- 20 から 30 までの法 m に対し、
全ての既約剰余類 a mod m の乗法位数を計算して
(Z/mZ)× が巡回群になる場合・ならない場合について観察せよ。
- 100 以下の奇素数 p に対して法 p の原始根をひとつずつ求めよ。
- 発展課題
大きな素数 p で、p-1 の素因数分解が解っている場合に、
素数 p を法とする原始根をひとつ求めるサンプルプログラム primitiveroot.py
を download し、p のサイズを変えて実行したり、上記の関数 primitiveroot との
時間比較を行ったりせよ。
- 提出期限 6月23日(木) 17:00
( 512号室ポストまで )
- 関数定義部（今まで作った関数をまとめたもの）
crypto050609.py
- 雛形
hina050609.py
- C言語版の関数定義部（今まで作った関数をまとめたもの）
crypto050609.h
- C言語による実装例
rep08.c
- 大きな素数 p を法とする原始根をひとつ求めるサンプルプログラム
primitiveroot.py と
実行例
戻る
|