secp256k1Jacobi64MaybeVar static method

Implementation

static int secp256k1Jacobi64MaybeVar(
    Secp256k1ModinvSigned x, Secp256k1ModinvInfo modinfo) {
  /// Start with f=modulus, g=x, eta=-1.
  Secp256k1ModinvSigned f = modinfo.modulus.clone();
  Secp256k1ModinvSigned g = x.clone();
  int j, len = 5;
  BigInt eta = Secp256k1Const.minosOne;

  /// eta = -delta; delta is initially 1
  BigInt cond, fn, gn;
  int jac = 0;
  int count;

  /// The input limbs must all be non-negative.
  _cond(
      g[0] >= BigInt.zero &&
          g[1] >= BigInt.zero &&
          g[2] >= BigInt.zero &&
          g[3] >= BigInt.zero &&
          g[4] >= BigInt.zero,
      "secp256k1Jacobi64MaybeVar");

  _cond((g[0] | g[1] | g[2] | g[3] | g[4]) != BigInt.zero,
      "secp256k1Jacobi64MaybeVar");

  for (count = 0; count < 12; ++count) {
    /// Compute transition matrix and new eta after 62 posdivsteps.
    Secp256k1ModinvTrans t = Secp256k1ModinvTrans();
    final etaR = secp256k1Modinv64Posdivsteps62var(
        eta,
        (f[0] | (f[1].toUnsigned64 << 62)).toUnsigned64,
        (g[0] | (g[1].toUnsigned64 << 62)).toUnsigned64,
        t,
        jac);
    eta = etaR.$1;
    jac = etaR.$2;

    /// Update f,g using that transition matrix.
    _cond(secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.zero) > 0,
        "secp256k1Jacobi64MaybeVar");

    /// f > 0
    _cond(secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.one) <= 0,
        "secp256k1Jacobi64MaybeVar");

    /// f <= modulus
    _cond(secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, BigInt.zero) > 0,
        "secp256k1Jacobi64MaybeVar");

    /// g > 0
    _cond(secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, BigInt.one) < 0,
        "secp256k1Jacobi64MaybeVar");

    /// g < modulus

    secp256k1Modinv64UpdateFg62Var(len, f, g, t);

    /// If the bottom limb of f is 1, there is a chance that f=1.
    if (f[0] == BigInt.one) {
      cond = BigInt.zero;

      /// Check if the other limbs are also 0.
      for (j = 1; j < len; ++j) {
        cond |= f[j];
      }

      /// If so, we're done. When f=1, the Jacobi symbol (g | f)=1.
      if (cond == BigInt.zero) return 1 - 2 * (jac & 1);
    }

    /// Determine if len>1 and limb (len-1) of both f and g is 0.
    fn = f[len - 1];
    gn = g[len - 1];
    cond = (len.toBigInt.toSigned64 - BigInt.two) >> 63;
    cond |= fn;
    cond |= gn;

    /// If so, reduce length.
    if (cond == BigInt.zero) --len;

    _cond(secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.zero) > 0,
        "secp256k1Jacobi64MaybeVar");

    /// f > 0
    _cond(secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.one) <= 0,
        "secp256k1Jacobi64MaybeVar");

    /// f <= modulus
    _cond(secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, BigInt.zero) > 0,
        "secp256k1Jacobi64MaybeVar");

    /// g > 0
    _cond(secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, BigInt.one) < 0,
        "secp256k1Jacobi64MaybeVar");

    /// g < modulus
  }

  /// The loop failed to converge to f=g after 1550 iterations. Return 0, indicating unknown result.
  return 0;
}