What is a convenient base for a bignum library & primality testing algorithm?

Question

Hi,

I am to program the Solovay-Strassen primality test presented in the original paper on RSA.

Additionally I will need to write a small bignum library, and so when searching for a convenient representation for bignum I came across this specification:

struct {
  int sign;
  int size;
  int *tab;
} bignum;

I will also be writing a multiplication routine using the Karatsuba method.

So, for my question:

What base would be convenient to store integer data in the bignum struct?

Note: I am not allowed to use third party or built-in implementations for bignum such as GMP.

Thank you.

Answer 1

A power of 2.

For a simple implementation, probably half the size of a word on your machine, so that you can multiply two digits without overflow. So 65536 or 4294967296. Or possibly half the size of the largest integer type, for the same reason but maybe better performance over all.

But I've never actually implemented such a library: if you're using best known algorithms then you won't be doing school-style long multiplication. Karatsuba multiplication (and whatever other clever tricks you use) might benefit from being done in an integer that's more than twice the size of the digits, I really don't know how the performance works out. If so, then you'd be best off using 256 and 32 bit arithmetic, or 65536 and 64 bit arithmetic.

In any case if your representation is binary, then you can pick and choose larger power-of-two bases as convenient for each operation. For instance, you could treat the data as base 2^16 for multiplication, but base 2^32 for addition. It's all the same thing provided you're careful about endian-ness. I'd probably start with base 2^16 (since that forces me to get the endian-ness right to begin with, while 2^8 wouldn't), and see how I get on - as each operation is optimised, part of the optimisation is to identify the best base.

Using a size which isn't a multiple of bytes is a possibility, but then you have to use the same base for everything, because there are unused bits in the storage in specific places according to the base.

Answer 2

The base you use should be a power of 2. Since it looks like you're going to keep track of sign separately, you can use unsigned ints for storing the numbers themselves. You're going to need the ability to multiply 2 pieces/digits/units of these numbers at a time, so the size must be no more than half the word size you've got available. i.e. on x86 an unsigned int is 32 bits, so you'd want your digits to be not more than 16 bits. You may also use "long long" for the intermediate results of products of unsigned ints. Then you're looking at 2^32 for your base. One last thing to consider is that you may want to add sums of products, which will overflow unless you use fewer bits.

If performance is not a major concern, I'd just use base 256 and call it a day. You may want to use typedefs and defined constants so you can later change these parameters easily.

Answer 3

The integers in the tab array should be unsigned. They should be largest possible size (base) that you can multiply and still represent the product. If your compiler/processor supports 64 bit unsigned long long, for example, you might use uint32_t for the array of "digits." If your compiler/processor can only natively produce 32 bit products, you should use uint16_t.

When you sum two arrays you will need to deal with overflow; in assembly this is easy. In C you may opt to use one less bit (31 or 15) to make the overflow detection easier.

Also consider endianess, and the effect it and the algorithm will have on cache behavior.

Answer 4

You will be doing the following operation a whole lot:

a*b+c*d...;

Either choose 1/4 the largest word size, or 1/2 the largest word size less a bit or two. That would be either 2^16 or 2^30 for 64 bit systems and 2^8 or 2^14 for 32 bit systems. Use the largest size the compiler supports, not the hardware.

If you choose 2^31 on a 64 bit system, that means you can add 4 products without overflow. If you choose 2^30 then you can add 16 products without overflow. The more you can add without overflow, the larger interim blocks you can use.

If you choose 1/4 the word size you will still have a native type so it will be easier to store results back out. You can pretty much ignore overflow too. This will basically make writing code faster and less error prone, and is slightly more memory efficient. I would recommend this unless you like lots of bit manipulation along with your math.

Choosing a larger base will make the big O numbers look better. In practice, while it would probably be faster to have a larger base, it will not be the 4x speed bump that you might hope for.