多倍長演算での累乗

質問

ElGamal暗号のプログラムをjavaで書いているのですが、累乗の計算で困っています。
RSA暗号で出てくる「a^b mod p」の場合はBigIntegerを使うと「a.modPow(b,p)」ですよね。
しかし今回使う式は「a*(b^p-x-1) mod p」といったような式です。
ということで

a.miltiply.b.pow(p.subtract(x).subtract(x)).mod(p)

としたんですが、コンパイルしてエラーが出たので調べたところ、指数部分はint型でないとpow()が使えないことを知りました。
しかし、この式の指数部分が1024ビットなので32ビットのint型には変換できません。

int型以外の値で累乗するにはどうしたらいいのでしょうか？

回答No.2

rinkun

まず、なぜpowの引数がint型なのかを考えましょう。
1024ビットで表現される数だけ累乗するとどれほどの大きさの数になるか考えればint型以外の値で累乗するのが現実的ではないことが分かります。

正しい方針は計算式を適当に変形してmodPowを使えるようにすることです。
modと四則演算の基本的な関係式で質問の式をmodPowを使う形に変換できるはずです。
# 具体的な変形は公式を覚えてないので省略

回答No.1

pcbeginner

int型以外の値で累乗するプログラムを作る。