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?

[Froroth]

supongo que una solución, sería guardar el numero en una cadena, y hacer por ejemplo la suma como la harías en papel, y el resultado lo sigues guardando en chars, mas o menos es una idea

[Gedeon]

He visto que hay una librería GMP que sirve para esto pero no tengo ni idea de como se usa porque utiliza sus propias funciones aunque por los ejemplos que he visto parece bastante complicada de usar.

[posman]

En realidad tu resultado puede necesitar mas de 8 bytes para representarlo?

Una variable declarada de tipo unsigned long long puede tener un valor de hasta 18,446,744,073,709,551,616

Aunque creo que este tipo de datos solo se puede usar en C (no estoy seguro)

[Gedeon]

Si, creo que es probable. No lo se seguro porque aún no se el tamaño del número primo del que debo partir para rsa porque aunque se pueda computar en un pc si lleva demasiado tiempo no es útil osea que habrá que tomar una decisión a ese respecto en su día.

Pero si consideras que para probar el número 19 te puedes necesitar calcular 9^17 pues calcula tu lo que puede pasar cuando necesites probar el número 60.001 y te salga algo como 5^59999

La solución por lo que veo va por instalar una libreria gmp que habilta al compilador a trabajar con números muy grandes a costa de utilizar sus funciones en vez de las estandar de c, lo que pasa es que no encuentro en google ni en los repositorios como instalar eso y tampoco encuentro documentacion al respecto.

gracias por responder

[genuine_carlosV2]

Buenas,

Yo programé el algoritmo de Okamoto-Uchiyama (similar al RSA) en Java. Allí utilicé unas clases llamadas BigInt. Me parece que para C también puedes encontrar funciones que trabajen con estos tipos de números. Estos números, no tienen límite de dígitos (yo hice cálculos con números de más de 700 dígitos (que se dice rápido)).

Suerte y ya contarás como te fue