Usando números grandes en C

Una duda que surgió hace tiempo en el foro pero a la que no me había enfrentado hasta ahora, es el uso de números grandes en C.

La necesidad de usar números grandes

En mi caso estaba trabajando con algoritmos de cifrado de datos, que usan números enteros de varios miles de bits, lo que implica que son números que no “entran” en ningún tipo de dato entero de C. Sin embargo estos números hay que almacenarlos de alguna manera, para ello surgen los números grandes.

¿Qué son los números grandes?

Básicamente es una implementación de un tipo de dato numérico, que permite trabajar con números de cualquier longitud, donde no hay un numero máximo que podamos almacenar. Para ello trabajan a con memoria dinámica y reescriben las operaciones aritméticas y lógicas.

Bibliotecas de números grandes

Como experiencia personal yo he trabajado con dos:

• OpenSSL que trae un tipo de dato denominado BIGNUM que tiene implementado la mayoría de las operaciones (básicamente las que necesitan ellos para cifrar los datos).
• GMP que traen una implementación completa de números grandes, siendo la biblioteca de este tipo más potente que he encontrado y una de las más usadas.
  

Ejemplo del uso de números grandes

En este caso usamos GMP (para ello hay que instalarlo y compilar con gcc -lgmp).

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

int
main (int argc, char *argv[])
{   
    char num1[] = "9523356807";
                   
    mpz_t entrada,raiz,resto,nAlto,temp1,temp2,temp3;
    
    mpz_init(entrada); //Usan memoria dinamica hay que inicializar siempre
    mpz_init(raiz);
    mpz_init(resto);
    mpz_init(nAlto);
    mpz_init(temp1);
    mpz_init(temp2);
    mpz_init(temp3);
    mpz_set_str(entrada,num1,10);

    //Factorizacion de Fermat
    mpz_sqrtrem(raiz,resto,entrada);
    if(mpz_cmp_ui(resto,0)!=0){ //Entero superior
        mpz_add_ui(nAlto,raiz,1);
    }   

    while(1==1){        
        mpz_mul(temp1,nAlto,nAlto); //Cuadrado
        mpz_sub(temp2,temp1,entrada); //Resto -n
        mpz_sqrtrem(temp1,temp3,temp2); // raiz
        if(mpz_cmp_ui(temp3,0)==0){ //raiz exacta
            break;
        }
        else{
            mpz_add_ui(nAlto,nAlto,1); //= nAlto++
        }
    }

    mpz_add(temp3,nAlto,temp1);
    mpz_sub(temp2,nAlto,temp1);
    gmp_printf("Num: %Zd\nPrimo1 %Zd Primo2 %Zd\n",entrada,temp3,temp2);
    
    mpz_clear(entrada); //Hay que liberar la memoria siempre
    mpz_clear(raiz);
    mpz_clear(resto);
    mpz_clear(nAlto);
    mpz_clear(temp1);
    mpz_clear(temp2);
    mpz_clear(temp3);
    
  return 0;
}

El resultado de la ejecución de este código es lo siguiente: