Bignum Arithmetic

[David McClain]

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-h9Lvq2qNYxl8mnqqp10EyDJtdDapTP/***@public.gmane.org

[Matthew Mondor]

Content preview: On Sat, 3 Dec 2011 16:00:56 -0700 David McClain <dbm-h9Lvq2qNYxl8mnqqp10EyDJtdDapTP/***@public.gmane.org>
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? [...]

Content analysis details: (-1.2 points, 5.0 required)

pts rule name description
---- ---------------------- --------------------------------------------------
-1.2 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain
Archived-At: <http://permalink.gmane.org/gmane.lisp.cl-pro/582>

On Sat, 3 Dec 2011 16:00:56 -0700

Post by David McClain
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).

[István Lakatos]

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.

[Hans Hübner]

Content preview: 2011/12/4 István Lakatos : > 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. [...]


Content analysis details: (-100.7 points, 5.0 required)

pts rule name description
---- ---------------------- --------------------------------------------------
-100 USER_IN_WHITELIST From: address is in the user's white-list
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(hans.huebner[at]gmail.com)
-0.7 RCVD_IN_DNSWL_LOW RBL: Sender listed at http://www.dnswl.org/, low
trust
[209.85.161.179 listed in list.dnswl.org]
-0.0 SPF_PASS SPF: sender matches SPF record
0.0 T_DKIM_INVALID DKIM-Signature header exists but is not valid
X-BeenThere: pro-***@public.gmane.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: Common Lisp Professionals <pro.common-lisp.net>
List-Unsubscribe: <http://lists.common-lisp.net/cgi-bin/mailman/options/pro>,
<mailto:pro-request-***@public.gmane.org?subject=unsubscribe>
List-Archive: <http://lists.common-lisp.net/pipermail/pro>
List-Post: <mailto:pro-***@public.gmane.org>
List-Help: <mailto:pro-request-***@public.gmane.org?subject=help>
List-Subscribe: <http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro>,
<mailto:pro-request-***@public.gmane.org?subject=subscribe>
Errors-To: pro-bounces-***@public.gmane.org
X-Spam-Score: -100.7 (---------------------------------------------------)
X-Spam-Report: Spam detection software, running on the system "tiger.common-lisp.net", has
identified this incoming email as possible spam. The original message
has been attached to this so you can view it (if it isn't spam) or label
similar future email. If you have any questions, see
the administrator of that system for details.

Content preview: 2011/12/4 István Lakatos : > 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. [...]


Content analysis details: (-100.7 points, 5.0 required)

pts rule name description
---- ---------------------- --------------------------------------------------
-0.7 RCVD_IN_DNSWL_LOW RBL: Sender listed at http://www.dnswl.org/, low
trust
[209.85.161.179 listed in list.dnswl.org]
-100 USER_IN_WHITELIST From: address is in the user's white-list
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(hans.huebner[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
0.0 T_DKIM_INVALID DKIM-Signature header exists but is not valid
Archived-At: <http://permalink.gmane.org/gmane.lisp.cl-pro/584>

Post by István Lakatos
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

[Stas Boukarev]

Post by Hans Hübner

Post by István Lakatos
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.

[Steve Haflich]

Post by David McClain

Post by Hans Hübner

Post by István Lakatos
The problem I ran into while trying to implement RSA in Common Lisp for

my

Post by Hans Hübner

Post by István Lakatos
cryptography class was calculating the square root of a bignum (to
demonstrate the Wiener attack on the cipher). There seems to be no

bignum

Post by Hans Hübner

Post by István Lakatos
equivalent to floating point numbers. Are there any libraries that

rectify

Post by Hans Hübner

Post by István Lakatos
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.