C++ handling very large integers

Question

Tomek, it sounds like you aren't linking to the BigInteger code correctly. I think you should resolve this problem rather than looking for a new library. I took a look at the source, and BigInteger::BigInteger(int) is most definitely defined. A brief glance indicates that the others are as well.

The link errors you're getting imply that you are either neglecting to compile the BigInteger source, or neglecting to include the resulting object files when you link. Please note that the BigInteger source uses the "cc" extension rather than "cpp", so make sure you are compiling these files as well.

I'd suggest using gmp, it can handle arbitrarily long ints and has decent C++ bindings.

afaik on current hardware/sofware long longs are 64bit, so unsigned can handle numbers up to (2**64)-1 == 18446744073709551615 which is quite a bit smaller than numbers you'd have to deal with with RSA.

To see the size of a long long try this:

#include <stdio.h>

int main(void) {
    printf("%d\n", sizeof(long long));

    return 0;
}

On my machine it returns 8 which means 8 bytes which can store 2^64 values.

For RSA you need a bignum library. The numbers are way too big to fit into a 64-bit long long. I once had a colleague at university who got an assignment to implement RSA including building his own bignum library.

As it happens, Python has a bignum library. Writing bignum handlers is small enough to fit into a computer science assignment, but still has enough gotchas to make it a non-trivial task. His solution was to use the Python library to generate test data to validate his bignum library.

You should be able to get other bignum libraries.

Alternatively, try implementing a prototype in Python and see if it's fast enough.

If you're not implementing RSA as a school assignment or something, then I'd suggest looking at the crypto++ library http://www.cryptopp.com

It's just so easy to implement crypto stuff badly.