Differential D9403 Diff 28170 src/secp256k1/src/modinv64_impl.h

Changeset View

Standalone View

src/secp256k1/src/modinv64_impl.h

Show All 12 Lines

/* This file implements modular inversion based on the paper "Fast constant-time gcd computation and		/* This file implements modular inversion based on the paper "Fast constant-time gcd computation and
* modular inversion" by Daniel J. Bernstein and Bo-Yin Yang.		* modular inversion" by Daniel J. Bernstein and Bo-Yin Yang.
*		*
* For an explanation of the algorithm, see doc/safegcd_implementation.md. This file contains an		* For an explanation of the algorithm, see doc/safegcd_implementation.md. This file contains an
* implementation for N=62, using 62-bit signed limbs represented as int64_t.		* implementation for N=62, using 62-bit signed limbs represented as int64_t.
*/		*/

		#ifdef VERIFY
		/* Helper function to compute the absolute value of an int64_t.
		* (we don't use abs/labs/llabs as it depends on the int sizes). */
		static int64_t secp256k1_modinv64_abs(int64_t v) {
		VERIFY_CHECK(v > INT64_MIN);
		if (v < 0) return -v;
		return v;
		}

		static const secp256k1_modinv64_signed62 SECP256K1_SIGNED62_ONE = {{1}};

		/* Compute afactor and put it in r. All but the top limb in r will be in range [0,2^62). /
		static void secp256k1_modinv64_mul_62(secp256k1_modinv64_signed62 r, const secp256k1_modinv64_signed62 a, int64_t factor) {
		const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
		int128_t c = 0;
		int i;
		for (i = 0; i < 4; ++i) {
		c += (int128_t)a->v[i] * factor;
		r->v[i] = (int64_t)c & M62; c >>= 62;
		}
		c += (int128_t)a->v[4] * factor;
		VERIFY_CHECK(c == (int64_t)c);
		r->v[4] = (int64_t)c;
		}

		/* Return -1 for a<bfactor, 0 for a==bfactor, 1 for a>bfactor. /
		static int secp256k1_modinv64_mul_cmp_62(const secp256k1_modinv64_signed62 a, const secp256k1_modinv64_signed62 b, int64_t factor) {
		int i;
		secp256k1_modinv64_signed62 am, bm;
		secp256k1_modinv64_mul_62(&am, a, 1); /* Normalize all but the top limb of a. */
		secp256k1_modinv64_mul_62(&bm, b, factor);
		for (i = 0; i < 4; ++i) {
		/* Verify that all but the top limb of a and b are normalized. */
		VERIFY_CHECK(am.v[i] >> 62 == 0);
		VERIFY_CHECK(bm.v[i] >> 62 == 0);
		}
		for (i = 4; i >= 0; --i) {
		if (am.v[i] < bm.v[i]) return -1;
		if (am.v[i] > bm.v[i]) return 1;
		}
		return 0;
		}
		#endif

