mpn_sec_powm
Niels Möller
nisse at lysator.liu.se
Tue Feb 11 21:42:37 UTC 2014
nisse at lysator.liu.se (Niels Möller) writes:
> Maybe one problem is that to make a "fair" comparison between window
> sizes k and k+1, the exponent bit size should be divisible by both k and
> k+1.
I'm testing the below patch. Output from four consecutive runs:
#define POWM_SEC_TABLE 1,29,203,839,1409
#define POWM_SEC_TABLE 1,11,203,399,899
#define POWM_SEC_TABLE 1,5,203,579,1289
#define POWM_SEC_TABLE 1,17,203,839,1409
At least the middle value is consistent ;) It means that we should
increase the window size from 3 to 4 bits when enb > 203. I.e.,
benchmarking was done at 204 = 17*12 bits.
Increasing the window size here saves 17 modular multiplications (on
four limbs) and table lookups (out of 68), at the cost of 8 additional
multiplies in the precomputation, and each of the remaining 51 table
lookups getting twice as expensive. Which sounds more or less sane to
me.
/Niels
 a/tune/tuneup.c Tue Feb 11 22:26:02 2014 +0100
+++ b/tune/tuneup.c Tue Feb 11 22:27:40 2014 +0100
@@ 1868,7 +1868,7 @@ tune_powm_sec (void)
mp_size_t n;
int k, i;
mp_size_t itch;
 mp_bitcnt_t nbits, nbits_next, possible_nbits_cutoff;
+ mp_bitcnt_t nbits, possible_nbits_cutoff;
const int n_max = 3000 / GMP_NUMB_BITS;
const int n_measurements = 5;
mp_ptr rp, bp, ep, mp, tp;
@@ 1914,7 +1914,10 @@ tune_powm_sec (void)
/* For nbits == 1, we should always use k == 1, so no need to tune
that. Starting with nbits == 2 also ensure that nbits always is
larger than the windowsize k+1. */
 for (nbits = 2; nbits <= n_max * GMP_NUMB_BITS; )
+ for (nbits = 2;
+ nbits <= n_max * GMP_NUMB_BITS && k < 10;
+ /* Increment, and round upwards to a multiple of k(k+1) */
+ nbits = k*(k+1)*(1+nbits/(k*(k+1))))
{
n = (nbits  1) / GMP_NUMB_BITS + 1;
@@ 1972,9 +1975,6 @@ tune_powm_sec (void)
}
else
possible_nbits_cutoff = 0;

 nbits_next = nbits * 65 / 64;
 nbits = nbits_next + (nbits_next == nbits);
}
printf ("\n");
TMP_FREE;

Niels Möller. PGPencrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmpdevel
mailing list