MathHelper { public static BigInteger CRT(BigInteger[] congs, BigInteger[] moduli) { BigInteger prodModuli = BigInteger.ONE; for (BigInteger mod : moduli) { prodModuli = prodModuli.multiply(mod); } BigInteger[] M = new BigInteger[moduli.length]; for (int i = 0; i < moduli.length; i++) { M[i] = prodModuli.divide(moduli[i]); } BigInteger retval = BigInteger.ZERO; for (int i = 0; i < moduli.length; i++) { BigInteger tmp = extendedEuclid(moduli[i], M[i]).c; retval = retval.add(congs[i].multiply(tmp).multiply(M[i]).mod(prodModuli)); } return retval.mod(prodModuli); } private  MathHelper(); static BigInteger intfloordiv(BigInteger c, BigInteger d); static BigInteger intceildiv(BigInteger c, BigInteger d); static int intfloordiv(int c, int d); static int intceildiv(int c, int d); static BigIntegerTripple extendedEuclid(BigInteger u, BigInteger v); static BigInteger gcd(BigInteger u, BigInteger v); static BigInteger inverseMod(BigInteger a, BigInteger p); static BigInteger CRT(BigInteger[] congs, BigInteger[] moduli); static BigInteger CRT(List<BigInteger> congs, List<BigInteger> moduli); static BigInteger bigIntSqRootFloor(BigInteger x); static BigInteger bigIntSqRootCeil(BigInteger x);  }
@Test public void testCRT() { BigInteger[] congs = { new BigInteger("3"), new BigInteger("4"), new BigInteger("5") }; BigInteger[] moduli = { new BigInteger("2"), new BigInteger("3"), new BigInteger("2") }; assertEquals(4, MathHelper.CRT(congs, moduli).intValue()); BigInteger[] congs2 = { new BigInteger("2"), new BigInteger("3"), new BigInteger("1") }; BigInteger[] moduli2 = { new BigInteger("3"), new BigInteger("4"), new BigInteger("5") }; assertEquals(11, MathHelper.CRT(congs2, moduli2).intValue()); }