sqrtRatio method

Implementation

FieldSqrtResult<F> sqrtRatio(F num, F div) {
  // Helper for repeated squaring
  F sqr(F x, int i) {
    var res = x;
    for (var j = 0; j < i; j++) {
      res = res.square();
    }
    return res;
  }

  // s = div^(2^S - 1) using an addition chain
  F s = div;
  for (var i = 0; i < 5; i++) {
    s = sqr(s, 1 << i) * s;
  }

  // t = div^(2^(S+1) - 1)
  final t = s.square() * div;

  // w = (num * t)^((T-1)/2) * s
  final w = (t * num).powByTMinus1Over2() * s;

  // v = u^((T-1)/2)
  final v = w * div;

  // uv = u * v
  final uv = w * num;

  // Compute sqrt_common
  final res = sqrtCommon(uv, v);

  // Check square vs nonsquare
  final sqdiv = res.square() * div;
  final isSquare = (sqdiv - num).isZero();
  final isNonSquare = (sqdiv - rootOfUnity * num).isZero();

  assert(num.isZero() || div.isZero() || (isSquare ^ isNonSquare));

  return FieldSqrtResult(res, isSquare);
}