/* Take as input a signed62 number in range (-2*modulus,modulus), and add a multiple of the modulus		/* Take as input a signed62 number in range (-2*modulus,modulus), and add a multiple of the modulus
* to it to bring it to range [0,modulus). If sign < 0, the input will also be negated in the		* to it to bring it to range [0,modulus). If sign < 0, the input will also be negated in the
* process. The input must have limbs in range (-2^62,2^62). The output will have limbs in range		* process. The input must have limbs in range (-2^62,2^62). The output will have limbs in range
* [0,2^62). */		* [0,2^62). */
static void secp256k1_modinv64_normalize_62(secp256k1_modinv64_signed62 r, int64_t sign, const secp256k1_modinv64_modinfo modinfo) {		static void secp256k1_modinv64_normalize_62(secp256k1_modinv64_signed62 r, int64_t sign, const secp256k1_modinv64_modinfo modinfo) {
const int64_t M62 = (int64_t)(UINT64_MAX >> 2);		const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
int64_t r0 = r->v[0], r1 = r->v[1], r2 = r->v[2], r3 = r->v[3], r4 = r->v[4];		int64_t r0 = r->v[0], r1 = r->v[1], r2 = r->v[2], r3 = r->v[3], r4 = r->v[4];
int64_t cond_add, cond_negate;		int64_t cond_add, cond_negate;

		#ifdef VERIFY
		/* Verify that all limbs are in range (-2^62,2^62). */
		int i;
		for (i = 0; i < 5; ++i) {
		VERIFY_CHECK(r->v[i] >= -M62);
		VERIFY_CHECK(r->v[i] <= M62);
		}
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(r, &modinfo->modulus, -2) > 0); /* r > -2modulus /
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(r, &modinfo->modulus, 1) < 0); /* r < modulus */
		#endif

/* In a first step, add the modulus if the input is negative, and then negate if requested.		/* In a first step, add the modulus if the input is negative, and then negate if requested.
* This brings r from range (-2*modulus,modulus) to range (-modulus,modulus). As all input		* This brings r from range (-2*modulus,modulus) to range (-modulus,modulus). As all input
* limbs are in range (-2^62,2^62), this cannot overflow an int64_t. Note that the right		* limbs are in range (-2^62,2^62), this cannot overflow an int64_t. Note that the right
* shifts below are signed sign-extending shifts (see assumptions.h for tests that that is		* shifts below are signed sign-extending shifts (see assumptions.h for tests that that is
* indeed the behavior of the right shift operator). */		* indeed the behavior of the right shift operator). */
cond_add = r4 >> 63;		cond_add = r4 >> 63;
r0 += modinfo->modulus.v[0] & cond_add;		r0 += modinfo->modulus.v[0] & cond_add;
r1 += modinfo->modulus.v[1] & cond_add;		r1 += modinfo->modulus.v[1] & cond_add;
Show All 26 Lines	#endif
r3 += r2 >> 62; r2 &= M62;		r3 += r2 >> 62; r2 &= M62;
r4 += r3 >> 62; r3 &= M62;		r4 += r3 >> 62; r3 &= M62;

r->v[0] = r0;		r->v[0] = r0;
r->v[1] = r1;		r->v[1] = r1;
r->v[2] = r2;		r->v[2] = r2;
r->v[3] = r3;		r->v[3] = r3;
r->v[4] = r4;		r->v[4] = r4;

		#ifdef VERIFY
		VERIFY_CHECK(r0 >> 62 == 0);
		VERIFY_CHECK(r1 >> 62 == 0);
		VERIFY_CHECK(r2 >> 62 == 0);
		VERIFY_CHECK(r3 >> 62 == 0);
		VERIFY_CHECK(r4 >> 62 == 0);
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(r, &modinfo->modulus, 0) >= 0); /* r >= 0 */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(r, &modinfo->modulus, 1) < 0); /* r < modulus */
		#endif
}		}

