mpz_powm memory usage vs speed

[Torbjorn Granlund]

I needed to run a Miller-Rabin test for a number of about 150000
bits.  That main computation for that is in mpz_powm with
exponent and mod argument both 150000 bits.

For this computation, mpz_powm allocates more than 70 MB of
temporary memory.  This memory is used for a table of 2048
precomputed powers of my base.

The actual exponentiation then takes (at least) 12 bits from the
exponent per iteration, indexing the precomputed table for the
right value to multiply into the result.  And then it performs 12
squarings.

My question is:

How was the table size vs execution speed determined for this
code?  If I understand correctly, for every extra bit we take
from the exponent per iteration, the table allocation doubles.
But once we take more than a few bits per iteration, the
dominating work will be squarings.

By my reckoning, going from 11 bits to 12 bits saves about 1% of
the execution time, while it needs 36 MB extra space (for this
particular computation).

Time savings table (assuming a squaring cost 2/3 of a full
multiplication):

1=>2    0%              (only half of bits are set)
2=>3   16%
3=>4    9%
4=>5    6%
5=>6    4%
6=>7    3%
7=>8    2%
8=>9    2%

Is my analysis correct?  If it is, I'd suggest that we change
this code to never take more than, say, 9 bits from the exponent.

--
Torbjörn