Faster table compute in mpn_sec_powm

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


francisco delgado <frdelgado at yahoo.com> 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.)

-- 
Torbjörn
Please encrypt, key id 0xC8601622


More information about the gmp-devel mailing list