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 CryptoException.failed(
      "modularSquareRootPrime",
      reason: "$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 CryptoException.failed(
          "modularSquareRootPrime",
          reason: "p is not prime.",
        );
      }
      return result[0];
    }
  }
  throw CryptoException.failed(
    "modularSquareRootPrime",
    reason: "No suitable 'b' found.",
  );
}