secp256k1Modinv64Divsteps59 static method

BigInt secp256k1Modinv64Divsteps59(
  1. BigInt zeta,
  2. BigInt f0,
  3. BigInt g0,
  4. Secp256k1ModinvTrans t,
)

Implementation

static BigInt secp256k1Modinv64Divsteps59(
  BigInt zeta,
  BigInt f0,
  BigInt g0,
  Secp256k1ModinvTrans t,
) {
  BigInt u = 8.toBigInt, v = BigInt.zero, q = BigInt.zero, r = 8.toBigInt;
  BigInt c1, c2;
  BigInt mask1, mask2, f = f0, g = g0, x, y, z;
  int i;

  for (i = 3; i < 62; ++i) {
    _cond(
      (f & BigInt.one).toU64 == BigInt.one,
      "secp256k1Modinv64Divsteps59",
    );
    _cond(
      (u * f0 + v * g0).toU64 == (f << i).toU64,
      "secp256k1Modinv64Divsteps59",
    );
    _cond(
      (q * f0 + r * g0).toU64 == (g << i).toU64,
      "secp256k1Modinv64Divsteps59",
    );

    /// Compute conditional masks for (zeta < 0) and for (g & 1).
    c1 = (zeta >> 63).toU64;
    mask1 = c1;
    c2 = (g & BigInt.one).toU64;
    mask2 = (-c2).toU64;

    /// Compute x,y,z, conditionally negated versions of f,u,v.
    x = ((f ^ mask1) - mask1).toU64;
    y = ((u ^ mask1) - mask1).toU64;
    z = ((v ^ mask1) - mask1).toU64;

    /// Conditionally add x,y,z to g,q,r.
    g = (g + (x & mask2)).toU64;
    q = (q + (y & mask2)).toU64;
    r = (r + (z & mask2)).toU64;

    /// In what follows, c1 is a condition mask for (zeta < 0) and (g & 1).
    mask1 = (mask1 & mask2).toU64;

    /// Conditionally change zeta into -zeta-2 or zeta-1.
    zeta = ((zeta ^ mask1) - BigInt.one).toI64;

    /// Conditionally add g,q,r to f,u,v.
    f = (f + (g & mask1)).toU64;
    u = (u + (q & mask1)).toU64;
    v = (v + (r & mask1)).toU64;

    /// Shifts
    g = (g >> 1).toU64;
    u = (u << 1).toU64;
    v = (v << 1).toU64;

    /// Bounds on zeta that follow from the bounds on iteration count (max 10*59 divsteps).
    _cond(
      zeta >= -591.toBigInt && zeta <= 591.toBigInt,
      "secp256k1Modinv64Divsteps59",
    );
  }

  /// Return data in t and return value.
  // t.u = u.toI64;
  // t.v = v.toI64;
  // t.q = q.toI64;
  // t.r = r.toI64;
  t.set(u, v, q, r);

  _cond(
    secp256k1Modinv64DetCheckPow2(t, 65, 0).toBool,
    "secp256k1Modinv64Divsteps59",
  );

  return zeta;
}