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.
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.