The BIGNUM Library for Multiple Precision Arithmetic

The main purpose of this library is to implement fast multiplication. It was used for my diploma thesis [1] and a subsequent paper for the ISSAC conference [2] (local copy), where I benchmark the speed of DKSS multiplication against Schönhage–Strassen multiplication and others. There is some updated information on the slides of my ISSAC talk.

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

BIGNUM is written in C++ and features fast implementations of:

addition,
subtraction,
some logical bit-operations,
grade-school multiplication,
Karatsuba multiplication,
Toom-Cook 3-way multiplication,
Modular FFT-based multiplication,
Schönhage–Strassen multiplication,
DKSS multiplication.

The full source code of arithmetic functions is included, but it won't compile since some header files are missing (for reasons of copyright). I am working on that. However, the arithmetic functions should be usable anyway or can be easily made to work.

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] and [2]. 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].

Source Code

Source code is available on GitLab, or can be downloaded in v7.62 as of 2023-11-29.

Citing

If you use BIGNUM, please cite it as:

@article{Lueders2015Fast,
  title   = {Fast Multiplication of Large Integers: Implementation and Analysis of the {DKSS} Algorithm},
  author  = {Christoph L{\"u}ders},
  journal = {{arXiv} preprint {arXiv}:1503.04955},
  year    = 2015,
  url     = {https://arxiv.org/abs/1503.04955}
}