sqrtUV function

Tuple<bool, BigInt> sqrtUV(
  1. BigInt u,
  2. BigInt v
)

sqrt u/v

Implementation

Tuple<bool, BigInt> sqrtUV(BigInt u, BigInt v) {
  final P = Curves.curveEd25519.p;
  final v3 = positiveMod(v * v * v, P);
  final v7 = positiveMod(v3 * v3 * v, P);
  final pow = _pow252(u * v7);
  var x = positiveMod(u * v3 * pow, P);
  final vx2 = positiveMod(v * x * x, P);
  final root1 = x;

  final root2 = positiveMod(x * sqrtM1, P);
  final useRoot1 = vx2 == u;
  final useRoot2 = vx2 == positiveMod(-u, P);
  final noRoot = vx2 == positiveMod(-u * sqrtM1, P);

  if (useRoot1) {
    x = root1;
  }
  if (useRoot2 || noRoot) {
    x = root2;
  }

  if (isOdd(x, P)) {
    x = positiveMod(-x, P);
  }
  return Tuple(useRoot1 || useRoot2, x);
}