>>348 public class A { public static void main(String[] args) { long n = 325; long e = 30; long m = 23; System.out.println(n + "^" + e + "(mod " + m + ") = " + java.math.BigInteger.valueOf(n).modPow(java.math.BigInteger.valueOf(e), java.math.BigInteger.valueOf(m))); /*System.out.println(n + "^" + e + "(mod " + m + ") = " + modPow(n, e, m));*/ } /*private static long modPow(long n, long e, long m) { long p = n % m; long q = 1; while (e > 0) { if (e % 2 != 0) { q *= p; q %= m; } e /= 2; p *= p; p %= m; } return q; }*/ } 例示された325の冪乗計算の途中がおかしいような。結果は合っているけど。 325^a(mod m) = ((325^(a/2)(mod m))^2)(mod m)を利用。例えば、23を法として、325≡3、325^2≡3*3≡9、325^4≡9*9≡12、... ビットが立ってる桁も順番に掛け算するたびにmodを求めている。
