You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Daniel Fridlender (JIRA)" <ji...@apache.org> on 2006/10/26 16:49:16 UTC
[jira] Created: (HARMONY-1981) [classlib][java.math] optimization
of BigInteger.modPow and BigInteger.pow
[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
Priority: Minor
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
[jira] Commented: (HARMONY-1981) [classlib][java.math] optimization
of BigInteger.modPow and BigInteger.pow
Posted by "Daniel Fridlender (JIRA)" <ji...@apache.org>.
[ 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
[jira] Closed: (HARMONY-1981) [classlib][java.math] optimization of
BigInteger.modPow and BigInteger.pow
Posted by "Alexey Petrenko (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-1981?page=all ]
Alexey Petrenko closed HARMONY-1981.
------------------------------------
Daniel, thanks for your great job!
> [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
[jira] Updated: (HARMONY-1981) [classlib][java.math] optimization
of BigInteger.modPow and BigInteger.pow
Posted by "Daniel Fridlender (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-1981?page=all ]
Daniel Fridlender updated HARMONY-1981:
---------------------------------------
Attachment: pow_modPow.diff
This patch improves the performance of pow and modPow methods.
It also fixes a bug in BigInteger.toString(int radix) when radix = 6, and removes "commented away" code from BigDecimal.
> [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
> 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
[jira] Resolved: (HARMONY-1981) [classlib][java.math] optimization
of BigInteger.modPow and BigInteger.pow
Posted by "Alexey Petrenko (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-1981?page=all ]
Alexey Petrenko resolved HARMONY-1981.
--------------------------------------
Resolution: Fixed
The patch has been applied.
Daniel, please verify and add your impressive performance comparision.
> [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
[jira] Assigned: (HARMONY-1981) [classlib][java.math] optimization
of BigInteger.modPow and BigInteger.pow
Posted by "Alexey Petrenko (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-1981?page=all ]
Alexey Petrenko reassigned HARMONY-1981:
----------------------------------------
Assignee: Alexey Petrenko
> [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