Faster table compute in mpn_sec_powm

Torbjörn Granlund tg at
Tue Mar 20 15:02:22 UTC 2018

francisco delgado <frdelgado at> writes:

  For odd values of i

  Instead of this
  B^(2j+1) = (B^(j-1))*B 

  Shouldn't be this?
  B^(2j+1) = (B^j)^2*B

That's at least mathmatically correct, but this is what I meant:

B^(2j)   = (B^j)^2      (i.e., even values of i)
B^(2j+1) = (B^(2j))*B   (i.e., odd values of i)

as that implies the algorithm.  (For mpn_sec_powm, it will translate to
doing one mpn_sqr_basecase call for even indices, one mpn_mul_basecase
for odd.)

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list