Further BigInteger performance improvements (original) (raw)

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

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