Hola Visitante

Autor Tema: Algoritmo extendido euclides  (Leído 1555 veces)

Berni69

  • Administrator
  • *****
  • Mensajes: 25
    • Ver Perfil
Algoritmo extendido euclides
« en: Octubre 31, 2011, 01:43:24 pm »
Este codigo permite además de calcular el mcd  mediante el algoritmo clasico de euclides, permite saber si en un subconjunto modular de modulo d, tiene inversa. Esto lo he usado para crear un \"rsa\" simple. Indica si tiene inversa o mcd

Código: (c) [Seleccionar]
#include
typedef struct
{
  short type;
   int result;
 } res;
int
euclide (res * result, int f, int d)
{
  int X[4], Y[4], T[4];
  X[0] = 1;
  X[1] = 0;
  X[2] = f;
  Y[0] = 0;
  Y[1] = 1;
  Y[2] = d;
  int Q = 0;
  printf (\"mcd(%d,%d)\\\\n\", f, d);
  printf (\"Q\\\\tX[0]\\\\tX[1]\\\\tX[2]\\\\tY[0]\\\\tY[1]\\\\tY[2]\\\\n\\\\n\");
  while (Y[2] != 0 && Y[2] != 1)
    {
      printf (\"%d\\\\t%d\\\\t%d\\\\t%d\\\\t%d\\\\t%d\\\\t%d\\\\n\\\\n\", Q, X[0], X[1], X[2], Y[0],
       Y[1], Y[2]);
      Q = X[2] / Y[2];
      T[0] = X[0] - Q * Y[0];
      T[1] = X[1] - Q * Y[1];
      T[2] = X[2] - Q * Y[2];
      X[0] = Y[0];
      X[1] = Y[1];
      X[2] = Y[2];
      Y[0] = T[0];
      Y[1] = T[1];
      Y[2] = T[2];
    }
  printf (\"%d\\\\t%d\\\\t%d\\\\t%d\\\\t%d\\\\t%d\\\\t%d\\\\n\\\\n\", Q, X[0], X[1], X[2], Y[0], Y[1],
   Y[2]);
  if (Y[2] == 0)
   
    {
      result->type = 0;
      result->result = X[2];
    }
  if (Y[2] == 1)
   
    {
      result->type = 1;
      int inversa = (Y[1] >= 0) ? Y[1] : f + Y[1];
      result->result = inversa;
    }
} int

main ()
{
 
    //fi de n
  int d = 8;
  int f = 4; // e
  res result;
   euclide (&result, d, f);
   switch (result.type)
    {
    case 1:
      printf (\"Inversa: %d\\\\n\", result.result);
      break;
    case 0:
      printf (\"MCD: %d\\\\n\", result.result);
      break;
    default:
      printf (\"Algo esta mal, no deberias llegar aqui!\");
      break;
    }
}