/* Data type for transition matrices (see section 3 of explanation).		/* Data type for transition matrices (see section 3 of explanation).
*		*
* t = [ u v ]		* t = [ u v ]
* [ q r ]		* [ q r ]
*/		*/
typedef struct {		typedef struct {
▲ Show 20 Lines • Show All 43 Lines • ▼ Show 20 Lines	for (i = 0; i < 62; ++i) {
/* Conditionally add g,q,r to f,u,v. */		/* Conditionally add g,q,r to f,u,v. */
f += g & c1;		f += g & c1;
u += q & c1;		u += q & c1;
v += r & c1;		v += r & c1;
/* Shifts */		/* Shifts */
g >>= 1;		g >>= 1;
u <<= 1;		u <<= 1;
v <<= 1;		v <<= 1;
		/* Bounds on eta that follow from the bounds on iteration count (max 1262 divsteps). /
		VERIFY_CHECK(eta >= -745 && eta <= 745);
}		}
/* Return data in t and return value. */		/* Return data in t and return value. */
t->u = (int64_t)u;		t->u = (int64_t)u;
t->v = (int64_t)v;		t->v = (int64_t)v;
t->q = (int64_t)q;		t->q = (int64_t)q;
t->r = (int64_t)r;		t->r = (int64_t)r;
		/* The determinant of t must be a power of two. This guarantees that multiplication with t
		* does not change the gcd of f and g, apart from adding a power-of-2 factor to it (which
		* will be divided out again). As each divstep's individual matrix has determinant 2, the
		* aggregate of 62 of them will have determinant 2^62. */
		VERIFY_CHECK((int128_t)t->u * t->r - (int128_t)t->v * t->q == ((int128_t)1) << 62);
return eta;		return eta;
}		}

/* Compute the transition matrix and eta for 62 divsteps (variable time).		/* Compute the transition matrix and eta for 62 divsteps (variable time).
*		*
* Input: eta: initial eta		* Input: eta: initial eta
* f0: bottom limb of initial f		* f0: bottom limb of initial f
* g0: bottom limb of initial g		* g0: bottom limb of initial g
Show All 34 Lines	for (;;) {
eta -= zeros;		eta -= zeros;
i -= zeros;		i -= zeros;
/* We're done once we've done 62 divsteps. */		/* We're done once we've done 62 divsteps. */
if (i == 0) break;		if (i == 0) break;
VERIFY_CHECK((f & 1) == 1);		VERIFY_CHECK((f & 1) == 1);
VERIFY_CHECK((g & 1) == 1);		VERIFY_CHECK((g & 1) == 1);
VERIFY_CHECK((u * f0 + v * g0) == f << (62 - i));		VERIFY_CHECK((u * f0 + v * g0) == f << (62 - i));
VERIFY_CHECK((q * f0 + r * g0) == g << (62 - i));		VERIFY_CHECK((q * f0 + r * g0) == g << (62 - i));
		/* Bounds on eta that follow from the bounds on iteration count (max 1262 divsteps). /
		VERIFY_CHECK(eta >= -745 && eta <= 745);
/* If eta is negative, negate it and replace f,g with g,-f. */		/* If eta is negative, negate it and replace f,g with g,-f. */
if (eta < 0) {		if (eta < 0) {
uint64_t tmp;		uint64_t tmp;
eta = -eta;		eta = -eta;
tmp = f; f = g; g = -tmp;		tmp = f; f = g; g = -tmp;
tmp = u; u = q; q = -tmp;		tmp = u; u = q; q = -tmp;
tmp = v; v = r; r = -tmp;		tmp = v; v = r; r = -tmp;
}		}
/* eta is now >= 0. In what follows we're going to cancel out the bottom bits of g. No more		/* eta is now >= 0. In what follows we're going to cancel out the bottom bits of g. No more
* than i can be cancelled out (as we'd be done before that point), and no more than eta+1		* than i can be cancelled out (as we'd be done before that point), and no more than eta+1
* can be done as its sign will flip once that happens. */		* can be done as its sign will flip once that happens. */
limit = ((int)eta + 1) > i ? i : ((int)eta + 1);		limit = ((int)eta + 1) > i ? i : ((int)eta + 1);
/* m is a mask for the bottom min(limit, 8) bits (our table only supports 8 bits). */		/* m is a mask for the bottom min(limit, 8) bits (our table only supports 8 bits). */
		VERIFY_CHECK(limit > 0 && limit <= 62);
m = (UINT64_MAX >> (64 - limit)) & 255U;		m = (UINT64_MAX >> (64 - limit)) & 255U;
/* Find what multiple of f must be added to g to cancel its bottom min(limit, 8) bits. */		/* Find what multiple of f must be added to g to cancel its bottom min(limit, 8) bits. */
w = (g * inv256[(f >> 1) & 127]) & m;		w = (g * inv256[(f >> 1) & 127]) & m;
/* Do so. */		/* Do so. */
g += f * w;		g += f * w;
q += u * w;		q += u * w;
r += v * w;		r += v * w;
VERIFY_CHECK((g & m) == 0);		VERIFY_CHECK((g & m) == 0);
}		}
/* Return data in t and return value. */		/* Return data in t and return value. */
t->u = (int64_t)u;		t->u = (int64_t)u;
t->v = (int64_t)v;		t->v = (int64_t)v;
t->q = (int64_t)q;		t->q = (int64_t)q;
t->r = (int64_t)r;		t->r = (int64_t)r;
		/* The determinant of t must be a power of two. This guarantees that multiplication with t
		* does not change the gcd of f and g, apart from adding a power-of-2 factor to it (which
		* will be divided out again). As each divstep's individual matrix has determinant 2, the
		* aggregate of 62 of them will have determinant 2^62. */
		VERIFY_CHECK((int128_t)t->u * t->r - (int128_t)t->v * t->q == ((int128_t)1) << 62);
