MathUtils { public static BigInteger modularSqrt(BigInteger value, BigInteger modulus) { if (!isQuadraticResidue(value, modulus)) { throw new IllegalArgumentException("Value has no square root in field"); } Pair<BigInteger, Integer> factors = expressAsProductOfPowerOfTwo( modulus.subtract(BigInteger.ONE)); BigInteger q = factors.getFirst(); int s = factors.getSecond(); BigInteger z = getNonQuadraticResidue(modulus); int m = s; BigInteger c = z.modPow(q, modulus); BigInteger t = value.modPow(q, modulus); BigInteger r = value.modPow(q.add(BigInteger.ONE).divide(TWO), modulus); while (!t.equals(BigInteger.ONE)) { int i = 0; BigInteger power = t; while (!power.equals(BigInteger.ONE)) { power = power.pow(2).mod(modulus); i++; } BigInteger exp = TWO.pow(m - i - 1).mod(modulus); BigInteger b = c.modPow(exp, modulus); m = i; c = b.pow(2).mod(modulus); t = t.multiply(c).mod(modulus); r = r.multiply(b).mod(modulus); } return r; } private  MathUtils(); static boolean isQuadraticResidue(BigInteger value, BigInteger modulus); static BigInteger modularSqrt(BigInteger value, BigInteger modulus); static BigInteger sum(List<BigInteger> summands, BigInteger modulus);  }
@Test public void testModularSqrt() { BigInteger value = new BigInteger("2"); BigInteger actual = MathUtils.modularSqrt(value, modulus); BigInteger expected = new BigInteger("62"); assertEquals(expected, actual); }
@Test public void testModularSqrtBigModulus() { BigInteger bigModulus = new BigInteger("340282366920938463463374607431768211283"); BigInteger value = new BigInteger("180740608519057052622341767564917758093"); BigInteger actual = MathUtils.modularSqrt(value, bigModulus); assertEquals(actual.pow(2).mod(bigModulus), value); }
@Test(expected = IllegalArgumentException.class) public void testModularSqrtNoSqrt() { MathUtils.modularSqrt(new BigInteger("23"), modulus); }