Further BigInteger performance improvements

Florian Weimer fw at deneb.enyo.de
Sat Jun 6 06:44:33 UTC 2009

* Alan Eliasen:

> Alan Eliasen wrote:
>>    Note that my optimizations for the pow() function give vastly better
>> performance at even small bit sizes for many operands, as they factor
>> out powers of 2 in the exponent and perform these very rapidly as
>> bit-shifts.
>    Oops.  I mean powers of 2 in the *base*, of course.  The
> exponentiation of these can be done extremely rapidly as left-shifts,
> and the remaining portion of the number can be exponentiated more
> rapidly because it's smaller.

To provide some more background, most of us probably worry about
BigInteger performance in the 512 to 2048 bit range because that's the
range used for RSA cryptography (assuming that Java uses the Chinese
Reminder Theorem optimization for private key operations).

More information about the core-libs-dev mailing list