Faster const-time inversion
@@ -65,13 +65,13 @@ public static int modOddInverse(int[] m, int[] x, int[] z)
encode30(bits, m, 0, M, 0);
System.arraycopy(M, 0, F, 0, len30);
- int eta = -1;
+ int delta = 0;
int m0Inv32 = inverse32(M[0]);
int maxDivsteps = getMaximumDivsteps(bits);
for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30)
{
- eta = divsteps30(eta, F[0], G[0], t);
+ delta = divsteps30(delta, F[0], G[0], t);
updateDE30(len30, D, E, t, m0Inv32, M);
updateFG30(len30, F, G, t);
}
@@ -303,38 +303,38 @@ private static void decode30(int bits, int[] x, int xOff, int[] z, int zOff)
}
}
- private static int divsteps30(int eta, int f0, int g0, int[] t)
+ private static int divsteps30(int delta, int f0, int g0, int[] t)
{
- int u = 1, v = 0, q = 0, r = 1;
+ int u = 1 << 30, v = 0, q = 0, r = 1 << 30;
int f = f0, g = g0;
for (int i = 0; i < 30; ++i)
{
// assert (f & 1) == 1;
-// assert (u * f0 + v * g0) == f << i;
-// assert (q * f0 + r * g0) == g << i;
+// assert ((u >> (30 - i)) * f0 + (v >> (30 - i)) * g0) == f << i;
+// assert ((q >> (30 - i)) * f0 + (r >> (30 - i)) * g0) == g << i;
- int c1 = eta >> 31;
+ int c1 = delta >> 31;
int c2 = -(g & 1);
- int x = (f ^ c1) - c1;
- int y = (u ^ c1) - c1;
- int z = (v ^ c1) - c1;
+ int x = f ^ c1;
+ int y = u ^ c1;
+ int z = v ^ c1;
- g += x & c2;
- q += y & c2;
- r += z & c2;
+ g -= x & c2;
+ q -= y & c2;
+ r -= z & c2;
- c1 &= c2;
- eta = (eta ^ c1) - (c1 + 1);
+ c2 &= ~c1;
+ delta = (delta ^ c2) - (c2 - 1);
- f += g & c1;
- u += q & c1;
- v += r & c1;
+ f += g & c2;
+ u += q & c2;
+ v += r & c2;
g >>= 1;
- u <<= 1;
- v <<= 1;
+ q >>= 1;
+ r >>= 1;
}
t[0] = u;
@@ -342,7 +342,7 @@ private static int divsteps30(int eta, int f0, int g0, int[] t)
t[2] = q;
t[3] = r;
- return eta;
+ return delta;
}
private static int divsteps30Var(int eta, int f0, int g0, int[] t)
