harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Ivanov, Alexey A" <alexey.a.iva...@intel.com>
Subject RE: [classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
Date Tue, 07 Nov 2006 07:37:09 GMT
Good job, Daniel!

--
Alexey A. Ivanov
Intel Middleware Product Division


>-----Original Message-----
>From: Daniel Fridlender [mailto:dfridlender@gmail.com]
>Sent: Tuesday, November 07, 2006 3:22 AM
>To: harmony-dev@incubator.apache.org
>Subject: Re: [classlib][java.math] optimization of BigInteger.modPow
and
>BigInteger.pow
>
>Hi Alexey,
>
>yes we often tested the speed in our several attempts to improve
>performance.  Comparing modPow before and after this new patch gave us
>the following figures:
>
>size         before              after
>16         5.636e+05       6.351e+05
>32         9.727e+04       1.293e+05
>48         3.225e+04       4.623e+04
>64         1.436e+04       2.148e+04
>128               1941                3114
>192                590                   970
>256                252                   420
>384                 75                    127
>512                 32                     55
>
>where the first column shows the size of the arguments in bytes and
>the other two the number of modPow operations per 100 seconds before
>and after the patch.
>
>The method modPow is used in cryptography, we tested several
>cryptographic algorithms obtaining in all cases figures in favor of
>the optimized version (the one in the patch).
>For instance, for RSA key generation we obtained:
>
>size         before           after
>512            3,00             2,06
>1024        20,17            13,58
>2048       280,38          149,48
>
>where the first column shows the length of the key in bits and the
>other two the time in seconds taken to perform 30 iterations of the
>key generation algorithm before and after the patch.
>
>Thanks,
>
>Daniel
>
>On 11/3/06, Alexey Petrenko <alexey.a.petrenko@gmail.com> wrote:
>> Hi, Daniel.
>>
>> Great job!
>>
>> Have you made any performance testing to understand how much the
patch
>> increases the speed of the methods?
>>
>> SY, Alexey
>>
>> 2006/11/3, Daniel Fridlender <dfridlender@gmail.com>:
>> > Hi,
>> >
>> > We have submitted in
http://issues.apache.org/jira/browse/HARMONY-1981
>> > an optimization of BigInteger methods modPow and pow.
>> >
>> > The optimization in modPow was achieved by introducing sliding
windows
>> > instead of the square-and-multiply method.  Some gain was obtained
>> > also from an optimized Montgomery multiplication used for computing
>> > squares.
>> >
>> > The method pow was optimized accordingly by improving the
computation
>> > of squares.
>> >
>> > Thanks
>> >
>> > Daniel
>> >
>>

Mime
View raw message