Re: [Boost-bugs] [Boost C++ Libraries] #12022: CRT optimised powm()

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #12022: CRT optimised powm()
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-02-26 15:21:34

#12022: CRT optimised powm()
-------------------------------+----------------------------
  Reporter:  psiha             |      Owner:  johnmaddock
      Type:  Feature Requests  |     Status:  new
 Milestone:  To Be Determined  |  Component:  multiprecision
   Version:  Boost 1.61.0      |   Severity:  Optimization
Resolution:                    |   Keywords:
-------------------------------+----------------------------
Description changed by psiha:

Old description:

> 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
> https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm
> 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)?

New description:

 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

--
-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/12022#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.