BaileyBorweinPlouffe extends Configured implements Tool { static long mod(final long e, final long n) { long mask = (e & 0xFFFFFFFF00000000L) == 0 ? 0x00000000FFFFFFFFL : 0xFFFFFFFF00000000L; mask &= (e & 0xFFFF0000FFFF0000L & mask) == 0 ? 0x0000FFFF0000FFFFL : 0xFFFF0000FFFF0000L; mask &= (e & 0xFF00FF00FF00FF00L & mask) == 0 ? 0x00FF00FF00FF00FFL : 0xFF00FF00FF00FF00L; mask &= (e & 0xF0F0F0F0F0F0F0F0L & mask) == 0 ? 0x0F0F0F0F0F0F0F0FL : 0xF0F0F0F0F0F0F0F0L; mask &= (e & 0xCCCCCCCCCCCCCCCCL & mask) == 0 ? 0x3333333333333333L : 0xCCCCCCCCCCCCCCCCL; mask &= (e & 0xAAAAAAAAAAAAAAAAL & mask) == 0 ? 0x5555555555555555L : 0xAAAAAAAAAAAAAAAAL; long r = 2; for (mask >>= 1; mask > 0; mask >>= 1) { r *= r; r %= n; if ((e & mask) != 0) { r += r; if (r >= n) r -= n; } } return r; }  int run(String[] args); static void main(String[] argv); static final String DESCRIPTION; }
@Test public void testMod() { final BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE); for(long n = 3; n < 100; n++) { for (long e = 1; e < 100; e++) { final long r = TWO.modPow( BigInteger.valueOf(e), BigInteger.valueOf(n)).longValue(); Assert.assertEquals("e=" + e + ", n=" + n, r, BaileyBorweinPlouffe .mod(e, n)); } } }