modularSquareRootPrime static method

BigInt modularSquareRootPrime(BigInt a, BigInt p)

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 == BigInt.from(-1)) {
    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) == BigInt.from(-1)) {
      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 MessageException("No suitable 'b' found.");
}