Simbolo de Jacobi

El sımbolo de Jacobi es una generalizacion del Simbolo de Legendre y es util para evaluar los sımbolos de Legendre asi como en la definicion de un tipo de numeros llamados pseudoprimos.

CODIGO EN C++

Necesitaremos la siguiente funcion:

son_congruentes(int a,int b,int n)(Funcion que verifica si dos numeros a y b son congruentes modulo n , puedes ver el codigo aqui)

Read more ...

Simbolo de Legendre

Sean p un numero primo e impar y a un numero entero no divisible por p. Entonces el sımbolo de Legendre se define por :



CODIGO EN C++

Necesitaremos las siguientes funciones :

esResiduoCuadratico(int a,int n) (Algoritmo que verifica si un numero a es residuo cuadratico de n, puedes ver el código aqui )

int Legendre(int a , int p)
{
    if(esResiduoCuadratico(a,p))
      return 1;
    return -1;     
}

Read more ...

Residuo Cuadratico

Sean n un numero primo impar y a un numero entero relativamente primo con n,entonces a es un residuo cuadratico de n, sı el mcd(a, n) = 1 y la congruencia tiene solucion.
Podemos deducir que si la congruencia no tiene solucion,entonces se dice que a no es residuo cuadratico de n.

EJEMPLO

Sea n = 11. Entonces para determinar que enteros son residuos cuadraticos de 11, debemos computar los cuadrados de los n´umeros enteros 1, 2, . . . , 10, es decir


Por lo tanto, los residuos cuadraticos son: 1, 3, 4, 5, 9 y los residuos no cuadraticos
son: 2, 6, 7, 8, 10.


CODIGO EN C++

Necesitaremos las siguientes funciones :

alg_euc() (Algoritmo de Euclides, puedes ver el código aqui )

a) Retornar todos los residuos cuadraticos de n

/* funcion que verifica si un elemento esta en el vector*/
bool esta_en(int elemento,vector<int> v)
{
  for(int i=0;i<v.size();i++)
   if(elemento==v.at(i))
     return true;
     
  return false;   
}

/*funcion que retorna todos los residuos cuadraticos de n*/
vector<int> ResiduosCuadraticos(int n)
{
 vector<int> v_rc;
 int mcd,x,a;
 for(int x=1;x<n;x++)
 {
     a=x*x%n;
     if(alg_euc(a,n)==1)
     {
        if(v_rc.size()==0 || !esta_en(a,v_rc))
          v_rc.push_back(a);
     }
 }
 return v_rc;
}

int main(int argc, char *argv[])
{
  vector<int> v=ResiduosCuadraticos(11);
  for(int i=0;i<v.size();i++)
  cout<<v.at(i)<<" ";
  cout<<endl;
    
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

b) Verificar si un numero 'a' es residuo cuadratico de n

bool esResiduoCuadratico(int a,int n)
{
  vector<int> v_rc=ResiduosCuadraticos(n);
  if(esta_en(a,v_rc))
     return true;
  return false; 
}

