Álgebra modular
Alejandro Silvestri
Presentación basada en el libro de W. Stallings, Cryptography and Network Security, 4º ed.
Grupos
y
campos
Grupo
● Es un conjunto discreto y finito de valores, sobre los que se define la suma
○ Cerramiento
■ el resultado de una suma se encuentra dentro del grupo
○ Asociatividad
■ (a+b)+c = a+(b+c)
○ Elemento de identidad
■ 0+a = a+0 = a
○ Inversa
■ a+a’ = a’+a = 0
● Grupo Abeliano
○ Conmutatividad de la adición
Anillo
● Es un grupo abeliano en el que se define el producto
○ Cerramiento
○ Asociatividad
○ Leyes distributivas con la adición
● Anillo conmutativo
○ Conmutatividad del producto
Dominio integral y Campo
●Dominio integral es un anillo conmutativo con:
● Elemento de identidad del producto
● 1.a = a.1 = a
● Divisores no cero
● a.b = 0 => a=0 v b=0
●Campo
● Inversa del producto
● Para todos los elementos excepto el cero
● b=a-1 => a.b = 1
Grupos, anillos y campos
Aritmética
modular
Artimética módulo n
●La aritmética modular es una forma particular de dominio integral
●Opera sobre n enteros, entre 0 y n-1
●La operación a mod b calcula el resto de a/b
●Operaciones módulo n se indican con un (mod n) a la derecha
a = b * c (mod n)
Adición y producto
●La adición se define a partir de la suma aritmética
● c=a+b (mod n) : c=(a+b) mod n
●Resta
● c=a–b (mod n) : c=(a-b) mod n
●El producto se define a partir de la multiplicación aritmética
● c=a.b (mod n) : c=(a.b) mod n
● c=a3 (mod n) : {[(a.a) mod n] . a} mod n
Adición,
producto e
inversas
División
●En álgebra modular no todos los elementos de un dominio tienen inversa
● Los valores sin inversas son los que tienen denominadores comunes con n
● Si todos los elementos tienen inversa, se trata de un campo
● Esto ocurre con n primo
●c=a/b (mod n) ≠> c=(a/b) mod n
a = c.b (mod n)
c = a.b-1 (mod n)
●La inversa no se determina a través de un cálculo directo
● pero sí iterando con el algoritmo de Euclides extendido
Campos de
Galois
Campos de Galois GF(p)
● suma y producto modular
○ el álgebra modular brinda cerramiento y todos los requisitos de un dominio integral
● p es el módulo, y es un número primo
○ valores de 0 a p-1
● todos los valores tienen inversa
○ por eso es un campo
Campos de Galois GF(2)
● Conviene que el módulo sea 2n
● Pero sólo es primo si n=1
● De ahí el interés por los GF(2)
○ La suma modular equivale a XOR
○ El producto equivale a AND
● ¿Cómo extender a n bits?
Aritmética polinomial modular
● a0 + a1x + a2x2 + a3x3 ...
● Suma y producto tradicionales
● Aritmética modular para los coeficientes a, módulo p
○ interesa módulo 2, los coeficientes a son binarios: 0 o 1
● Los polinomios se pueden sumar, multiplicar y dividir
○ pero no tienen cerramiento
○ aritmética modular para el polinomio, módulo f(x), proporciona cerramiento
● El módulo polinomial f(x) forma un campo
○ debe ser relativamente primo a todos los polinomios del grupo
GF(2n)
● Aritmética modular para los coeficientes, módulo 2
○ suma: XOR
○ producto: AND
● Aritmética polinomial
○ el módulo es un polinomio f(x) de grado n
m(x) = x⁸ + x⁴ + x³ + x + 1
○ irreducible (relativamente primo)
○ se demuestra que estos módulos polinomiales logran cerramiento
● Una propiedad random:
○ xn mod f(x) = f(x) - xn
Operaciones matriciales en GF(2n)
● GF(2n) son campos
○ tienen suma, producto e inversa
● Se pueden usar con matrices
○ el producto matricial requiere suma y producto de elementos
○ la inversa de una matriz requiere inversa de elementos
Teoremas y técnicas
●Halla el máximo divisor común (gcd) de dos
Algoritmo de valores
Euclides ●Algoritmo recursivo de recursividad finita
●Se basa en la siguiente propiedad
gcd(a,b) = gcd(b, a mod b) para a>b
●Se reducen sucesivamente las magnitudes de a y
b
●Cuando la iteración devuelve cero, el valor
obtenido en la iteración anterior es el gcd.
EUCLID(A, B)
1.if B = 0 return A
Código del 2.aux = A mod B
algoritmo de 3.A = B
4.B = aux
Euclides 5.goto 1
Algoritmo de Euclides extendido
●Versión extendida del algoritmo de Euclides
●Determina la inversa módulo n de un número
●De manera iterativa por aproximaciones sucesivas
