harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alexey Petrenko" <alexey.a.petre...@gmail.com>
Subject Re: [classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
Date Tue, 07 Nov 2006 07:07:22 GMT
Daniel,

These results looks really cool!

Could you please add this data or a link to this thread to the
corresponding issue?
And I'll look into the issue and applly it.

SY, Alexey

2006/11/7, Daniel Fridlender <dfridlender@gmail.com>:
> 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