Cómo lidiar con números masivos en C

Estoy escribiendo un algoritmo de cifrado RSA en C. No planeo ponerlo en producción en ningún lugar, es principalmente para poder ampliar mi comprensión del cifrado.

¿Cómo trato con los números masivos que genera RSA? Incluso cuando realizo el descifrado con una clave privada relativamente pequeña como 103, todavía tengo el problema de tratar con cosas como esta:

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

¿Cuál es la mejor manera de almacenar un número de ese tamaño? ¿Hay alguna manera de hacerlo utilizando bibliotecas estándar? .

Enfoque equivocado 67^103 mod 143 no necesita calcular primero 67^103 .

Calcule el modulo en un bucle, 1 bit de exponente a la vez.

 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)); } 

Salida

 89