Use Montgomery Multiplication Algorithm to improve modular exponentiation speed

[Zealot]

Hi:
    I found gcry_mpi_powm in mpi-pow.c still use binary exponentiation
and div method to calculate modular exponentiation, montgomery
multiplication algorithm can do it more faster. Montgomery
multiplication algorithm only use division once, instead it use more
multiplication, so it is faster on platforms which multiplication is
faster than division, and on almost all platforms multiplication is
faster than division.

    I have written a patch using SOS method referred by paper
Analyzing and comparing Montgomery multiplication algorithms
(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.26.3120&rep=rep1&type=pdf).
According to my benchmark result, it is ~25% faster than current
implementation.

before patch:

Algorithm         generate  100*sign  100*verify
------------------------------------------------
RSA 1024 bit          30ms     110ms         0ms
RSA 2048 bit         290ms     690ms        20ms
RSA 3072 bit         850ms    1990ms        20ms
RSA 4096 bit         720ms    4640ms        40ms

after patch

Algorithm         generate  100*sign  100*verify
------------------------------------------------
RSA 1024 bit          10ms      80ms         0ms
RSA 2048 bit         380ms     550ms        10ms
RSA 3072 bit        1690ms    1560ms        20ms
RSA 4096 bit        2600ms    3980ms        40ms

benchmark environment:
Debian amd64
Pentium(R) Dual-Core CPU E5400 @ 2.70GHz

P.S. It is only a prove that montgomery multiplication should be
faster than current implementation, I haven't test the it much, so use
it carefully.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch
Type: application/octet-stream
Size: 13351 bytes
Desc: not available
URL: </pipermail/attachments/20101116/ef120e16/attachment.obj>