return eta;		return eta;
}		}

/* Compute (t/2^62) * [d, e] mod modulus, where t is a transition matrix for 62 divsteps.		/* Compute (t/2^62) * [d, e] mod modulus, where t is a transition matrix for 62 divsteps.
*		*
* On input and output, d and e are in range (-2*modulus,modulus). All output limbs will be in range		* On input and output, d and e are in range (-2*modulus,modulus). All output limbs will be in range
* (-2^62,2^62).		* (-2^62,2^62).
*		*
* This implements the update_de function from the explanation.		* This implements the update_de function from the explanation.
*/		*/
static void secp256k1_modinv64_update_de_62(secp256k1_modinv64_signed62 d, secp256k1_modinv64_signed62 e, const secp256k1_modinv64_trans2x2 t, const secp256k1_modinv64_modinfo modinfo) {		static void secp256k1_modinv64_update_de_62(secp256k1_modinv64_signed62 d, secp256k1_modinv64_signed62 e, const secp256k1_modinv64_trans2x2 t, const secp256k1_modinv64_modinfo modinfo) {
const int64_t M62 = (int64_t)(UINT64_MAX >> 2);		const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
const int64_t d0 = d->v[0], d1 = d->v[1], d2 = d->v[2], d3 = d->v[3], d4 = d->v[4];		const int64_t d0 = d->v[0], d1 = d->v[1], d2 = d->v[2], d3 = d->v[3], d4 = d->v[4];
const int64_t e0 = e->v[0], e1 = e->v[1], e2 = e->v[2], e3 = e->v[3], e4 = e->v[4];		const int64_t e0 = e->v[0], e1 = e->v[1], e2 = e->v[2], e3 = e->v[3], e4 = e->v[4];
const int64_t u = t->u, v = t->v, q = t->q, r = t->r;		const int64_t u = t->u, v = t->v, q = t->q, r = t->r;
int64_t md, me, sd, se;		int64_t md, me, sd, se;
int128_t cd, ce;		int128_t cd, ce;
		#ifdef VERIFY
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(d, &modinfo->modulus, -2) > 0); /* d > -2modulus /
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(d, &modinfo->modulus, 1) < 0); /* d < modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(e, &modinfo->modulus, -2) > 0); /* e > -2modulus /
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(e, &modinfo->modulus, 1) < 0); /* e < modulus */
		VERIFY_CHECK((secp256k1_modinv64_abs(u) + secp256k1_modinv64_abs(v)) >= 0); /* \|u\|+\|v\| doesn't overflow */
		VERIFY_CHECK((secp256k1_modinv64_abs(q) + secp256k1_modinv64_abs(r)) >= 0); /* \|q\|+\|r\| doesn't overflow */
		VERIFY_CHECK((secp256k1_modinv64_abs(u) + secp256k1_modinv64_abs(v)) <= M62 + 1); /* \|u\|+\|v\| <= 2^62 */
		VERIFY_CHECK((secp256k1_modinv64_abs(q) + secp256k1_modinv64_abs(r)) <= M62 + 1); /* \|q\|+\|r\| <= 2^62 */
		#endif
/* [md,me] start as zero; plus [u,q] if d is negative; plus [v,r] if e is negative. */		/* [md,me] start as zero; plus [u,q] if d is negative; plus [v,r] if e is negative. */
sd = d4 >> 63;		sd = d4 >> 63;
se = e4 >> 63;		se = e4 >> 63;
md = (u & sd) + (v & se);		md = (u & sd) + (v & se);
me = (q & sd) + (r & se);		me = (q & sd) + (r & se);
/* Begin computing t[d,e]. /		/* Begin computing t[d,e]. /
cd = (int128_t)u * d0 + (int128_t)v * e0;		cd = (int128_t)u * d0 + (int128_t)v * e0;
ce = (int128_t)q * d0 + (int128_t)r * e0;		ce = (int128_t)q * d0 + (int128_t)r * e0;
Show All 32 Lines	#endif
ce += (int128_t)q * d4 + (int128_t)r * e4;		ce += (int128_t)q * d4 + (int128_t)r * e4;
cd += (int128_t)modinfo->modulus.v[4] * md;		cd += (int128_t)modinfo->modulus.v[4] * md;
ce += (int128_t)modinfo->modulus.v[4] * me;		ce += (int128_t)modinfo->modulus.v[4] * me;
d->v[3] = (int64_t)cd & M62; cd >>= 62;		d->v[3] = (int64_t)cd & M62; cd >>= 62;
e->v[3] = (int64_t)ce & M62; ce >>= 62;		e->v[3] = (int64_t)ce & M62; ce >>= 62;
/* What remains is limb 5 of t[d,e]+modulus[md,me]; store it as output limb 4. */		/* What remains is limb 5 of t[d,e]+modulus[md,me]; store it as output limb 4. */
d->v[4] = (int64_t)cd;		d->v[4] = (int64_t)cd;
e->v[4] = (int64_t)ce;		e->v[4] = (int64_t)ce;
		#ifdef VERIFY
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(d, &modinfo->modulus, -2) > 0); /* d > -2modulus /
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(d, &modinfo->modulus, 1) < 0); /* d < modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(e, &modinfo->modulus, -2) > 0); /* e > -2modulus /
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(e, &modinfo->modulus, 1) < 0); /* e < modulus */
		#endif
}		}

