The-Fastest-Arithmetic-in-the-World-new

Faster Arithmetic for Cryptography and Computer Algebra

GMP, a widely used and already very fast and highly mature software package for high-speed large integer arithmetic (used in cryptography and computer algebra systems), has been sped up by factors ranging from two to six.

The figure illustrates optimal algorithms for multiplication. The horizontal axis represents the size of the first multiply operand in 64-bit words and the vertical axis represents the size of the other operand. Both axes have logarithmic scale. The colors indicate which multiplication algorithm within GMP gives the best performance, as per the legend to the left.

Challenge overview

Shortly after the start of the Center for Industrial and Applied Mathematics (CIAM) at KTH, Torbjörn Granlund, the principal architect and creator of GMP, was recruited to CIAM. GMP, developed by the company SWOX, was already the most widely used library for large integer arithmetic. However, even though GMP was already very mature and sophisticated, it seemed likely that developing and implementing more mathematically advanced algorithms would result in significant performance improvements.

Implementation of the initiative

Torbjörn Granlund was recruited as a CIAM PhD student under the supervision of Johan Håstad (Professor, theoretical computer science) and Pär Kurlberg (Professor, number theory). So far the project has also involved a postdoc (Niels Möller), and two MSc students who are writing their theses under supervision of the group.

The problem

The major challenge is to develop new algorithms with improved asymptotic runtime, and to implement these in an efficient manner on the many popular CPU architectures currently in use. For further improvements, ever more mathematically sophisticated and subtle algorithms are needed, but implementing these efficiently is then a major challenge. Due to the large ranges of operand sizes, many different algorithms (see figure) are needed for good performance across all situations. To do this, one must exploit all available synergies between computer science and mathematics, and a major challenge is finding and synthesising a very wide spectrum of skills, ranging from advanced mathematics to a high-level ability to overcome subtle engineering challenges.

Results and achievements

Public key cryptography, as well as most computer algebra systems (e.g., Maple, Mathematica, Sage) in widespread use today, are all highly reliant on high-speed integer arithmetic. Since the inception of the project within CIAM, speedups of factors between two and six have been obtained – a quite remarkable result for such a mature project.

Lessons learned and replicability

A key insight is that software engineers, even extremely good ones, reap tremendous benefits from learning more advanced mathematics. Another realisation is the huge value in using more sophisticated models of algorithm runtimes, and then analysing these with traditional mathematical tools (i.e., rather than relying on benchmarks) when developing better algorithms in this setting.

GMP is by now the standard library for arbitrary-precision arithmetic operating on signed integers, rational numbers, and floating point numbers. It is used by several cryptography and computer algebra software packages, such as Mathematica, Maple, and Sage (computer algebra software) and GnuTLS, gcrypt, and nettle (cryptography).

Contact

CIAM
Department of Mathematics
Royal Institute of Technology
SE-100 44 Stockholm, Sweden

GMP
Torbjörn Granlund (tege@nada.kth.se)

Posted: