離散対数の計算について

質問

m = 7のとき、φ(7) = 6なので
3^1 ≡ 3 ( mod 7), 3^2 ≡ 2 ( mod 7), 3^3 ≡ 6 ( mod 7)
3^4 ≡ 4 ( mod 7), 3^5 ≡ 5 ( mod 7), 3^6 ≡ 1 ( mod 7)
よって3が７の原始根というのはわかったのですが

ここから離散対数を求める過程がわかりません。
ind_3 1 = 6, ind_3 2 = 2, ind_3 3 = 1,
ind_3 4 = 4, ind_3 5 = 5, ind_3 6 = 3
この答えはどうやって出しているのでしょうか？お願いします。

回答No.1

Tacosan · ベストアンサー

離散じゃないふつ～の対数はどう計算していますか?

例えば
3^2 = 9
ですが, ここから
log_3 9 = 2
はどうしてでてくると思いますか?

回答No.2

Rice-Etude

＃有限巡回群における離散対数を求める問題になっていますので、それを前提として回答いたします。

koni-amiさんがいくつか離散対数に関する質問をされていたので、気になっていました。

koni-amiさんは、「離散対数問題」というのをお聞きになったことはありますか？実は離散対数を求めるのに（計算量のオーダーが多項式時間になるという意味で）効率的なアルゴリズムというのは存在しません。

一般的に考えるなら3^1、3^2、…と求めていって該当する数字がでるまで計算することになります。また、これよりもう少し効率的に離散対数を求めるアルゴリズムというのも存在します。しかしながら、今分かっている最も効率の良いアルゴリズムでも準指数オーダーの計算量となっていて、特定条件な時でもない限り基本的にはコンピュータを使っても現実的な時間で離散対数を解くことはできません。

＃暗号の中には、この性質を安全性の根拠としているプロトコル（例：Diffie-Hellman鍵交換、ElGamal暗号 ）があります。

この辺のことが興味ありましたら、公開鍵暗号に関するテキスト／参考書をご覧になれば詳しく載っていますので、ぜひ図書館などでご覧下さい。