El 4 y 5 de Julio de este año, se celebrará el V Encuentro Andaluz de matemáticas discreta, el cual este año está organizado por el departamento de matemáticas de la Universidad de Cádiz.
Las áreas tratadas durante el encuentro serán:
- Algoritmos y estructuras de datos
- Geometría discreta y combinatoria
- Aplicaciones de la matemática discreta
- Fundamentos teóricos de la matemática discreta
El V Encuentro Andaluz de Matemática Discreta se desarrollará en el Auditorio de Conferencias del nuevo Palacio de Congresos y Exposiciones de La Línea de la Concepción.
(Más información en web de la Universidad de Cádiz)
(Vía Genciencia)
Autor: Fran | Publicado el 8 de Febrero de 2007 | 2 Comentarios
Categorías: Matemáticas discreta, Noticias
Cifrado RSA
El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Len Adleman (la sigla RSA es Rivest Shamir Adleman) en el MIT.
El cifrado RSA es un algoritmo de cifrado de clave pública (o asimétrico) por bloques, que como todos los cifrados de clave pública tiene dos claves: una pública, que se distribuye a los usuarios que quiera el propietario de ella, y otra privada, la cual es guardada en secreto por su propietario. Así cuando se envía un mensaje, el emisor usa la clave pública de cifrado del receptor para cifrar el mensaje y una vez que dicho mensaje llega al receptor, éste se ocupa de descifrarlo usando su clave oculta.
El algoritmo sigue los siguientes pasos:
- Se construye un número “N”, que resulta del producto de dos primos “p” y “q” (normalmente son números muy grandes). Teniendo N = p · q y Φ(N) = (p-1) · (q-1)
- Se selecciona un número “e”,1 < e < Φ(N), tal que MCD (e, Φ(N)) = 1 (”e” y Φ(N) son primos relativos).
- Se calcula el inverso de “e”, denotado por “d”, tal que e · d = 1 (mod Φ(N))
- Con esto se consiguen las claves (e, d), siendo la clave pública (e, N) y la clave privada (d, N).
Una vez tenemos las claves podemos pasar a cifrar/descfirar los mensajes:
- Cifrado: C = Me (mod N) con MCD (M, N) = 1 y M < N
- Descifrado: M = Cd (mod N)
La seguridad de este algoritmo radica en que no hay maneras rápidas conocidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales.
(Más información en Wikipedia)
(Leer el resto del post)
Autor: Fran | Publicado el 20 de Diciembre de 2006 | Comments Off
Categorías: Criptografía, Informática, Matemáticas discreta, Números primos
¿Qué es el cifrado de clave pública?
Un cifrado de clave pública (o asimétrica), es aquel cifrado que se basa en el uso de una pareja de claves, pública y privada, de las cuales una se usa para cifrar y la otra para descifrar.
Ambas claves están relacionadas por una función trampa, suele ser una función matemática. Las claves se calculan usando la función y la inversa de ésta, siendo la función inversa la función trampa al ser muy difícil o imposible de calcular.
-
Función irreversible
x ∈ A, f(x) fácil de calcular
y ∈ f(A), x = f-1(y) difícil de calcular
-
Función trampa
x = f-1(y) Es calculable conociendo la trampa de la función. Pero sin conocer dicha trampa, y = f(x) es unidireccional.
Además la trampa sólo se puede calcular con la clave privada.
(Leer el resto del post)
Autor: Fran | Publicado el 15 de Diciembre de 2006 | 13 Comentarios
Categorías: Criptografía, Informática, Matemáticas discreta
¿Qué es un cifrado por sustitución?
Es aquel cifrado que sustituye cada letra o grupo de letras por otra letra o grupo de letras distinta/s para cifrar el texto en claro.
Los primeros y antiguos métodos de cifrado se basaban en este principio, aunque en aquella época no eran muy robustos ni difíciles de descifrar, pero les resultaban muy útiles.
(Leer el resto del post)
Autor: Fran | Publicado el 23 de Octubre de 2006 | 22 Comentarios
Categorías: Criptografía, Informática, Matemáticas discreta
Ya que he acabado la serie de posts sobre la Teoría de Números Elemental, en este post os voy a poner los enlaces a todos los posts que he hecho sobre este tema, para que podáis tenerlos a mano.
Autor: Fran | Publicado el 6 de Octubre de 2006 | 2 Comentarios
Categorías: Matemáticas discreta
Vamos a terminar ya con la teoría de números elemental, que se me está haciendo demasiado larga.
Números pseudoprimos
Los matemáticos Chinos de la antigüedad creían que:
n primo 2n-1 ≡ 1 (mod (n))
Sin embargo se equivocaron y su condición sólo es válida en un sentido:
n primo => 2n-1 ≡ 1 (mod (n))
A los números que sin ser primos, cumplen la propiedad se les conoce como pseudoprimos.
Teorema pequeño de Fermat
Sea “p” primo y a ∈ Z no divisible por “p”. Entonces,
ap-1 ≡ 1 (mod (p))
Como podéis ver no es más que una mejora de la propiedad de los números pseudoprimos.
(Más información en Wikipedia)
(Leer el resto del post)
Autor: Fran | Publicado el 5 de Octubre de 2006 | 2 Comentarios
Categorías: Aprenda como, Matemáticas discreta, Números enteros, Números primos, Teoremas
Aritmética modular
Con las congruencias podemos establecer un conjunto de operaciones aritméticas, como:
Siendo a, b, c, d ∈ Z y m ∈ N, tales que a ≡ b (mod (m)) y c ≡ d (mod (m)). Entonces,
a + c ≡ b + d (mod (m))
a · c ≡ b · c (mod (m))
(Recordemos que el signo ≡ significa “congruente con” y no es lo mismo que el signo = que significa “igual a”)
A partir de esto, podemos definir las propiedades aritméticas para las sumas de congruencias:
- Propiedad asociativa: a + (b + c) (mod (m)) = (a + b) + c (mod (m))
- Elemento neutro: Existe un elemento 0 ∈ Zm, tal que a + 0 (mod (m)) = a (mod (m))
- Elemento opuesto: Existe un elemento b ∈ Zm, tal que a + b = 0 (recordemos que 0 es el elemento neutro de la suma)
- Propiedad conmutativa: a + b (mod (m)) = b + a (mod (m))
También podemos definir las propiedades aritméticas para el producto de congruencias:
- Propiedad cancelativa: a · c ≡ b · c (mod (m)) y MCD (m, c) = 1, entonces a ≡ b (mod (m))
- Propiedad asociativa: a · (b · c) (mod (m)) = (a · b) · c (mod (m))
- Elemento neutro: Existe un elemento 1 ∈ Zm, tal que a · 1 (mod (m)) = a (mod (m))
- Elemento inverso: Existe un elemento a-1 ∈ Zm para todo a ∈ Zm con MCD (a, m) = 1, tal que a · a-1 = 1 (recordemos que 1 es el elemento neutro del producto)
Además de todas estas propiedades también se cumple la propiedad distributiva: a · (b + c) (mod (m)) = (a · b) + (a · c) (mod (m))
(Más información en la Wikipedia)
Para acabar, os voy a dar unos ejemplos de usos de las congruencias:
- En el DNI: La letra de tu NIF se realiza del siguiente modo: Número DNI (mod 23) y el resultado se pasa a una tabla que relaciona números con letras.
- En la generación de números seudoaleatorios: Los números aleatorios que genera cualquier ordenador se calculan usando una sucesión basada en congruencias: Xn+1 = (a · Xn + c) (mod (m))
- En criptografía: De este tema os hablaré dentro de poco, por ahora saber que las congruencias son la base de toda la criptografía moderna: RSA, El Gamal, …
Autor: Fran | Publicado el 29 de Septiembre de 2006 | 3 Comentarios
Categorías: Matemáticas discreta, Números enteros
Después de mi parón por los examenes de Septiembre, aquí vuelvo para dar la puntilla definitiva a mi serie de posts sobre la teoría de números elemental. Así que aquí viene quizá lo más importante (en mi opinión) de la teoría de números elemental, las congruencias.
¿Qué es una congruencia?
Es una relación de equivalencia (no me quiero meter a explicar que es una relación de equivalencia, por eso os pongo el enlace) que cumple la siguiente propiedad:
Sean a, b ∈ Z, m ∈ N, entonces “a” y “b” son congruentes si:
a mod (m) = b mod (m) ó b - a = K·m (siendo K ∈ Z)
Cuando dos números son congruentes se denota de la siguiente manera:
a ≡ b (mod (m))
Definimos “mod” como la operación módulo, que es el resto de la división euclídea de dos números:
r = a mod (m) a = m·q + r
(Más información en Wikipedia)
Conjuntos cocientes
Como las congruencias son relaciones de equivalencia, se pueden definir para cada elemento del conjunto en el que se da la relación, las clases de equivalencia.
La clase de equivalencia de cualquier elemento “a” perteneciente al conjunto “A”, se define como el conjunto:
[a] = {b ∈ A : aRb} (donde R es la relación de equivalencia)
Aplicando esto a los números enteros y a las congruencias, tenemos que:
a ≡ b (mod (m)) en Z tiene como clases de equivalencia a:
[o] = {…., -2·m, -m, 0, m, 2·m, ….}
[1] = {…., 1-2·m, 1-m, 1, 1+m, 1+2m, ….}
….
[m-1] = {…., -1-m, -1, m-1, 2·m-1, 3·m-1, ….}
(Más información en Wikipedia)
Sabiendo ya que son las clases de equivalencia, podemos pasar a explicar qué son los conjuntos cocientes. El conjunto cociente de A por R, se denota A/R, es el conjunto cuyos elementos son las clases de equivalencia por R de los elementos de A, es decir:
A/R = {[a] : a ∈ A}
Aplicando esto a los números enteros y a las congruencias, tenemos que:
Siendo a ≡ b (mod (m)) y sus clases de equivalencia [0], [1], …, [m-1], su conjunto cociente es:
Zm = {[0], [1], …, [m-1]} [Para los números enteros y las congruencias se denota Zm en lugar de Z/(mod (m))]
(Más información en Wikipedia)
—
Aunque no quería meterme demasiado en el tema de las relaciones de equivalencia, he tenido que explicar que son las clases de equivalencia y conjuntos cocientes sin haber explicado antes nada de relaciones de equivalencia ni de relaciones binarias, lo he hecho lo más sencillo posible y orientado a las congruencias en lugar de a cualquier relación, así que espero que lo entendáis bien, de todos modos ahí tenéis los comentarios para exponer vuestras dudas.
Autor: Fran | Publicado el 21 de Septiembre de 2006 | 6 Comentarios
Categorías: Matemáticas discreta, Números enteros
¿Qué son los primos relativos (o coprimos)?
Sean a, b ∈ Z, se dice que son primos relativos (o coprimos) “a” y “b” si no tienen ningún factor primo en común, es decir, si no tienen otro divisor común más que 1 ó -1, o cumplen que el mcd (a, b) = 1.
(Más información en Wikipedia)
Teorema de la identidad de Bézout
Sean a, b ∈ Z con d=mcd (a, b), entonces existen x, y ∈ Z tales que ax + by = d. En particular si “a” y “b” son primos relativos, entonces existen x, y ∈ Z tales que ax + by = 1.
(Más información en Wikipedia)
Autor: Fran | Publicado el 11 de Agosto de 2006 | 3 Comentarios
Categorías: Matemáticas discreta, Números enteros, Números primos, Teoremas
¿Qué son el máximo común divisor (MCD) y el mínimo común múltiplo (mcm)?
Sean a, b ∈ Z y a, b distintos de cero simultáneamente.
Se dice que un número entero “d” es el Máximo Común Divisor, denotado por mcd (a, b), al mayor de los divisores comunes de “a” y “b”. Si “a” y “b” fueran iguales a cero, se toma por convenio que el mcd (0, 0) sea igual a cero.
Se dice que un número entero “d” es el mínimo común múltiplo, denotado por mcm (a, b), al menor de los enteros que son divisibles tanto por “a” como por “b”.
Así partiendo del teorema fundamental de la aritmética:
mcd (a, b) = p1min (a1, b1) · p2min (a2, b2) · p3min (a3, b3) · … · pnmin (an, bn)
mcm (a, b) = p1max (a1, b1) · p2max (a2, b2) · p3max (a3, b3) · … · pnmax (an, bn)
(Anotación: Puede que haya factores elevados a cero)
Además, mcd (a, b) · mcm (a, b) = a · b
(Más información en Wikipedia: MCD y mcm)
Cálculo del MCD usando el algoritmo de euclídes
El Máximo Común Divisor también se puede calcular usando el algoritmo de euclídes (que viene del siglo III a. C.). Se fundamenta en el siguiente resultado:
Sean a, b ∈ Z, “b” distinto de cero y sea “r” el resto de la división euclídea de “a” por “b”. Entonces:
- Los divisores comunes de “a” y “b” son divisores de “r”.
- Los divisores comunes de “b” y “r” son divisores de “a”.
- mcd (a, b) = mcd (b, r)
- mcd (a, 0) = a
Con estos datos realizamos la división euclídea, de la siguiente forma, siendo r0 = a, r1 = b.
r0 = r1 · q1 + r2 (siendo r2 menor que r1 y mayor o igual a cero)
Se “mueven” las “r’s” hacia la izquierda.
r1 = r2 · q2 + r3 (siendo r3 menor que r2 y mayor o igual a cero)
Se “mueven” las “r’s” hacia la izquierda.
…….
Así seguiríamos “moviendo” las “r’s” hacia la izquierda hasta que en un paso algún resto (rm) sea igual a cero, y por la propiedad mcd (a, b) = mcd (b, r) antes mencionada, tendríamos que mcd (a, b) = mcd (r0, r1) = .. = mcd (rn, 0) = rn.
(Más información en Wikipedia)
Autor: Fran | Publicado el 10 de Agosto de 2006 | 11 Comentarios
Categorías: Matemáticas discreta, Números enteros, Teoremas
