[pro] Bignum Arithmetic

[Matthew Mondor]

On Sat, 3 Dec 2011 16:00:56 -0700
David McClain <dbm at refined-audiometrics.com> wrote:

> I'm getting more deeply involved in Bignum prime-field and Elliptic Curve computations. Wonder if anyone knows the degree to which the Bignum support in Lisp is enhanced, in the sense that multiple algorithms can be used for, e.g., multiplication, depending on bignum operand sizes. FFT's over integer fields for large numbers, Montgomery multiplication elsewhere, etc.??
> 
> I just reviewed GnuMP docs and saw a fairly sophisticated collection of internal optimizations. Would it pay to migrate to GnuMP for specialized applications?

I unfortunately don't have much number crunching or cryptography
experience using Lisp, but perhaps of help might be that ECL uses
libgmp as part of its math operators implementation, and that there
exists a suite of cryptographic utilities, some of which might be
useful for benchmarking (including RSA which needs bignums), called
Ironclad (http://www.cliki.net/Ironclad).

I'd definitely also try SBCL as a lot of effort is put on its
performance.  I'm unsure if SBCL native bignum performance is worse or
better than C+libgmp, or if the overhead necessary to wrap libgmp
through CFFI would be worth the try.

The C cryptography suite I'm most familiar with (OpenSSL) uses its own
bignum library; it's possible that it might be specially optimized for
the limited use cases of its cryptographic needs and might also be
worth looking at (it does include montgomery multiplication).
-- 
Matt