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].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);
}