Cálculo con números grandes

[Gedeon]

Hola

Estoy realizando un código que requiere trabajar con números grandes. El problema es que con cierta frecuencia (la probabilidad de que ocurra es muy grande) los números son tan grandes que exceden la capacidad de la variable y no veo que solución tiene eso.

Por ejemplo.
Pongamos que necesito obtener el valor Pow(12,9) % 19. Este es un caso que se me ha dado y puede dar valores mucho mayores ¿Como hago para calcular eso?

La razón de ese cálculo es para probar la primalidad de un determnado número (que será un número grande). En el test de miller-rabin hay que hacer una serie de cálculos tales que se de esa circunstancia. Para probar he intentado comprobar si el 19 es primo y para ello obtengo que 18=9*2^1. Ese valor 9 según este test será la potencia que tenga que aplicar a un número aleatorio. Si el número obtenido es pequeño (por ejemplo 2) entonces 2^9 será un número pequeño, pero si es un número grande (por ejemplo 18) entonces 18^9 será un número grande.

Y eso para probar el 19. No hablemos ya de probar números de cuatro o cinco dígitos que son lo mínimo que se puede esperar de un número primo requerido para rsa que es lo que al final tengo que hacer.

Pues eso ¿Como hago para calcular Pow(12,9) % 19?