modularSquareRootPrime static method

BigInt modularSquareRootPrime(BigInt a, BigInt p)

Calculate the modular square root of 'a' modulo prime 'p' using algorithms from the Handbook of Applied Cryptography (3.34 to 3.39).

Implementation

static BigInt modularSquareRootPrime(BigInt a, BigInt p) {
  assert(BigInt.zero <= a && a < p);
  assert(p > BigInt.one);

  if (a == BigInt.zero) {
    return BigInt.zero;
  }

  if (p == BigInt.two) {
    return a;
  }

  final jacobiSymbol = jacobi(a, p);

  if (jacobiSymbol.isNegative) {
    throw SquareRootError("$a has no square root modulo $p");
  }

  if (p % BigInt.from(4) == BigInt.from(3)) {
    return a.modPow((p + BigInt.one) ~/ BigInt.from(4), p);
  }

  if (p % BigInt.from(8) == BigInt.from(5)) {
    final d = a.modPow((p - BigInt.one) ~/ BigInt.from(4), p);
    if (d == BigInt.one) {
      return a.modPow((p + BigInt.from(3)) ~/ BigInt.from(8), p);
    }
    // assert(d == p - BigInt.one);
    return (BigInt.from(2) *
            a *
            (BigInt.from(4) * a)
                .modPow((p - BigInt.from(5)) ~/ BigInt.from(8), p)) %
        p;
  }

  for (BigInt b = BigInt.from(2); b < p; b += BigInt.one) {
    if (jacobi(b * b - BigInt.from(4) * a, p).isNegative) {
      final quadraticForm = [a, -b, BigInt.one];
      final result = polynomialExponentiationMod([BigInt.zero, BigInt.one],
          (p + BigInt.one) ~/ BigInt.from(2), quadraticForm, p);
      if (result[1] != BigInt.zero) {
        throw const SquareRootError("p is not prime");
      }
      return result[0];
    }
  }

  throw const SquareRootError("No suitable 'b' found.");
}