Definiciones 2 Flashcards
Un grupo es un conjunto G con una operacion binaria ∗ : G × G → G tal que
- (asociativa) x ∗ (y ∗ z) = (x ∗ y) ∗ z para todo x, y, z ∈ G,
- (neutro) existe un elemento e ∈ G tal que e ∗ x = x y x ∗ e = x para todo x ∈ G,
- (inverso) para todo elemento g ∈ G, existe g 0 ∈ G tal que g ∗ g 0 = e y g 0 ∗ g = e.
En general escribimos al grupo como (G, ∗) o (G, ∗, e). Cuando la operacion y neutro son claros escribimos simplemente G.
Orden de G y Grupo abeliano
A la cantidad de elementos del grupo lo llamamos orden de G y lo escribimos |G|. La operación del grupo puede ser conmutativa o no. En el caso en que la operacion sea conmutativa decimos que el grupo es abeliano.
Tabla de Cayley del grupo
Para grupos de orden finito puede resultar conveniente escribir la tabla de multiplicación. A esta tabla se la conoce como Tabla de Cayley del grupo y se construye de la siguiente forma: se colocan los elementos de G arriba de la tabla, y en el mismo orden se los colocan también a la izquierda de la tabla; luego en la entrada correspondiente a la fila del elemento g y a la columna del elemento h colocamos g ∗ h
Observar que un grupo finito G es abeliano si y sólo si su tabla es simétrica (en el sentido de matriz simétrica).
El grupo de enteros módulo n
z̅ = {x ∈ Z : x ≡ z (mód n)}.
Tenemos entonces que (por la propiedad transitiva de la congruencia)
x ≡ z (mód n) si y sólo si x̅ = z̅.
Producto directo de G y K
Subgrupo
Dado un grupo (G,∗,e), un subconjunto H ⊂ G es un subgrupo de G si cumple:
1. (cerrado con la operación) para todo h,h’ ∈ H, h ∗ h’ ∈ H,
2. (neutro) e ∈ H.
3. (cerrado por inversos) si h ∈ H entonces h^(−1) ∈ H.
Escribiremos H < G cuando H es un subgrupo de G.
Claramente, un subgrupo es en particular un grupo (con la misma operación de G).
Potencias de g
Si (G,∗,e) es un grupo definimos las potencias de g como g^0 = e y si n ∈ Z+
g^n = g ∗ g ∗ ··· ∗ g (n veces)
g^(−n) = g^−1 ∗ g^−1 ∗ ··· ∗ g^−1 (n veces)
Orden de un elemento de un grupo
Sea (G,∗,e) un grupo y g ∈ G. Definimos el orden del elemento g (y lo escribiremos o(g)) de la siguiente manera:
* si g^n ≠ e para todo n ∈ Z+, decimos que o(g) = ∞;
* en caso contrario, definimos o(g) = mín{n ∈ Z+ : g^n = e}.
Homomorfismo de grupos
Núcleo e Imágen
Isomorfismo en 2 grupos (G,∗,eG) y (K,★,eK)
Definición 3.9.13. Dados dos grupos (G,∗,eG) y (K,★,eK), una función f : G → K es un isomorfismo si es un homomorfismo biyectivo. Decimos que G y K son isomorfos si existe un isomorfismo f : G → K.
Observaciones 3.9.14. Tenemos que
1. Un homomorfismo f : G → K es un isomorfismo si y sólo si Ker(f) = {eG} e Im(f) = K.
2. Si f : G → K es un isomorfismo, entonces la función f^−1 : K → G también es un isomorfismo.
3. Si G y K son grupos isomorfos, entonces |G| = |K|.
4. Si G y K son grupos isomorfos, entonces G es abeliano si y sólo si K es abeliano.
5. Si f : G → K es un isomorfismo y g ∈ G entonces o(g) = o(f(g)).
Raíz primitiva módulo n
Criptosistema César
E : Zn → Zn, E(x) = x + k (mód n),
D : Zn → Zn, D(y) = y − k (mód n).
Criptosistema César afín
E : Zn → Zn, E(x) = ax + k (mód n).
D : Zn → Zn, D(y) = a’(y − k) (mód n)
donde a0 es un inverso de a módulo n
Pero para poder descifrar el mensaje original la función de cifrado debe ser inyectiva => mcd(a,n) = 1.
Método de cifrado Vigenére
Aquí la clave consiste en una palabra. El método consiste en repetir debajo del texto cifrado la palabra clave, luego sumar cada letra del texto plano, con la letra de la palabra clave que está debajo de ella y reduciendo módulo la cantidad de símbolos
Método Diffie-Helmann de intercambio de clave
Estamos suponiendo que los espías son atacantes pasivos, es decir, tienen la capacidad de acceder a la información, pero no de modificarla
Problema del logaritmo discreto en U(p)
Criptosistema RSA
