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).toUnsigned64 == BigInt.one,
        "secp256k1Modinv64Divsteps59");
    _cond((u * f0 + v * g0).toUnsigned64 == (f << i).toUnsigned64,
        "secp256k1Modinv64Divsteps59");
    _cond((q * f0 + r * g0).toUnsigned64 == (g << i).toUnsigned64,
        "secp256k1Modinv64Divsteps59");

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

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

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

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

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

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

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

    /// 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.toSigned64;
  // t.v = v.toSigned64;
  // t.q = q.toSigned64;
  // t.r = r.toSigned64;
  t.set(u, v, q, r);

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

  return zeta;
}