secp256k1Modinv64Var static method

void secp256k1Modinv64Var(
  1. Secp256k1ModinvSigned x,
  2. Secp256k1ModinvInfo modinfo
)

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].toUnsigned64, g[0].toUnsigned64, 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]).toSigned64;
      }

      /// 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).toSigned64;
    cond = (cond | (fn ^ (fn >> 63))).toSigned64;
    cond = (cond | (gn ^ (gn >> 63))).toSigned64;

    /// 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.toUnsigned64 << 62)).toSigned64;
      g[len - 2] = (g[len - 2] | (gn.toUnsigned64 << 62)).toSigned64;
      --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);
}