diff options
author | NIIBE Yutaka <gniibe@fsij.org> | 2015-02-11 22:30:02 +0900 |
---|---|---|
committer | NIIBE Yutaka <gniibe@fsij.org> | 2015-02-27 14:03:57 +0900 |
commit | 1fa8cdb933505960d4e4b4842b122d4e06953e88 (patch) | |
tree | 851bc4f84ef4c320000bfd3407a5920d89837b22 /mpi | |
parent | 410d70bad9a650e3837055e36f157894ae49a57d (diff) | |
download | libgcrypt-1fa8cdb933505960d4e4b4842b122d4e06953e88.tar.gz |
mpi: Revise mpi_powm.
* mpi/mpi-pow.c (_gcry_mpi_powm): Rename the table to PRECOMP.
--
The name of precomputed table was b_2i3 which stands for BASE^(2*I+3).
But it's too cryptic, so, it's renamed. Besides, we needed to
distinguish the case of I==0, that was not good. Since it's OK to
increase the size of table by one, it's BASE^(2*I+1), now.
Diffstat (limited to 'mpi')
-rw-r--r-- | mpi/mpi-pow.c | 60 |
1 files changed, 18 insertions, 42 deletions
diff --git a/mpi/mpi-pow.c b/mpi/mpi-pow.c index 0f0947f4..930d3440 100644 --- a/mpi/mpi-pow.c +++ b/mpi/mpi-pow.c @@ -381,7 +381,7 @@ mul_mod (mpi_ptr_t xp, mpi_size_t *xsize_p, *xsize_p = rsize + ssize; } -#define SIZE_B_2I3 ((1 << (5 - 1)) - 1) +#define SIZE_PRECOMP ((1 << (5 - 1))) /**************** * RES = BASE ^ EXPO mod MOD @@ -417,8 +417,8 @@ _gcry_mpi_powm (gcry_mpi_t res, unsigned int bp_nlimbs = 0; unsigned int ep_nlimbs = 0; unsigned int xp_nlimbs = 0; - mpi_ptr_t b_2i3[SIZE_B_2I3]; /* Pre-computed array: BASE^3, ^5, ^7, ... */ - mpi_size_t b_2i3size[SIZE_B_2I3]; + mpi_ptr_t precomp[SIZE_PRECOMP]; /* Pre-computed array: BASE^1, ^3, ^5, ... */ + mpi_size_t precomp_size[SIZE_PRECOMP]; mpi_size_t W; mpi_ptr_t base_u; mpi_size_t base_u_size; @@ -555,31 +555,23 @@ _gcry_mpi_powm (gcry_mpi_t res, memset( &karactx, 0, sizeof karactx ); negative_result = (ep[0] & 1) && bsign; - /* Precompute B_2I3[], BASE^(2 * i + 3), BASE^3, ^5, ^7, ... */ + /* Precompute PRECOMP[], BASE^(2 * i + 1), BASE^1, ^3, ^5, ... */ if (W > 1) /* X := BASE^2 */ mul_mod (xp, &xsize, bp, bsize, bp, bsize, mp, msize, &karactx); - for (i = 0; i < (1 << (W - 1)) - 1; i++) - { /* B_2I3[i] = BASE^(2 * i + 3) */ - if (i == 0) - { - base_u = bp; - base_u_size = bsize; - } - else - { - base_u = b_2i3[i-1]; - base_u_size = b_2i3size[i-1]; - } - + base_u = precomp[0] = mpi_alloc_limb_space (bsize, esec); + base_u_size = precomp_size[0] = bsize; + MPN_COPY (precomp[0], bp, bsize); + for (i = 1; i < (1 << (W - 1)); i++) + { /* PRECOMP[i] = BASE^(2 * i + 1) */ if (xsize >= base_u_size) mul_mod (rp, &rsize, xp, xsize, base_u, base_u_size, mp, msize, &karactx); else mul_mod (rp, &rsize, base_u, base_u_size, xp, xsize, mp, msize, &karactx); - b_2i3[i] = mpi_alloc_limb_space (rsize, esec); - b_2i3size[i] = rsize; - MPN_COPY (b_2i3[i], rp, rsize); + base_u = precomp[i] = mpi_alloc_limb_space (rsize, esec); + base_u_size = precomp_size[i] = rsize; + MPN_COPY (precomp[i], rp, rsize); } i = esize - 1; @@ -667,16 +659,8 @@ _gcry_mpi_powm (gcry_mpi_t res, rsize = xsize; } - if (e0 == 0) - { - base_u = bp; - base_u_size = bsize; - } - else - { - base_u = b_2i3[e0 - 1]; - base_u_size = b_2i3size[e0 -1]; - } + base_u = precomp[e0]; + base_u_size = precomp_size[e0]; mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size, mp, msize, &karactx); @@ -703,16 +687,8 @@ _gcry_mpi_powm (gcry_mpi_t res, if (e != 0) { - if ((e>>1) == 0) - { - base_u = bp; - base_u_size = bsize; - } - else - { - base_u = b_2i3[(e>>1) - 1]; - base_u_size = b_2i3size[(e>>1) -1]; - } + base_u = precomp[(e>>1)]; + base_u_size = precomp_size[(e>>1)]; mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size, mp, msize, &karactx); @@ -761,8 +737,8 @@ _gcry_mpi_powm (gcry_mpi_t res, MPN_NORMALIZE (rp, rsize); _gcry_mpih_release_karatsuba_ctx (&karactx ); - for (i = 0; i < (1 << (W - 1)) - 1; i++) - _gcry_mpi_free_limb_space( b_2i3[i], esec ? b_2i3size[i] : 0 ); + for (i = 0; i < (1 << (W - 1)); i++) + _gcry_mpi_free_limb_space( precomp[i], esec ? precomp_size[i] : 0 ); } /* Fixup for negative results. */ |