Optimization proposal of BigInteger class


#1

Hello guys !

I have just done some optimization work on the BigInteger class, in order to speed up RSA calculations, and I have been able to get a very good performance increase in multiple cases, around 30-50 times faster for decryption, which can be easily seen in the Juce Demo for example…

So I thought it would be a good idea to share the result, in order to include it in JUCE for real.

In short, what I did there is improving the multiplication method, using 32 bits operations instead of calls to the addition function, and using two new algorithms for the modular exponentiation, with one using Montgomery Multiplication, for doing (a^b % n) with large n. I have added two functions in order to get what I need (the Montgomery Multiplication, and the Extended Euclidean algorithm to get the integers from the Bezout identity).

I have done already numerous tests to be sure that no bug is there, but the code around my functions might be improved a little such as the comments. Otherwise it should be easily useable without any modification.


#2

Hi Ivan, and thanks - that sounds like a great improvement!

If you’re happy for us to use your code, I’ll take a look asap.


#3

Yes go ahead !


#4

Just compared the performance of the cryptography demo in the last commit with JUCE 4.1 JuceDemo, the gain is significant :slight_smile: