- 647 名前：FM東京 [04/10/03 02:20:50]
- >>646
xって書くから判りにくくなるんですよ。
p:素数、g (Z/pZ)^*のgenerator, a整数 st. a|p-1
で
Y=g^(a*r) mod p (r:乱数たぶんp-1と素)が与えられた時、
y=g^r mod p がわかるか？
っていいたいんでしょ？？？
で、これは、f(t)=t^a-Y \in Fp[x]を解けばいいんで、
O(a^3 log^3 p)くらい？で解けますよね（ちゃんと見積もっていません）。
だから、aが小さければ、解ける。
一方で、この解は必ずa個出てくるはずなので、解くのは困難になる
（はずだ）けども、
aが大きかったら、解がたくさん（a個）在りすぎて何かに使えるようには見えない
にやーー。
