How to deal with massive numbers in C

Question

I am writing an RSA encryption algorithm in C. I do not plan to put it into production anywhere, it is basically just that, I can expand my understanding of encryption.

How can I handle the massive numbers that the RSA generates? Even when decrypting with a relatively small private key like 103, I still have to deal with such things:

67 ^ 103 mod 143 = (1.21816096336830017301951805581 x 10 ^ 188) mod 143

What is the best way to store that amount? Is there a way to do this using standard libraries? .

Answer 1

The wrong approach. 67^103 mod 143 no need to calculate 67^103 .

Calculate modulo in a loop, 1 bit exponent at a time.

 uint32_t powmod(uint32_t base, uint32_t expo, uint32_t mod) { // % mod need only for the cases expo==0, mod<=1 uint32_t y = 1u % mod; while (expo) { if (expo & 1u) { y = ((uint64_t) base * y) % mod; } expo >>= 1u; base = ((uint64_t) base * base) % mod; } return y; } int main(void) { printf("%lu",(unsigned long) powmod(67, 103, 143)); } 

Output

 89