secp256k1Jacobi64MaybeVar static method
Compute the Jacobi symbol of x modulo modinfo.modulus (variable time). gcd(x,modulus) must be 1.
Implementation
static int secp256k1Jacobi64MaybeVar(
Secp256k1ModinvSigned x, Secp256k1ModinvInfo modinfo) {
/// Start with f=modulus, g=x, eta=-1.
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;
int jac = 0;
int count;
/// The input limbs must all be non-negative.
_cond(
g[0] >= BigInt.zero &&
g[1] >= BigInt.zero &&
g[2] >= BigInt.zero &&
g[3] >= BigInt.zero &&
g[4] >= BigInt.zero,
"secp256k1Jacobi64MaybeVar");
_cond((g[0] | g[1] | g[2] | g[3] | g[4]) != BigInt.zero,
"secp256k1Jacobi64MaybeVar");
for (count = 0; count < 12; ++count) {
/// Compute transition matrix and new eta after 62 posdivsteps.
Secp256k1ModinvTrans t = Secp256k1ModinvTrans();
final etaR = secp256k1Modinv64Posdivsteps62var(
eta,
(f[0] | (f[1].toUnsigned64 << 62)).toUnsigned64,
(g[0] | (g[1].toUnsigned64 << 62)).toUnsigned64,
t,
jac);
eta = etaR.$1;
jac = etaR.$2;
/// Update f,g using that transition matrix.
_cond(secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.zero) > 0,
"secp256k1Jacobi64MaybeVar");
/// f > 0
_cond(secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.one) <= 0,
"secp256k1Jacobi64MaybeVar");
/// f <= modulus
_cond(secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, BigInt.zero) > 0,
"secp256k1Jacobi64MaybeVar");
/// g > 0
_cond(secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, BigInt.one) < 0,
"secp256k1Jacobi64MaybeVar");
/// g < modulus
secp256k1Modinv64UpdateFg62Var(len, f, g, t);
/// If the bottom limb of f is 1, there is a chance that f=1.
if (f[0] == BigInt.one) {
cond = BigInt.zero;
/// Check if the other limbs are also 0.
for (j = 1; j < len; ++j) {
cond |= f[j];
}
/// If so, we're done. When f=1, the Jacobi symbol (g | f)=1.
if (cond == BigInt.zero) return 1 - 2 * (jac & 1);
}
/// Determine if len>1 and limb (len-1) of both f and g is 0.
fn = f[len - 1];
gn = g[len - 1];
cond = (len.toBigInt.toSigned64 - BigInt.two) >> 63;
cond |= fn;
cond |= gn;
/// If so, reduce length.
if (cond == BigInt.zero) --len;
_cond(secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.zero) > 0,
"secp256k1Jacobi64MaybeVar");
/// f > 0
_cond(secp256k1Modinv64MulCmp62(f, len, modinfo.modulus, BigInt.one) <= 0,
"secp256k1Jacobi64MaybeVar");
/// f <= modulus
_cond(secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, BigInt.zero) > 0,
"secp256k1Jacobi64MaybeVar");
/// g > 0
_cond(secp256k1Modinv64MulCmp62(g, len, modinfo.modulus, BigInt.one) < 0,
"secp256k1Jacobi64MaybeVar");
/// g < modulus
}
/// The loop failed to converge to f=g after 1550 iterations. Return 0, indicating unknown result.
return 0;
}