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;
}