/* Compute (t/2^62) * [f, g], where t is a transition matrix for 62 divsteps.		/* Compute (t/2^62) * [f, g], where t is a transition matrix for 62 divsteps.
*		*
* This implements the update_fg function from the explanation.		* This implements the update_fg function from the explanation.
*/		*/
static void secp256k1_modinv64_update_fg_62(secp256k1_modinv64_signed62 f, secp256k1_modinv64_signed62 g, const secp256k1_modinv64_trans2x2 *t) {		static void secp256k1_modinv64_update_fg_62(secp256k1_modinv64_signed62 f, secp256k1_modinv64_signed62 g, const secp256k1_modinv64_trans2x2 *t) {
const int64_t M62 = (int64_t)(UINT64_MAX >> 2);		const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
▲ Show 20 Lines • Show All 45 Lines • ▼ Show 20 Lines	static void secp256k1_modinv64(secp256k1_modinv64_signed62 x, const secp256k1_modinv64_modinfo modinfo) {
/* Do 12 iterations of 62 divsteps each = 744 divsteps. 724 suffices for 256-bit inputs. */		/* Do 12 iterations of 62 divsteps each = 744 divsteps. 724 suffices for 256-bit inputs. */
for (i = 0; i < 12; ++i) {		for (i = 0; i < 12; ++i) {
/* Compute transition matrix and new eta after 62 divsteps. */		/* Compute transition matrix and new eta after 62 divsteps. */
secp256k1_modinv64_trans2x2 t;		secp256k1_modinv64_trans2x2 t;
eta = secp256k1_modinv64_divsteps_62(eta, f.v[0], g.v[0], &t);		eta = secp256k1_modinv64_divsteps_62(eta, f.v[0], g.v[0], &t);
/* Update d,e using that transition matrix. */		/* Update d,e using that transition matrix. */
secp256k1_modinv64_update_de_62(&d, &e, &t, modinfo);		secp256k1_modinv64_update_de_62(&d, &e, &t, modinfo);
/* Update f,g using that transition matrix. */		/* Update f,g using that transition matrix. */
		#ifdef VERIFY
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, 1) <= 0); /* f <= modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &modinfo->modulus, -1) > 0); /* g > -modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &modinfo->modulus, 1) < 0); /* g < modulus */
		#endif
secp256k1_modinv64_update_fg_62(&f, &g, &t);		secp256k1_modinv64_update_fg_62(&f, &g, &t);
		#ifdef VERIFY
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, 1) <= 0); /* f <= modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &modinfo->modulus, -1) > 0); /* g > -modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &modinfo->modulus, 1) < 0); /* g < modulus */
		#endif
}		}

