Opened 7 years ago

Last modified 7 years ago

#12022 new Feature Requests

CRT optimised powm() — at Version 1

Reported by: Domagoj Šarić Owned by: John Maddock
Milestone: To Be Determined Component: multiprecision
Version: Boost 1.61.0 Severity: Optimization
Keywords: Cc:

Description (last modified by Domagoj Šarić)

multiprecision::powm() with unchecked uints is _much_ slower (i.e. I actually perceive the time it takes for the function to return on an 4GHz i5 in release builds) than say the equivalent libtomcrypt/math operation. I'm guessing the major reason for this is the CRT[1] optimisation (or lack thereof in multiprecision). So, can you implement a CRT 'enabled' powm overload (I presume this would also require a function for factoring a large multiprecision uint into to dp, dq, etc. factors)?

[1] https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm http://crypto.stackexchange.com/questions/2575/chinese-remainder-theorem-and-rsa

Change History (1)

comment:1 by Domagoj Šarić, 7 years ago

Description: modified (diff)
Note: See TracTickets for help on using tickets.