int main(int argc, char *argv[])
{
    if(esResiduoCuadratico(5,11))
      cout<<"\n SI es Residuo Cuadratico"<<endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

Read more ...

Teorema Chino del Resto

Supongamos que

son enteros coprimos dos a dos. Entonces, para enteros dados

existe un entero x que resuelve el sistema de congruencias simultáneas


Codigo en C++

El siguiente algoritmo necesita las siguientes funciones :

Inverso_Zn() (Inverso en Zn, puedes ver el código aqui)

void chino_del_resto()
{
 int num_ec;
 cout<<"                forma de ecuacion : x = a (mod m)\n\n"; 
 cout<<" ingrese el numero de ecuaciones : ";
 cin>>num_ec;  
 cout<<endl;
 int a[num_ec],m[num_ec],M[num_ec],y[num_ec],x=0;
 
 for(int i=0;i<num_ec;i++)
 {
   cout<<"  a"<<i+1<<" : ";
   cin>>a[i];
 }
 cout<<endl<<endl;
 for(int i=0;i<num_ec;i++)
 {
   cout<<"  m"<<i+1<<" : ";
   cin>>m[i];
 }

  int prod=1;
  // calculamos el producto
  for(int i=0;i<num_ec;i++)
  {
    prod*=m[i];
  }
  for(int i=0;i<num_ec;i++)
  {
  M[i]=prod/m[i];
  }
  for(int i=0;i<num_ec;i++)
  {
   y[i]=Inverso_Zn(M[i]mm[i]);      
  }

  for(int i=0;i<num_ec;i++)
  {
    x+=a[i]*M[i]*y[i];
  }
  x%=prod;
  cout<<"\n  el valor de x es : "<<x<<endl;

}


int main(int argc, char *argv[])
{
    int op;
    cout<<"\n\n         TEOREMA CHINO DEL RESTO\n\n";      
    chino_del_resto();      

    cout<<endl;    
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

Read more ...

Operaciones en Zn

Zn es un conjunto especial de números enteros,el cual se define como el conjunto de enteros dado por {0,1,2,...,n-1}.Como en todo conjunto, en los Zn tambien se pueden efectuar operaciones tales como adicion,multiplicacion y exponenciacion modulo n. Su importancia esta en que es muy usado en los sistemas criptograficos.

ADICION

Sean a, b que pertenecen a Zn, la adicion modular se define por


Codigo en C++

long  Adicion_Zn(int a,int b,int n)
{
 long adicion;
 if(a+b<n)
  adicion=a+b;
 else
  adicion=a+b-n;
 return adicion;
}

MULTIPLICACION

Siendo a, b que pertenecen Zn, la multiplicacion modular se efectua simplemente multiplicandolos como si fueran numeros enteros comunes, para luego coger el resto
de la division de tal producto por n.

Codigo en C++

long Multiplicacion_Zn(int a,int b,int n)
{
 long mult;
 mult=(a*b)%n;
 return mult;
} 

INVERSO MULTIPLICATIVO

Dados los numeros enteros a y n > 0, el inverso multiplicativo de a modulo
n esta dado por el numero entero 'y' que pertenece a Zn, tal que a x y = 1(mod n).
Es importante tener en cuenta que si 'y' existe, entonces es unico, y 'a' es
llamado invertible. Por notacion, el inverso de a se denota por a−1.

Ejemplo

En Z9 = {0, 1, . . . , 8} los elementos invertibles son 1, 2, 4, 5, 7, 8, pues por
ejemplo el inverso de 4 es 7 ya que 4 x 7 = 1(mod 9). Analogamente, el inverso
de 7 es 4, pues 7 x 4 = 1(mod 9).

Codigo en C++

long Inverso_Zn(int a,int n)
{
  long* ptr,array[3];
  ptr=alg_euc_ext(n,a);

  array[0]=*ptr;
  array[1]=*(ptr+1);
  array[2]=*(ptr+2);
  
  if(array[0]!=1)
  return -1;
  else
  {
  if(array[2]<0)
   array[2]+=n;
   return array[2];
  }  
}

Nota : La funcion alg_euc_ext(n,a) (Algoritmo de Euclides Extendido) se encuentra aqui

DIVISION

Sean a, b que pertenecen a Zn. La division de a por b modulo n esta dado por el producto
de a con el inverso de b modulo n.
Podemos notar que la division modular es posible, solamente si b es invertible
modulo n.

Ejemplo

Sea Z9 = {0, 1, . . . , 8} el conjunto de los numeros enteros modulo 9,
entonces considerando que 3 pertenece a Z9 y 4 pertenece a Z9 tenemos que 3 ÷ 4(mod 9) = 3, pues
como el inverso de 4 = 7 entonces tenemos que 3 × 7(mod 9) = 3.

Codigo en C++

int Division_Zn(int a,int b,int n)
{
  b=Inverso_Zn(b,n);
  int division;
  return division=Multiplicacion_Zn(a,b,n);  
}

EXPONENCIACION

La exponenciacion modular es otra operacion basica muy util para la criptografia. El siguiente algoritmo emplea una representacion binaria de un numero entero k de modo que donde cada ki es de la forma
binaria, esto es Ki = {0, 1}.

Ejemplo

Sea ,donde y k=596 .Entonces el algoritmo reporta donde

Codigo en C++

unsigned long long  Exponenciacion_Zn(unsigned long long  a,unsigned long long  k,unsigned long long  n)
{
  // convertimos "k" a binario
   unsigned long long numero=k;

  unsigned long long bin[300];
  unsigned long long  ind=0;
  while(numero>=2)
  {
   bin[ind++]=numero%2;
   numero/=2;      
  }     
  bin[ind]=numero;    
  unsigned long long  tam=ind+1;
 // for(int i=0;i<tam;i++)
 // cout<<bin[i]<<endl;     
  /////////////////////////////   
     
  unsigned long long  b=1;
  if(k==0)
     return b;
  
  unsigned long long  A=a;   
  for(int i=(tam-1);i>=0;i--)
  {
    b=(b*b)%n;
    if(bin[i]==1)
    b=(A*b)%n;   
   // cout<<"b :"<<b<<endl;   
  }

return b;
}

Read more ...

Algoritmo de Euclides

Es un metodo que sirve para hallar el mcd de dos numeros enteros
positivos. El metodo fue creado por el matematico de origen griego llamado
Euclides.

Codigo en C++

int alg_euc(int a,int b) 
{ 
   int max,min,r;
    
  // identificamos el mayor y menor de los numeros
   if(a>=b)
   {max=a;min=b;}
   else
   {max=b;min=a;}
   
   while(min!=0)
   {
    r=max%min;
    max=min;
    min=r;
   }
    return max;
}

Llamamos a nuestra funcion desde nuestro metodo main

int main(int argc, char *argv[])
{
   int a,b,mcd;
   cout<<" Algoritmo de Euclides\n\n";
   
   cout<<" ingrese a : ";cin>>a;
   cout<<"\n ingrese b : ";cin>>b;
        
   mcd=alg_euc(a,b);
   cout<<"\n el mcd de "<<a<<" y "<<b<<" es "<<mcd<<endl<<endl;  
   
    system("PAUSE");
    return EXIT_SUCCESS;    
}

Read more ...

Algoritmo de Euclides Extendido

Es un metodo sistematico que sirve para hallar el mcd de dos numeros enteros
positivos, el cual es expresado como la combinacion lineal de dos numeros enteros
x e y, es decir d = ax + by. (d es el mcd de a y b)

Codigo en C++

El siguiente programa retorna un array con 3 valores : mcd(a,b) , x , y

long* alg_euc_ext(int n1,int n2) // n1 es a y n2 es b
{   
   long array[3],x=0,y=0,d=0,x2 = 1,x1 = 0,y2 = 0,y1 = 1,q = 0, r = 0;
  if(n2==0)
  {
  array[0]=n1;
  array[1]=1; 
  array[2]=0;  
  }
  else
  {
   while(n2>0) 
      {
     q = (n1/n2); 
      r = n1 - q*n2; 
      x = x2-q*x1; 
      y = y2 - q*y1; 
      n1 = n2; 
      n2 = r; 
      x2 = x1; 
      x1 = x; 
      y2 = y1;             
      y1 = y; 
      }
      array[0] = n1;   // mcd (n1,n2)
      array[1] = x2;   // x
      array[2] = y2;   // y
    }
    return array;
}

Read more ...