/* At this point sufficient iterations have been performed that g must have reached 0		/* At this point sufficient iterations have been performed that g must have reached 0
* and (if g was not originally 0) f must now equal +/- GCD of the initial f, g		* and (if g was not originally 0) f must now equal +/- GCD of the initial f, g
* values i.e. +/- 1, and d now contains +/- the modular inverse. */		* values i.e. +/- 1, and d now contains +/- the modular inverse. */
VERIFY_CHECK((g.v[0] \| g.v[1] \| g.v[2] \| g.v[3] \| g.v[4]) == 0);		#ifdef VERIFY
		/* g == 0 */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &SECP256K1_SIGNED62_ONE, 0) == 0);
		/* \|f\| == 1, or (x == 0 and d == 0 and \|f\|=modulus) */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &SECP256K1_SIGNED62_ONE, -1) == 0 \|\|
		secp256k1_modinv64_mul_cmp_62(&f, &SECP256K1_SIGNED62_ONE, 1) == 0 \|\|
		(secp256k1_modinv64_mul_cmp_62(x, &SECP256K1_SIGNED62_ONE, 0) == 0 &&
		secp256k1_modinv64_mul_cmp_62(&d, &SECP256K1_SIGNED62_ONE, 0) == 0 &&
		(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, 1) == 0 \|\|
		secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, -1) == 0)));
		#endif

/* Optionally negate d, normalize to [0,modulus), and return it. */		/* Optionally negate d, normalize to [0,modulus), and return it. */
secp256k1_modinv64_normalize_62(&d, f.v[4], modinfo);		secp256k1_modinv64_normalize_62(&d, f.v[4], modinfo);
*x = d;		*x = d;
}		}

