Big numbers in C

Question

I need help working with very big numbers. According to Windows calc, the exponent 174^55 = 1.6990597648061509725749329578093e+123. How would I store this using C (c99 standard).

int main(){
 long long int x = 174^55; //result is 153
 printf("%lld\n", x);
}

For those curious, it is for a school project where we are implementing the RSA cryptographic algorithm, which deals with exponentiating large numbers with large powers for encryption/decryption.

Answer 1

Normal types in C can usually only store up to 64 bits, so you'll have to store big numbers in an array, for example, and write mathematical operations yourself. But you shouldn't reinvent the wheel here - you could try the GNU Multiple Precision Arithmetic Library for this purpose.

And as the comments already pointed out, the ^ operation is binary XOR. For exponentiation, you will have to use mathematical functions like pow.

Answer 2

If approximation is OK, you can use floating-point (float or double) numbers. And you need pow, not ^, as the commenters said.

However, for cryptography, approximation doesn't work. You need support for arithmetic with very large integers. GMP provides general multiple-precision arithmetic support. Many cryptographic packages will also have such algorithms in their code, either through a third-party library or built-in; PuTTY has a bignum library for large integers, and OpenSSL probably has something similar.

Basic C data types are not enough.

Answer 3

You could store it in an array of integers? Afterall a 64-bit integer is just 2 32-bit integers. A 1024 bit integer could also be seen as 32 32-bit integers ...