[HACK] Numeros primos

[Roman Medina]

On Fri, 14 May 2004 15:35:33 +0100, you wrote:

>Una pregunta, como se puede trabajar en C con numeros en coma flotante
>mayores de 64 bits?

Busca en Google por "grandes números" o "big numbers". Por ejemplo, te
puede valer: freelip, miracl, etc.

Yo usé este último (miracl) para una de las pruebas de Izhal. URL para
Miracl:
http://indigo.ie/~mscott/

Para que veas lo "feo" que es usar este tipo de librerías te pego uno
de los fuentes que hice para Izhal. He borrado lineas a caso hecho,
asi q *espero q no compile*, pero te harás una idea de cómo se
programa con grandes números.

roman at sniff:~/hack/izhal/miracl > cat roman.c
/*
 * Prueba de Capitan a Comandante. Izhal. (c) RoMaNSoFt, 2002
 * [ Compilar: gcc -o roman roman.c -I. miracl.a ]
 */

#include <stdio.h>
#include <miracl.h>

#define MAX 10000

big euclides_ext(big n, big a) {
   int i;
   big c,res, cero, aux;
   big g[MAX],u[MAX],v[MAX];
   
   c=mirvar(0);
   res=mirvar(0);
   cero=mirvar(0);
   for(i=0;i<MAX;i++) {
      g[i]=mirvar(0);
      v[i]=mirvar(0);
   }

   copy(n,g[0]);
   u[0]=mirvar(1);
   zero(u[1]);
   zero(v[0]);
   v[1]=mirvar(1);
   
   i=1;
   while ( (compare(g[i],cero)) != 0 ) {
      copy(g[i-1],c);
      divide(c,g[i],c);
      copy(g[i-1],g[i]);
      divide(g[i+1],g[i+1],g[i]);
      multiply(c,u[i],aux);
      subtract(u[i-1],aux,u[i+1]);
      multiply(1,v[i],aux);
      subtract(v[i-1],aux,v[i+1]);
      i++;
   }

   copy(v[i-1],res);

   return(res);
}


int main()
{
   big msgencr;                         /* mensaje encriptado */
   big e, n;                            /* (e, n) := clave publica */
   big d;
   big p, q, fi, p1, q1, cero;
   big msgdesencr;                      /* mensaje desencriptado */
   
   miracl *mip=mirsys(5000,16);         /* base hexadecimal */

   msgencr=mirvar(0);                   /* inicializamos las variables
*/
   e=mirvar(0);
   n=mirvar(0);
   p=mirvar(0);
   q=mirvar(0);
   d=mirvar(0);
   fi=mirvar(0);
   p1=mirvar(0);
   q1=mirvar(0);
   cero=mirvar(0);
   msgdesencr=mirvar(0);
   
   printf("Texto encriptado: ");        /* leemos los datos de entrada
*/
   innum(msgencr, stdin);
   printf("NumeroE := ");
   innum(e, stdin);
   printf("NumeroP := ");
   innum(p, stdin);
   printf("NumeroQ := ");
   innum(q, stdin);

   multiply(p,q,n);
   printf("\nNumeroN := ");
   otnum(n, stdout);
   
   decr(p,1,p1);
   decr(q,1,q1);
   multiply(p1,q1,fi);
   printf("FI = (p-1)(q-1) = ");
   otnum(fi, stdout);

   printf("\nAplicando algoritmo extendido de Euclides...\n");
   d=euclides_ext(fi,e);
   if (compare(d,cero)==-1)
   printf("NumeroD := ");
   otnum(d, stdout);

   powmod(msgencr,d,n,msgdesencr);
   printf("\nTexto desencriptado: ");   /* visualizamos resultado */
   otnum(msgdesencr, stdout);
}
roman at sniff:~/hack/izhal/miracl > 

 Saludos,
 --Roman

--
PGP Fingerprint:
09BB EFCD 21ED 4E79 25FB  29E1 E47F 8A7D EAD5 6742
[Key ID: 0xEAD56742. Available at KeyServ]