You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@harmony.apache.org by Daniel Fridlender <df...@gmail.com> on 2006/11/03 18:30:00 UTC
[classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
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
Re: [classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
Posted by Alexey Petrenko <al...@gmail.com>.
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 <df...@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 <al...@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 <df...@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
> > >
> >
>
Re: [classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
Posted by Daniel Fridlender <df...@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 <al...@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 <df...@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
> >
>
Re: [classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
Posted by Alexey Petrenko <al...@gmail.com>.
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 <df...@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
>