Can anyone point me to any books, documentation or whatever that will explain the methods used in routines like bignum for doing sums with 'too-big' numbers.

Try Knuth's The Art of Computer Programming, Volume 2, Seminumerical Algorithms. Most bignum routines work like this. An integer is represented as a polynomial p(x) with coefficients a_0, a_1, ..., a_n, where x is the radix or "base" of the number. The coefficients come from the ring of integers, modulo the base. For instance, if you are using base-2 (x=2), the number 28 could be represented as p(x) = a_4 x^4 + a_3 + x^3 + a_2 x^2 + a_1 x + a_0 where a_4=a_3=a_2=1 and a_1=a_0=0. Each a_n is an element of Z mod x To add two bignums, P(x) and Q(x) simply sum coefficients of like terms like you would with any polynomial addition, with one simple modification. If a_k is the coefficient of the x^k term of P(x), and b_k is the coefficient of the x^k term of Q(x), then the x^k term of P(x)+Q(x) is a_k+b_k+(carry of previous term) mod x. (new carry=(a_k+b_k + previous carry)/x) All this says is, the new term is the sum of the coefficients on the x^k terms, modulo x (because your coefficients can not hold numbers larger than 'x'), plus the carry of the last term. The carry is 1 if a_k+b_k+previous_carry > x. Now you may ask, if our coefficients in our bignum are stored as 32-bit integers, how do I compute the result in C and take into account overflow? Well, add the two numbers together. If the result is less than either of the numbers, an overflow has occured and you must carry (the machine register has 'rolled over'). For multiplication, you can either break a 32-bit number into 2 16-bit chunks and perform 4 16-bit multiplies to get a 64-bit result (using 16x16->32 bit hardware multiplication) or you can use a number of type "long long int" in C and let the compiler do it for you. A short example: let X=123 and Y=789 be bignums represented via the polynomials P(x)=1 x^2 + 2 x + 3 and Q(x)=7 x^2 + 8 x + 9 with x=10. let r_n be the coefficients of the resultant polynomial R(x)=P(x)+Q(x) Start at the least significant term. Carry=0 Now r_0=(a_0 + b_0)+carry mod x, or r_0=9+3 mod 10=2, carry=(9+3)/10=1 r_1=8 + 2 + carry = 11 mod 10 = 1 carry=11/10 = 1 r_2=1+7 + carry = 9 carry = 9 / 10 = 0 So the result is 912. Explicit modulos are only required if you are working in some base other then the machine's natural word size. (otherwise the 'roll over' effect gives you the mod for free) If you are seeking the fastest practical methods of doing multiplication, division, and modular exponentiation, look up information on Karatsuba multiplication, fast reciprocals via Newton's Method, and Fast Integer Squaring combined with exponent shifting. (if you are looking at PGP's source code, PGP does not use the fastest algorithms) -Ray