ユニット群のサブグループにおける離散対数のSAGE実装

Question

これはthisに関する質問です。簡単には、基底グループを持つElGammal暗号システムでは、素数pを法とする単位のグループは、システムを破壊するために離散対数問題を解くためにインデックス2のサブグループを見つけるように言われています。

明らかに、素数がモジュロであり、xがジェネレータである場合、x^2はインデックス2のサブグループを生成します。今、sageの離散対数問題を解決するよい方法はありますか？このサブグループの離散対数問題を解く結果を、グループ全体でどのように解くことができますか？

Answer 1

セージは、有限体での離散対数を計算する方法を知っている：

sage: K = GF(19) 
sage: z = K.primitive_element() 
sage: a = K.random_element() 
sage: b = a.log(z) 
sage: z^b == a 
True 

あなたはこれが唯一のおもちゃで2

sage: x = z^2 
sage: a = K.random_element()^2 
sage: a.log(x) 
6 

指数のサブグループに離散対数を解決するために、この機能を使用することができますこれは完全なグループΠ9*の離散対数を解くよりも効率的ではないことに注意してください。

ジェネリックアルゴリズム（Baby Step-Giantステップ、Pollard rhoなど）の効率がサブグループのサイズに直接関係していることは事実です。しかし、有限体（数場ふるい、関数場ふるい）における離散対数を解くために使用されるアルゴリズムは、乗法下位群の大きさにほとんど影響されず、一般に一般的なアルゴリズムよりはるかに効率的です。