sqrtTonelliShanks<F extends CryptoField<F>> static method

Implementation

static FieldSqrtResult<F> sqrtTonelliShanks<F extends CryptoField<F>>({
  required F f,
  required F fPowTm1d2,
  required F rootOfUnity,
  required F one,
  required F Function(F a, F b, bool choice) conditionalSelect,
  int s = 32,
}) {
  // w = f^((t - 1) // 2)
  final F w = fPowTm1d2;

  // v = 2^S
  int v = JubJubFqConst.S;
  F x = w * f;
  F b = x * w;

  // Initialize z as the 2^S root of unity.
  F z = rootOfUnity;
  final r = one;

  // for max_v in (1..=JubJubFq::S).rev()
  for (int maxV = JubJubFqConst.S; maxV >= 1; maxV--) {
    int k = 1;
    F b2k = b.square();
    bool jLessThanV = true; // Choice = 1.into() in Rust corresponds to "true"

    // Inner loop: j runs 2..max_v (exclusive of max_v)
    // (Rust's for j in 2..max_v)
    for (int j = 2; j < maxV; j++) {
      final bool b2kIsOne = b2k == r;

      final F squared = conditionalSelect(b2k, z, b2kIsOne).square();
      // b2k = b2kIsOne ? squared : b2k  (constant-time select)
      b2k = conditionalSelect(squared, b2k, b2kIsOne);
      final F newZ = conditionalSelect(z, squared, b2kIsOne);

      // j_less_than_v &= !j.ct_eq(&v);
      // Rust used a constant-time compare; we approximate with normal compare here.
      // If you need constant-time, make `ctEqInt(j, v)` available.
      jLessThanV = jLessThanV & (j != v);

      // k = u32::conditional_select(&j, &k, b2k_is_one);
      // conditional_select chooses j when b2k_is_one, else k.
      k = IntUtils.ctSelectInt(j, k, b2kIsOne);

      // z = JubJubFq::conditional_select(&z, &new_z, j_less_than_v);
      z = conditionalSelect(z, newZ, jLessThanV);
    }

    final F result = x * z;
    // x = conditional_select(result, x, b.ct_eq(&JubJubFq::ONE));
    x = conditionalSelect(result, x, b == r);
    z = z.square();
    b = b * z;
    v = k;
  }

  final bool ok = (x * x) == f;
  return FieldSqrtResult(x, ok);
}