harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Daniel Fridlender (JIRA)" <j...@apache.org>
Subject [jira] Commented: (HARMONY-1981) [classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
Date Tue, 07 Nov 2006 21:40:52 GMT
    [ http://issues.apache.org/jira/browse/HARMONY-1981?page=comments#action_12447930 ] 
            
Daniel Fridlender commented on HARMONY-1981:
--------------------------------------------

Thanks, Alexey, the patch was applied as expected.

This patch improved the performance of modPow and its cryptographic applications.

Comparing modPow before and after the 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.

As for cryptographic applications, 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 again!


> [classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
> --------------------------------------------------------------------------
>
>                 Key: HARMONY-1981
>                 URL: http://issues.apache.org/jira/browse/HARMONY-1981
>             Project: Harmony
>          Issue Type: Improvement
>            Reporter: Daniel Fridlender
>         Assigned To: Alexey Petrenko
>            Priority: Minor
>         Attachments: pow_modPow.diff
>
>
> The method modPow is important for cryptographic applications.  We optimized it by
> + using sliding windows instead of the simpleminded square-and-multiply technique
> + optimizing Montogomery multiplication when computing squares
> We also optimized pow with a more efficient computation of squares.

-- 
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message