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)