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?
Dr. David McClain dbm@refined-audiometrics.com
On Sat, 3 Dec 2011 16:00:56 -0700 David McClain dbm@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).
The problem I ran into while trying to implement RSA in Common Lisp for my cryptography class was calculating the square root of a bignum (to demonstrate the Wiener attack on the cipher). There seems to be no bignum equivalent to floating point numbers. Are there any libraries that rectify this issue? I couldn't seem to find any.
2011/12/4 István Lakatos lakatos.isti@gmail.com:
The problem I ran into while trying to implement RSA in Common Lisp for my cryptography class was calculating the square root of a bignum (to demonstrate the Wiener attack on the cipher). There seems to be no bignum equivalent to floating point numbers. Are there any libraries that rectify this issue? I couldn't seem to find any.
Clozure CL implements EXPT and SQRT for bignums.
-Hans
Hans Hübner hans.huebner@gmail.com writes:
2011/12/4 István Lakatos lakatos.isti@gmail.com:
The problem I ran into while trying to implement RSA in Common Lisp for my cryptography class was calculating the square root of a bignum (to demonstrate the Wiener attack on the cipher). There seems to be no bignum equivalent to floating point numbers. Are there any libraries that rectify this issue? I couldn't seem to find any.
Clozure CL implements EXPT and SQRT for bignums.
Every implementation does that. But it may overflow double floats.
There's ISQRT for integer square roots.
On Sat, Dec 3, 2011 at 11:54 PM, Stas Boukarev stassats@gmail.com wrote:
Hans Hübner hans.huebner@gmail.com writes:
2011/12/4 István Lakatos lakatos.isti@gmail.com:
The problem I ran into while trying to implement RSA in Common Lisp for
my
cryptography class was calculating the square root of a bignum (to demonstrate the Wiener attack on the cipher). There seems to be no
bignum
equivalent to floating point numbers. Are there any libraries that
rectify
this issue? I couldn't seem to find any.
Clozure CL implements EXPT and SQRT for bignums.
Every implementation does that. But it may overflow double floats.
This is required by the ANS.
Numberical (*) calculations in ANSI CL usually devolve towards floats (or complex floats) because ANSI CL is intended to be an "industrial strength" programming language that mostly conforms to the usual efficiency assumptions of IEEE float processors. That gets you 64 or 80 or 81 bits, depending. But there is another venerable tradition of numerical (even float) computation that preserves accuracy. See the "bigfloat" capability of Maxima (the public-domain version of Macsyma) open sourced at Sourceforge. Indeed, you might find that the easiest way to write the computations you need would be to do them in Maxima (which is sort-of CL) rather than trying to expropriate the Maxima source code. HTH... . (*) -- This neologism was found on a door label sign at the Yale CS department group for "numerical calculation" some time in the late 1970's. I've alwasy thought that this intentional illiteracy (misspelling) was particularly witty.
-
David McClain -
Hans Hübner -
István Lakatos -
Matthew Mondor -
Stas Boukarev -
Steve Haflich