UnixReview.com
October 2006

Book Review: BigNum Math

Reviewed by Cameron Laird

BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic
By Tom St. Denis
O'Reilly, 2006
ISBN: 1-59749-112-8
272 pages

BigNum Math has our children wary — they know Daddy likes books and numbers and calculations, but isn't doing arithmetic going backward? They suspect a trick.

The trick, of course, is that anything can be stretched, expanded, abstracted, or reworked to become entirely more challenging than its original form. Children's games become million-dollar industries when played by sufficiently expert athletes, and, treated with enough panache, peanut butter is a gourmet item.

Or, as in the case at hand, when the additions and multiplications contribute to "Implementing Cryptographic Multiple Precision Arithmetic" (the book's subtitle), the numeric tables and rules we learned in grade school appear in a whole new light.

Humans demand privacy and authentication with sufficient enthusiasm to support a lively market in codes. For our purposes, codes are cryptographic objects; their effective management requires multiplication of numbers like 83567040975197715972768175 and 6089933037757203664490167389076125.

For your virtual private network (VPN) or DVD player to be fast enough to satisfy you as a customer, then, depends crucially on arithmetic that goes beyond the kind taught in elementary school. At one level or another, you rely on "multiple-precision" calculations.

Many languages support arithmetic within definite limits; you can write:

	my_product = factor1 * factor2    

	one_fifth = 1. / 5.
	product = 5. * one_fifth
	difference = product - 1.    

This just won't do, especially not for codes and cyphers. Keys have to be exactly right, and it's not enough to say that the computer "lost a little precision" in unlocking nuclear launch codes or directing space probes hundreds of millions of kilometers distant.

Bignums, or multi-precision, arithmetics, give exact results for operations beyond the ranges supported by conventional hardware and languages. BigNum Math methodically documents the algorithms and source code for one particular implementation, LibTomCrypt.

"Methodically" here is a key word. Computing arithmetic has been documented many times. No other work I know, though, not even Knuth's Volume 2, simultaneously takes such care to detail mundane matters like signs and magnitude differences, while also describing advanced and even deep results from Karatsuba multiplication and modular exponentiation. BigNum Math is unique.

It's quite specialized, both for good and bad. The languages of expression are pseudocode and executable C. The algorithms are almost exclusively for multi-precision integer calculations, not rational, floating-point, or infinite-precision ones.

Let's be clear on these distinctions. A modern CPU might offer 32- or even 64-bit integer arithmetic in its dedicated hardware. For the cryptographic purposes that motivate him, BigNum Math author Tom St. Denis needs a couple of hundreds of bits of full precision. To achieve these, he defines C structures that represent multiple-precision integers. For his purposes, though, the precision is fixed at compile time. Given this context, he makes detailed and subtle measurements that yield tiny but definite performance improvements.

With some effort, St. Denis's ideas and algorithms can be translated to infinite-precision code. Infinite-precision numbers, standard in such languages as Lisp and the latest Python, are variable-length representations, ones whose precisions are determined at the time of execution. Number theorists typically need this sort of arithmetic more than the multiple-precision forms of BigNum Math.

The text is clear and relentlessly dry. Typographical errors are few and inconsequential: a single word missing or out of place. Symbolic expressions have been reviewed carefully; from everything I've noticed, they're entirely correct.

Only the very few programmers who need to implement a multiple-precision arithmetic library will want to read BigNum Math through from cover to cover. There are many more people, though, who might like to have on their shelves a reference that supplies many unique passages. Anyone tuning high- or variable-precision arithmetic, anyone looking to implement specialized primality tests or exponentiation speed-ups, and anyone analyzing cryptography constraints will find in BigNum Math descriptions and results published nowhere else.