3進展開による有限体上での累乗計算の方法

質問

僕はペアリング暗号システムを作るために現在有限体上（標数3^97）の楕円曲線の計算プログラムを作成しています。その過程ででてくる数字で、a^((3^97+1)/4)という数字が出てきます。この指数を2進展開してdouble and add法を使って計算していたのですが、この方法だと少し計算速度が遅いのです。
そこで(3^97+1)/4という数字を3進数に直して演算を行えば高速化ができると思いました(標数が3の倍数になるから)が、その計算方法がわかりません。
double and add法のような形での計算方法が知りたいです。知っている方がいたら、是非教えてください。

回答No.1

Tacosan

a_n = (3^(2n+1)+1)/4 とおくと a_0 = 1 かつ a_(n+1) = 9 a_n - 2 です.
だから,
x = a からはじめて
x = x^9 / a^2
を繰り返せばいい (x^9 = x^(2^3)×x なので, ここは double and add で計算) んだろうけど.... a^2 でわるところで, どのくらい性能が落るかはわかりません. 実用上は 1/a^2 を計算しておけばまし?

お礼

回答ありがとうございます。
参考にさせていただきます＾＾
考えてみたらこれはパソコンのカテゴリよりは数学のカテゴリで投稿するべき質問でしたね。
すみませんでした。