mpz_powm memory usage vs speed

[Jason Moxham]

On Saturday 16 Nov 2002 11:34 am, Torbjorn Granlund wrote:
> 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=3D>2    0%              (only half of bits are set)
> 2=3D>3   16%
> 3=3D>4    9%
> 4=3D>5    6%
> 5=3D>6    4%
> 6=3D>7    3%
> 7=3D>8    2%
> 8=3D>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.


One way to save a bit a space it to only store the precomputed powers tha=
t are=20
actually used in the exponent , using random 150000 bit exponents and tak=
ing=20
12 bits at a time I can get 2.43% memory saving on average.

Who is to say that 70Mb is a lot of memory ? , it only costs =A34 today.

Perhaps a configure switch ? to restrict those algorithms that can use a =
lot=20
of memory to get a bit of extra speed