secp256k1Modinv64Var static method

Implementation

static void secp256k1Modinv64Var(
  Secp256k1ModinvSigned x,
  Secp256k1ModinvInfo modinfo,
) {
  Secp256k1ModinvSigned d = Secp256k1ModinvSigned();
  Secp256k1ModinvSigned e = Secp256k1Const.modeInvOne.clone();

  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;

  /// Do iterations of 62 divsteps each until g=0.
  while (true) {
    /// Compute transition matrix and new eta after 62 divsteps.
    Secp256k1ModinvTrans t = Secp256k1ModinvTrans();
    eta = secp256k1Modinv64Divsteps62Var(eta, f[0].toU64, g[0].toU64, t);

    /// Update d,e using that transition matrix.
    secp256k1Modinv64UpdateDe62(d, e, t, modinfo);

    /// Update f,g using that transition matrix.
    _cond(
      secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, (-1).toBigInt) > 0,
      "secp256k1Modinv64Var",
    );

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

    /// f <= modulus
    _cond(
      secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, (-1).toBigInt) > 0,
      "secp256k1Modinv64Var",
    );

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

    /// g <  modulus

    secp256k1Modinv64UpdateFg62Var(len, f, g, t);

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

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

      /// If so, we're done.
      if (cond == BigInt.zero) break;
    }

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

    /// If so, reduce length, propagating the sign of f and g's top limb into the one below.
    if (cond == BigInt.zero) {
      f[len - 2] = (f[len - 2] | (fn.toU64 << 62)).toI64;
      g[len - 2] = (g[len - 2] | (gn.toU64 << 62)).toI64;
      --len;
    }
    _cond(
      secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, (-1).toBigInt) > 0,
      "secp256k1Modinv64Var",
    );

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

    /// f <= modulus
    _cond(
      secp256k1Modinv64MulCmp62(
            g,
            len,
            modinfo.modulus,
            Secp256k1Const.minosOne,
          ) >
          0,
      "secp256k1Modinv64Var",
    );

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

    /// g <  modulus
  }

  /// g == 0
  _cond(
    secp256k1Modinv64MulCmp62(
          g,
          len,
          Secp256k1Const.secp256k1Signed62One,
          BigInt.zero,
        ) ==
        0,
    "secp256k1Modinv64Var",
  );
  // /// |f| == 1, or (x == 0 and d == 0 and f == modulus)
  _cond(
    secp256k1Modinv64MulCmp62(
              f,
              len,
              Secp256k1Const.secp256k1Signed62One,
              (-1).toBigInt,
            ) ==
            0 ||
        secp256k1Modinv64MulCmp62(
              f,
              len,
              Secp256k1Const.secp256k1Signed62One,
              BigInt.one,
            ) ==
            0 ||
        (secp256k1Modinv64MulCmp62(
                  x,
                  5,
                  Secp256k1Const.secp256k1Signed62One,
                  BigInt.zero,
                ) ==
                0 &&
            secp256k1Modinv64MulCmp62(
                  d,
                  5,
                  Secp256k1Const.secp256k1Signed62One,
                  BigInt.zero,
                ) ==
                0 &&
            secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.one) ==
                0),
    "secp256k1Modinv64Var",
  );

  /// Optionally negate d, normalize to [0,modulus), and return it.
  secp256k1Modinv64Normalize62(d, f[len - 1], modinfo);
  x.set(d);
}