javaでべき乗余

質問

テストプログラムとしてjavaでべき乗余を求めるプログラムを作っているんですがint N
の大きさを大きくするとかなり時間がかかってしまいます。実行時間を早くする方法はないでしょうか？

import java.math.BigInteger;
import java.util.Random;
public class s1{
public static void main(String args[]){
BigInteger a = new BigInteger("2");
int N = 100000;
BigInteger n,p,q;
Random rnd = new Random();
BigInteger f[] = new BigInteger[N];
int bit = 512;
int k = 10;

p = new BigInteger(bit,k, rnd);
q = new BigInteger(bit,k, rnd);
n = p.multiply(q);

int j;

for(j=0;j<N;j++){

f[j]=(a.modPow(BigInteger.valueOf(j), n)) ;

}

for(j=0;j<N;j++){
System.out.println(j +"="+f[j]);
}

}
}

回答No.1

Tacosan · ベストアンサー

えぇと....
f[j] = f[j-1]*a mod n
という感じで計算しちゃいかんの?