/* Compute the inverse of x modulo modinfo->modulus, and replace x with it (variable time). */		/* Compute the inverse of x modulo modinfo->modulus, and replace x with it (variable time). */
static void secp256k1_modinv64_var(secp256k1_modinv64_signed62 x, const secp256k1_modinv64_modinfo modinfo) {		static void secp256k1_modinv64_var(secp256k1_modinv64_signed62 x, const secp256k1_modinv64_modinfo modinfo) {
/* Start with d=0, e=1, f=modulus, g=x, eta=-1. */		/* Start with d=0, e=1, f=modulus, g=x, eta=-1. */
secp256k1_modinv64_signed62 d = {{0, 0, 0, 0, 0}};		secp256k1_modinv64_signed62 d = {{0, 0, 0, 0, 0}};
secp256k1_modinv64_signed62 e = {{1, 0, 0, 0, 0}};		secp256k1_modinv64_signed62 e = {{1, 0, 0, 0, 0}};
secp256k1_modinv64_signed62 f = modinfo->modulus;		secp256k1_modinv64_signed62 f = modinfo->modulus;
secp256k1_modinv64_signed62 g = *x;		secp256k1_modinv64_signed62 g = *x;
int j;		int j;
		#ifdef VERIFY
		int i = 0;
		#endif
int64_t eta = -1;		int64_t eta = -1;
int64_t cond;		int64_t cond;

/* Do iterations of 62 divsteps each until g=0. */		/* Do iterations of 62 divsteps each until g=0. */
while (1) {		while (1) {
/* Compute transition matrix and new eta after 62 divsteps. */		/* Compute transition matrix and new eta after 62 divsteps. */
secp256k1_modinv64_trans2x2 t;		secp256k1_modinv64_trans2x2 t;
eta = secp256k1_modinv64_divsteps_62_var(eta, f.v[0], g.v[0], &t);		eta = secp256k1_modinv64_divsteps_62_var(eta, f.v[0], g.v[0], &t);
/* Update d,e using that transition matrix. */		/* Update d,e using that transition matrix. */
secp256k1_modinv64_update_de_62(&d, &e, &t, modinfo);		secp256k1_modinv64_update_de_62(&d, &e, &t, modinfo);
/* Update f,g using that transition matrix. */		/* Update f,g using that transition matrix. */
		#ifdef VERIFY
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, 1) <= 0); /* f <= modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &modinfo->modulus, -1) > 0); /* g > -modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &modinfo->modulus, 1) < 0); /* g < modulus */
		#endif
secp256k1_modinv64_update_fg_62(&f, &g, &t);		secp256k1_modinv64_update_fg_62(&f, &g, &t);
/* If the bottom limb of g is zero, there is a chance that g=0. */		/* If the bottom limb of g is zero, there is a chance that g=0. */
if (g.v[0] == 0) {		if (g.v[0] == 0) {
cond = 0;		cond = 0;
/* Check if the other limbs are also 0. */		/* Check if the other limbs are also 0. */
for (j = 1; j < 5; ++j) {		for (j = 1; j < 5; ++j) {
cond \|= g.v[j];		cond \|= g.v[j];
}		}
/* If so, we're done. */		/* If so, we're done. */
if (cond == 0) break;		if (cond == 0) break;
}		}
		#ifdef VERIFY
		VERIFY_CHECK(++i < 12); /* We should never need more than 1262 = 744 divsteps /
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, 1) <= 0); /* f <= modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &modinfo->modulus, -1) > 0); /* g > -modulus */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &modinfo->modulus, 1) < 0); /* g < modulus */
		#endif
}		}

/* At this point g is 0 and (if g was not originally 0) f must now equal +/- GCD of		/* At this point g is 0 and (if g was not originally 0) f must now equal +/- GCD of
* the initial f, g values i.e. +/- 1, and d now contains +/- the modular inverse. */		* the initial f, g values i.e. +/- 1, and d now contains +/- the modular inverse. */
		#ifdef VERIFY
		/* g == 0 */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&g, &SECP256K1_SIGNED62_ONE, 0) == 0);
		/* \|f\| == 1, or (x == 0 and d == 0 and \|f\|=modulus) */
		VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, &SECP256K1_SIGNED62_ONE, -1) == 0 \|\|
		secp256k1_modinv64_mul_cmp_62(&f, &SECP256K1_SIGNED62_ONE, 1) == 0 \|\|
		(secp256k1_modinv64_mul_cmp_62(x, &SECP256K1_SIGNED62_ONE, 0) == 0 &&
		secp256k1_modinv64_mul_cmp_62(&d, &SECP256K1_SIGNED62_ONE, 0) == 0 &&
		(secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, 1) == 0 \|\|
		secp256k1_modinv64_mul_cmp_62(&f, &modinfo->modulus, -1) == 0)));
		#endif

/* Optionally negate d, normalize to [0,modulus), and return it. */		/* Optionally negate d, normalize to [0,modulus), and return it. */
secp256k1_modinv64_normalize_62(&d, f.v[4], modinfo);		secp256k1_modinv64_normalize_62(&d, f.v[4], modinfo);
*x = d;		*x = d;
}		}

#endif /* SECP256K1_MODINV64_IMPL_H */		#endif /* SECP256K1_MODINV64_IMPL_H */