The BIGNUM Library for Multiple Precision Arithmetic

Copyright 2015 Christoph Lüders

Version 7.61, 2015-04-25

This archive contains the source files of BIGNUM, a library for multiple precision arithmetic. So far, the main purpose of this library is to implement fast multiplication. It was used for my diploma thesis [1] and for a subsequent paper for the ISSAC conference [2]. There is some updated information on the slides of my ISSAC talk [3].

The source code is available under the GNU Lesser General Public License, see COPYING.txt and COPYING.LESSER.txt.

BIGNUM features fast implementations of:

addition,

substraction,

some logical bit-operations,

grade-school multiplication,

Karatsuba multiplication,

Toom-Cook 3-way multiplication,

Modular FFT-based multiplication,

Schönhage-Strassen multiplication,

DKSS multiplication.

Right now, the full source code of the arithmetic functions is included, but it does not compile, since some header files are still missing. I am working on that.

Also included is a compiled x64 version of my Lucas-Lehmer Mersenne prime tester in lltest\lltest.exe. It has a lot of overly cryptic options for benchmarking. I used it to make the speed tests for [1], [2] and [3]. Have a look at lltest\main.cpp to find out more.

The code is written for Visual Studio 2012 and is much faster in x64 mode (factor of 4?), but will run in 32-bit mode as well. Detailed technical information can be found in [1, Appendix A] and [2, sec. 3.2].

I can be contacted via email as: chris at cfos dot de

Furthermore, I have a blog: http://wrogn.com

The latest version of BIGNUM is available under: http://wrogn.com/bignum

Click here to download BIGNUM v7.61.

If you use BIGNUM, please cite it like this:

@Electronic{LuedersBignum, Title = {{BIGNUM} Library for Multiple Precision Arithmetic}, Author = {Christoph L{\"u}ders}, HowPublished = {\url{http://www.wrogn.com/bignum}} }

[1] http://wrogn.com/fast-multiplication-of-large-integers-implementation-and-analysis-of-the-dkss-algorithm/ (local copy with slightly better typesetting available here)

[2] http://dx.doi.org/10.1145/2755996.2756643 (local copy available here)

[3] http://www.issac-symposium.org/2015/Slides/Lueders.pdf (local copy available here)