sqrt static method

BigInt sqrt(
  1. BigInt n
)

Implementation

static BigInt sqrt(BigInt n) {
  // So, a special, fast case. Paper: "Square Roots from 1;24,51,10 to Dan Shanks".
  var r = BigInt.one;
  // powMod: modular exponentiation.
  for (var num = n, e = (P + BigInt.one) ~/ BigInt.from(4);
      e > BigInt.zero;
      e >>= 1) {
    // Uses exponentiation by squaring.
    if ((e & BigInt.one) == BigInt.one) {
      r = (r * num) % P;
    }
    // Not constant-time.
    num = (num * num) % P;
  }
  /* return mod(r * r) == n ? r : err('sqrt invalid'); */ // check if result is valid
  if (mod(r * r) == n) {
    return r;
  }
  throw Exception('sqrt invalid');
}