secp256k1Modinv64 static method

Implementation

static void secp256k1Modinv64(
  Secp256k1ModinvSigned x,
  Secp256k1ModinvInfo modinfo,
) {
  /// Start with d=0, e=1, f=modulus, g=x, zeta=-1.
  Secp256k1ModinvSigned d = Secp256k1ModinvSigned();
  Secp256k1ModinvSigned e = Secp256k1Const.modeInvOne.clone();
  Secp256k1ModinvSigned f = modinfo.modulus.clone();
  Secp256k1ModinvSigned g = x.clone();
  int i;
  BigInt zeta = (-1).toBigInt;

  /// Do 10 iterations of 59 divsteps each = 590 divsteps. This suffices for 256-bit inputs.
  for (i = 0; i < 10; ++i) {
    /// Compute transition matrix and new zeta after 59 divsteps.
    Secp256k1ModinvTrans t = Secp256k1ModinvTrans();
    zeta = secp256k1Modinv64Divsteps59(zeta, 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,
            5,
            modinfo.modulus,
            Secp256k1Const.minosOne,
          ) >
          0,
      "secp256k1Modinv64",
    );
    _cond(
      secp256k1Modinv64MulCmp62(f, 5, modinfo.modulus, BigInt.one) <= 0,
      "secp256k1Modinv64",
    );
    _cond(
      secp256k1Modinv64MulCmp62(
            g,
            5,
            modinfo.modulus,
            Secp256k1Const.minosOne,
          ) >
          0,
      "secp256k1Modinv64",
    );

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

    secp256k1Modinv64UpdateFg62(f, g, t);

    _cond(
      secp256k1Modinv64MulCmp62(
            f,
            5,
            modinfo.modulus,
            Secp256k1Const.minosOne,
          ) >
          0,
      "secp256k1Modinv64",
    );

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

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

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

    /// g <  modulus
  }

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

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