mpn_sec_powm

[Niels Möller]

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. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.