class MathUtils {

  public static BigInteger modularSqrt(BigInteger value, BigInteger modulus) {
    // check if square root exists
    if (!isQuadraticResidue(value, modulus)) {
      throw new IllegalArgumentException("Value has no square root in field");
    }

    // find q and s such that (p - 1) = q * 2^s
    Pair<BigInteger, Integer> factors = expressAsProductOfPowerOfTwo(
        modulus.subtract(BigInteger.ONE));
    BigInteger q = factors.getFirst();
    int s = factors.getSecond();

    // find non-quadratic residue for field
    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();

}