Matemáticas aplicadas a lacriptografía
Unidad I - Bases matemáticasgenerales
Dr. Luis J. Dominguez Perez
Universidad Don Bosco
Abril 22, 2013
Los seis fundamentales
Hay seis conceptos elementales que necesitan enfatizarse en lasmatemáticas de la criptografía. Sea S un conjunto de elementos, y +,×, ⊙ operadores binarios en S:
• Cerradura: S está cerrado sobre ⊙ si para todo a, b ∈ S, a⊙ b ∈ S
• Asociatividad: S es asociativo sobre ⊙ si para todo a, b, c ∈ S:
a⊙ (b⊙ c) = (a⊙ b)⊙ c.
los elementos en R son asociativos sobre +, y ×.
Matemáticas aplicadas a la criptografía Introducción 2 / 73
. . . los seis fundamentales
• Conmutabilidad: S es conmutativa sobre ⊙ si para todo a, b, c ∈ S:
a⊙ b = b⊙ a
los elementos en R son conmutativos sobre +, y ×.
• Distributiva: S es distributivo sobre + si para todo a, b, c ∈ S:
a× (b+ c) = (a× b) + (a× c)
los elementos en R son distributivos sobre la suma
Matemáticas aplicadas a la criptografía Introducción 3 / 73
. . . los seis fundamentales
• Identidad: El elemento I ∈ S es una identidad sobre + si paratodo a ∈ S:
a+ I = I+ a = a
los elementos en R tienen el 0 como elemento identidad para lasuma, y el 1 para la multiplicación
• Inverso: Sean 0, 1 ∈ S las identidades aditivas y multiplicativas,respectivamente, de S. Un elemento a ∈ S es el inverso aditivo deb ∈ S si a+ b = b+ a = 0. Es el inverso multiplicativo sia× b = b× a = 1. Por ejemplo, 2 es el inverso aditivo de −2 (yviceversa), mientras que 0.5 es su inverso multiplicativo.
Matemáticas aplicadas a la criptografía Introducción 4 / 73
Bases matemáticas generales
• Tipos de números
• Teorema, lema, colorario, proposición
• Teoría de conjuntos, matrices, y vectores
El objetivo de esta unidad es recordar los conceptos generales dematemáticas aplicadas. . .
Matemáticas aplicadas a la criptografía Introducción 5 / 73
Bases matemáticas generales
• Tipos de números
• Teorema, lema, colorario, proposición
• Teoría de conjuntos, matrices, y vectores
El objetivo de esta unidad es recordar los conceptos generales dematemáticas aplicadas. . .
Matemáticas aplicadas a la criptografía Introducción 5 / 73
otros temas a cubrir
. . .se incluyen además los siguientes temas:
• Teoría de probabilidad
• Teoría de la información
• Teoría de la complejidad
• Teoría de números
• Álgebra abstracta
• Campos finitos
De hecho, Teoría de números y Campos finitos tienen su propiasección en este curso.
Matemáticas aplicadas a la criptografía Introducción 6 / 73
otros temas a cubrir
. . .se incluyen además los siguientes temas:
• Teoría de probabilidad
• Teoría de la información
• Teoría de la complejidad
• Teoría de números
• Álgebra abstracta
• Campos finitos
De hecho, Teoría de números y Campos finitos tienen su propiasección en este curso.
Matemáticas aplicadas a la criptografía Introducción 6 / 73
Contenido de la sección 2
Introducción
Tipos de números
Teorema, lema, etc
Teoría de conjuntos
Teoría de probabilidad
Teoría de la información
Teoría de la complejidad
Matemáticas aplicadas a la criptografía Tipos de números 7 / 73
Clases de números
• Naturales
• Enteros
• Reales
• Imaginarios
• Racionales
• Irracionales
Matemáticas aplicadas a la criptografía Tipos de números 8 / 73
Notación
• Z denota el conjunto de números enteros:. . . ,−2,−1, 0, 1, 2, . . .
• Q denota el conjunto de número racionales: ab |a, b ∈ Z, b = 0
• R denota el conjunto de los números reales
• [a, b] denota a todos los enteros x que satisfacen: a ≤ x ≤ b
• ⌊x⌋ denota el entero más grade que es menor o igual a x:⌊5.2⌋ = 5, ⌊−5.2⌋ = 6
• ⌈x⌉ denota el entero más pequeño que es mayor o igual a x:⌈5.2⌉ = 6, ⌈−5.2⌉ = 5
Matemáticas aplicadas a la criptografía Tipos de números 9 / 73
Notación
• Una función o mapeo f : A → B es una regla que asigna a cadaelemento a en A un solo elemento b en B. Si a ∈ A se mapea ab ∈ B, entonces a b se le conoce como la imagen de a, y a la a sele conoce como la preimagen de b, y se escribe como: f(a) = b. Elconjunto A se le conoce como el dominio de f, y al conjunto B sele conoce como codominio de f.
Matemáticas aplicadas a la criptografía Tipos de números 10 / 73
Notación
• Una functión f : A → B es 1−−1 (uno-a-uno) or inyectiva si cadaelemento en B es la imagen de al menos un elemento en A. Por loque f(a1) = f(a2) implica que a1 = a2.
• Una función f : A → B es sobreyectiva si cada b ∈ B es la imagende al menos un elemento a ∈ A.
• Una función f : A → B es biyectiva si es inyectiva y sobreyectiva. Sif es una biyección entre los conjuntos finitos A y B, entonces|A| = |B|. Si f es una biyección entre el conjunto A y sí mismo,entonces f es una permutación de A.
Matemáticas aplicadas a la criptografía Tipos de números 11 / 73
Notación
• Si A es un conjunto finito, entonces |A| denota el número deelementos en A, o cardinalidad de A
• π es la constante matemática: π ≈ 3.14159
• e es la base de los logaritmos naturales: e ≈ 2.71828
Matemáticas aplicadas a la criptografía Tipos de números 12 / 73
Contenido de la sección 3
Introducción
Tipos de números
Teorema, lema, etc
Teoría de conjuntos
Teoría de probabilidad
Teoría de la información
Teoría de la complejidad
Matemáticas aplicadas a la criptografía Teorema, lema, etc 13 / 73
Teorema
DefiniciónUn teorema es una fórmula bien formada que puede ser demostradadentro de un sistema formal.
Para que una afirmación de este tipo pueda ser considerada unteorema, esta debe ser interesante o útil desde un punto de vistamatemático.
Ejemplo: el teorema de Pitágoras
Matemáticas aplicadas a la criptografía Teorema, lema, etc 14 / 73
Teorema
DefiniciónUn teorema es una fórmula bien formada que puede ser demostradadentro de un sistema formal.
Para que una afirmación de este tipo pueda ser considerada unteorema, esta debe ser interesante o útil desde un punto de vistamatemático.
Ejemplo: el teorema de Pitágoras
Matemáticas aplicadas a la criptografía Teorema, lema, etc 14 / 73
Práctica
• Verifique el teorema de Pitágoras. (en Sage)
Matemáticas aplicadas a la criptografía Teorema, lema, etc 15 / 73
Lema
DefiniciónEs una afirmación probada, y que está ligada a un teorema,normalmente como consecuencia.
Teorema de Euclides: Si p es un número primo, y divide al productode dos enteros positivos, entonces p divide al menos a uno de estos.
Lema: Si n es un entero positivo, y divide al producto de dos enterospositivos, y si además, es coprimo de uno de ellos, entonces, divide alotro.
Matemáticas aplicadas a la criptografía Teorema, lema, etc 16 / 73
Lema
DefiniciónEs una afirmación probada, y que está ligada a un teorema,normalmente como consecuencia.
Teorema de Euclides: Si p es un número primo, y divide al productode dos enteros positivos, entonces p divide al menos a uno de estos.
Lema: Si n es un entero positivo, y divide al producto de dos enterospositivos, y si además, es coprimo de uno de ellos, entonces, divide alotro.
Matemáticas aplicadas a la criptografía Teorema, lema, etc 16 / 73
Lema
DefiniciónEs una afirmación probada, y que está ligada a un teorema,normalmente como consecuencia.
Teorema de Euclides: Si p es un número primo, y divide al productode dos enteros positivos, entonces p divide al menos a uno de estos.
Lema: Si n es un entero positivo, y divide al producto de dos enterospositivos, y si además, es coprimo de uno de ellos, entonces, divide alotro.
Matemáticas aplicadas a la criptografía Teorema, lema, etc 16 / 73
Práctica
• Verifique el teorema de Euclides, y su lema. (en Sage)
Matemáticas aplicadas a la criptografía Teorema, lema, etc 17 / 73
Corolario
DefiniciónDesignar la evidencia de un teorema o de una definición yademostrados, sin necesidad de invertir esfuerzo adicional en sudemostración
Esto es, es una afirmación tan evidente, que no necesita comprobación
Ejemplo:
• La suma de los ángulos interiores de un triángulo es igual a 180°
• En un triángulo rectángulo la suma de los dos ángulos contiguosa la hipotenusa es igual a 90°.
Matemáticas aplicadas a la criptografía Teorema, lema, etc 18 / 73
Corolario
DefiniciónDesignar la evidencia de un teorema o de una definición yademostrados, sin necesidad de invertir esfuerzo adicional en sudemostración
Esto es, es una afirmación tan evidente, que no necesita comprobación
Ejemplo:
• La suma de los ángulos interiores de un triángulo es igual a 180°
• En un triángulo rectángulo la suma de los dos ángulos contiguosa la hipotenusa es igual a 90°.
Matemáticas aplicadas a la criptografía Teorema, lema, etc 18 / 73
Corolario
DefiniciónDesignar la evidencia de un teorema o de una definición yademostrados, sin necesidad de invertir esfuerzo adicional en sudemostración
Esto es, es una afirmación tan evidente, que no necesita comprobación
Ejemplo:
• La suma de los ángulos interiores de un triángulo es igual a 180°
• En un triángulo rectángulo la suma de los dos ángulos contiguosa la hipotenusa es igual a 90°.
Matemáticas aplicadas a la criptografía Teorema, lema, etc 18 / 73
Otros
ProposiciónUna sentencia portadora de valores de verdad
Ejemplo: Está lloviendo (válida sólo si está lloviendo)
ConjeturaAfirmación que se supone cierta, pero que no ha sido probada nirefutada hasta la fecha
Ejemplo: P = NP
Matemáticas aplicadas a la criptografía Teorema, lema, etc 19 / 73
otros
PostuladoUn postulado es una proposición no evidente por sí misma, nidemostrada, pero que se acepta ya que no existe otro principio al quepueda ser referida.
Ejemplo: Los postulados de Euclides, que dieron nacimiento a lageometría euclidiana. Cuando algunos de sus postulados fueroncuestionados, nació la geometría no-euclidiana, la hiperbólica, etc.
Matemáticas aplicadas a la criptografía Teorema, lema, etc 20 / 73
Contenido de la sección 4
Introducción
Tipos de números
Teorema, lema, etc
Teoría de conjuntos
Teoría de probabilidad
Teoría de la información
Teoría de la complejidad
Matemáticas aplicadas a la criptografía Teoría de conjuntos 21 / 73
Conjuntos
DefiniciónEs una colección bien definida de objetos
• Estos objetos se llaman elementos, y se dice que son miembros delconjunto.
• Se escribe:• a ∈ A, si a es un elemento de A• b ∈ A, si b no es un elemento de A
• Para enumerar los elementos de un conjunto, se escribe:• A = 1, 2, 3, 4, 5• A = x|x es un entero, y 1 ≤ x ≤ 5
• La cardinalidad o tamaño de un conjunto se denota por |A|
Matemáticas aplicadas a la criptografía Teoría de conjuntos 22 / 73
Subconjuntos
DefiniciónSi C, D son conjuntos del universo U , se dice que C es un subconjuntode D (escrito así: C ⊆ D, o C ⊃ C), si cada elemento de C es unelemento de D.
Si D contiene al menos un elemento que no está en C, entonces C esun subconjunto propio de D: C ⊂ D, o D ⊃ C.
Matemáticas aplicadas a la criptografía Teoría de conjuntos 23 / 73
Reglas de pertenencia
Para cualquier conjunto C, D, en el universo U :
• C ⊆ D ⇔ ∀x[x ∈ C ⇒ x ∈ D]
• C ⊂ D ⇒ C ⊆ D
cuando C, D son finitos:
• C ⊆ D ⇒ |C| ≤ |D|• C ⊂ D ⇒ |C| < |D|
Matemáticas aplicadas a la criptografía Teoría de conjuntos 24 / 73
Igualdad y transitividad entre conjuntos
DefiniciónPara un universo dado U , los conjuntos C y D (contenidos en U ) soniguales (denotado como C = D), cuando C ⊆ D, y D ⊆ C.
TeoremaSean A, B,C ⊆ U :
• (A ⊆ B ∧ B ⊆ C) ⇒ A ⊆ C
• (A ⊂ B ∧ B ⊆ C) ⇒ A ⊂ C
• (A ⊆ B ∧ B ⊂ C) ⇒ A ⊂ C
• (A ⊂ B ∧ B ⊂ C) ⇒ A ⊂ C
Matemáticas aplicadas a la criptografía Teoría de conjuntos 25 / 73
Conjutos varcíos y potencia
DefiniciónEl conjunto vacío o nulo es el (único) conjunto que no contieneelementos. Se denota: ∅ o .
TeoremaPara cualquier universo U , sea A ⊆ U . Entonces ∅ ⊆ A, y si A = ∅,entonces ∅ ⊂ A.
DefiniciónSi A es un conjunto del universo U , el conjunto potencia, que se denotaP(A) es el conjunto de todos los subconjuntos de A.
TeoremaPara cualquier conjunto finito A con |A| = n ≥ 0, |P(A)| = 2n
Matemáticas aplicadas a la criptografía Teoría de conjuntos 26 / 73
Operaciones de conjuntos
Definiciones (entre los conjuntos A y B):
• Unión: A ∪ B = x|x ∈ A ∨ x ∈ B• Intersección: A ∩ B = x|x ∈ A ∧ x ∈ B• Diferencia simétrica: A B = x|x ∈ A ∪ B ∧ x ∈ A ∩ B
Un resultado importante es que: A ∩ B ⊆ A ⊆ A ∪ B
Matemáticas aplicadas a la criptografía Teoría de conjuntos 27 / 73
Definiciones
DefiniciónSean S, T ⊆ U , los conjuntos S y T son disjuntos o mutuamente disjuntossi S ∩ T = ∅
TeoremaSi S, T ⊆ U , entonces S y T son disjuntos sí, y sólo sí S ∪ T = S T
Matemáticas aplicadas a la criptografía Teoría de conjuntos 28 / 73
. . . más definiciones
Definiciones
• Para un conjunto A ⊂ U , el complemento de A, que se denota conU − A, o A, está dado por x|x ∈ U ∧ x ∈ A
• Para A, B ⊆ U , el complemento (relativo) de A en B, que se denotacon B− A está dado por x|x ∈ B ∧ x ∈ A
TeoremaA ⊆ B ⇔ A ∩ B = A ⇔ A ∪ B = B ⇔ B ⊆ A
Matemáticas aplicadas a la criptografía Teoría de conjuntos 29 / 73
Propiedades de la teoría de conjuntos
¯A = A Ley del doble complemento
A ∪ B = A ∩ BLeyes de De Morgan
A ∩ B = A ∪ B
A ∪ B = B ∪ APropiedades conmutativas
A ∩ B = B ∩ A
A ∪ (B ∪ C) = (A ∪ B) ∪ CPropiedades asociativas
A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)Propiedades distributivas
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Matemáticas aplicadas a la criptografía Teoría de conjuntos 30 / 73
más propiedades de la teoría de conjuntos
A ∪ A = APropiedades idempotentes
A ∩ A = A
A ∪ ∅ = APropiedades del neutro
A ∩ U = A
A ∪ A = UPropiedades del investo
A ∩ A = ∅
A ∪ U = UPropiedades de dominación
A ∩ ∅ = ∅
A ∪ (A ∩ B) = APropiedades de absorción
A ∩ (A ∪ B) = A
Matemáticas aplicadas a la criptografía Teoría de conjuntos 31 / 73
Dualidad
DefiniciónSea s una proposición (general) que trata de la igualdad de dosexpresiones de conjuntos. cada una de estas expresiones puedecontener una o más ocurrencias de conjuntos (como A, A, B, etc.), unao más ocurrencias de ∅ y U , y solamente los símbolos de lasoperaciones de conjuntos ∪ y ∩. El dual de s, denotado sd, se obtienede s al reemplazar:
• cada ocurrencia de ∅ y U (en s) por Uy ∅, respectivamente
• cada ocurrencia de ∪ e ∩ (en s) por ∩ y ∪ respectivamente.
Matemáticas aplicadas a la criptografía Teoría de conjuntos 32 / 73
Principio de dualidad
TeoremaEl principio de dualidad. Sea s un teorema relativo a la igualdad de dosexpresiones con conjuntos (como en la definición anterior). Entoncessd, el dual de s, es también un teorema.
Matemáticas aplicadas a la criptografía Teoría de conjuntos 33 / 73
Contenido de la sección 5
Introducción
Tipos de números
Teorema, lema, etc
Teoría de conjuntos
Teoría de probabilidad
Teoría de la información
Teoría de la complejidad
Matemáticas aplicadas a la criptografía Teoría de probabilidad 34 / 73
Definiciones
DefiniciónUn experimento es un procedimientos que produce un conjunto dadode resultados. Losposibles resultados individuales se llaman eventossimples. El conjunto de todos los posibles resultados es el espacio demuestra.
DefiniciónLa distribución de probabilidad P en S es una secuencia de númerosp1, p2, . . . , pn no-negativos que suman 1. El número pi se interpretacomo la probabilidad de si de ser el resultado de un experimento.
Matemáticas aplicadas a la criptografía Teoría de probabilidad 35 / 73
definiciones
DefiniciónUn evento E es un subconjunto del espacio de muestra S. Laprobabilidad de que el evento E ocurra, P(E), es la suma de lasprobabilidades pi de todos los eventos simples si que pertenecen a E.Si si ∈ S, entonces P(si) se denota como P(si).
DefiniciónSi E es un evento, el evento complementario es el conjunto de loseventos simples que no pertenecen a E, denotado como E.
Matemáticas aplicadas a la criptografía Teoría de probabilidad 36 / 73
definiciones
ObservaciónSean E ⊆ S un evento:
• 0 ≤ P(E) ≤ 1. Adicionalmente, P(S) = 1, y P(∅) = 0
• P(E) = 1− P(E)
• Si los resultados en S tienen igual probabilidad de suceder,entonces P(E) = |E|
|S| .
DefiniciónDos eventos E1 y E2 se llaman mutuamente exclusivos si P(E1 ∩ E2) = 0.Esto es, si la occurrencia de uno de los eventos excluye la posibilidadde que el otro ocurra.
Matemáticas aplicadas a la criptografía Teoría de probabilidad 37 / 73
Definiciones
ObservaciónSean E1 y E2 dos eventos
• Si E1 ⊆ E2, entonces P(E1) ≤ P(E2)
• P(E1 ∪ E2) + P(E1 ∩ E2) = P(E1) + P(E2). Por lo que, si E1, y E2 sonmutuamente exclusivos, entonces P(E1 ∪ E2) = P(E1) + P(E2)
Matemáticas aplicadas a la criptografía Teoría de probabilidad 38 / 73
Probabilidad condicional
DefiniciónSean E1 y E2 dos eventos con P(E2) > 0. La probabilidad condicional deE1 dado E2, denotada como P(E1|E2), es:
P(E1|E2) =P(E1 ∩ E2)
E2
En otras palabras, P(E1|E2) mide la probabilidad de que ocurra elevento E1, una vez que E2 ha ocurrido.
Matemáticas aplicadas a la criptografía Teoría de probabilidad 39 / 73
Probabilidad condicional
DefiniciónLos eventos E1 y E2 son independientes si P(E1 ∩ E2) = P(E1)P(E2)
Observe que si E1 y E2 so independientes, entonces P(E1|E2) = P(E1), yP(E2|E1) = P(E2). Esto es, que la ocurrencia de un evento no influye enla probabilidad de ocurrir de el otro.
Teorema de BayesSi E1 y E2 son eventos con P(E2) > 0, entonces:
P(E1|E2) =P(E1)P(E2|P(E1)
P(E2)
Matemáticas aplicadas a la criptografía Teoría de probabilidad 40 / 73
Distrubución binomial
DefiniciónSea n y k enteros no negativos. El coeficiente binomial
(nk
)es el
número de diferentes maneras de escoger k objetos diferentes de unconjunto de n objetos diferentes, en donde el orden no es importante
Propiedades de los coeficientes binomialesSean n y k enteros no negativos:
•(nk
)= n!
k!(n−k)!
•(nk
)=
( nn−k
)•(n+1k+1
)=
(nk
)+
( nk+1
)Use Sage para verificar estos valores
Matemáticas aplicadas a la criptografía Teoría de probabilidad 41 / 73
Distrubución binomial
DefiniciónSea n y k enteros no negativos. El coeficiente binomial
(nk
)es el
número de diferentes maneras de escoger k objetos diferentes de unconjunto de n objetos diferentes, en donde el orden no es importante
Propiedades de los coeficientes binomialesSean n y k enteros no negativos:
•(nk
)= n!
k!(n−k)!
•(nk
)=
( nn−k
)•(n+1k+1
)=
(nk
)+
( nk+1
)Use Sage para verificar estos valores
Matemáticas aplicadas a la criptografía Teoría de probabilidad 41 / 73
Distribución binomial
Teorema binomialPara todos los números reales a, b, y enteros no negativos n:(a+ b)n =
∑nk=0
(nk
)akbn−k
Use Sage para verificar estos valores
DefiniciónUn intento de Bernoulli es un experimento con exactamente dosresultados posibles, llamados éxito y fracaso
Matemáticas aplicadas a la criptografía Teoría de probabilidad 42 / 73
Distribución binomial
Teorema binomialPara todos los números reales a, b, y enteros no negativos n:(a+ b)n =
∑nk=0
(nk
)akbn−k
Use Sage para verificar estos valores
DefiniciónUn intento de Bernoulli es un experimento con exactamente dosresultados posibles, llamados éxito y fracaso
Matemáticas aplicadas a la criptografía Teoría de probabilidad 42 / 73
Distribución binomial
Teorema binomialPara todos los números reales a, b, y enteros no negativos n:(a+ b)n =
∑nk=0
(nk
)akbn−k
Use Sage para verificar estos valores
DefiniciónUn intento de Bernoulli es un experimento con exactamente dosresultados posibles, llamados éxito y fracaso
Matemáticas aplicadas a la criptografía Teoría de probabilidad 42 / 73
Distribución binomial
ObservaciónSuponga que la probabilidad de éxito en un intento de Bernoulli es p.Entonces la probabilidad de que k tenga éxito en una secuencia de nintentos independientes es:(
nk
)pk(1− p)n−k,para cada0 ≤ k ≤ n
DefiniciónA esta distribución de probabilidad, se le llama distribución binomial
Matemáticas aplicadas a la criptografía Teoría de probabilidad 43 / 73
Distribución binomial
DefiniciónEl número esperado de éxitos en una secuencia de n intentosindependientes de Bernoulli, con probabilidad p de éxitos en cadaintento es np. La varianza de el número de éxitos es np(1− p).
Ley de números largosSea X una variable aleatoria denotando la fracción de éxitos en nintentos independientes de Bernoulli, con probabilidad p de éxito encada intento. Para cada ϵ > 0:
P(|X− p| > ϵ) → 0, as n → ∞
En otras palabras, mientras n crezca, la proporción de éxitos sedebería de acercar a p (la probabilidad de éxito en cada intento)
Matemáticas aplicadas a la criptografía Teoría de probabilidad 44 / 73
Contenido de la sección 6
Introducción
Tipos de números
Teorema, lema, etc
Teoría de conjuntos
Teoría de probabilidad
Teoría de la información
Teoría de la complejidad
Matemáticas aplicadas a la criptografía Teoría de la información 45 / 73
Variables aleatorias
Sea S el espacio de muestra con una distribución de probabilidad P.
DefiniciónUna variable aleatoria X es una función del espacio de muestra S a elconjunto de los números reales; para cada evento simple si ∈ S, Xasigna un número real X(si).
Dado que S se considera finito, X sólo puede tomar un número finitode valores.
DefiniciónSea X una variable aleatoria en S. El valor esperado o media de X esE(X) =
∑si∈S X(si)P(si)
Matemáticas aplicadas a la criptografía Teoría de la información 46 / 73
Variables aleatorias
ObservaciónSea X una variable aleatoria en S. Entonces E(X) =
∑x∈R x · P(X = x)
ObservaciónSi X1, X2, . . . , Xm son variables aleatorias en S, y a1, a2, . . . , am sonnúmeros reales, entonces E(
∑mi=1 aiXi) =
∑mi=1 aiE(Xi)
Matemáticas aplicadas a la criptografía Teoría de la información 47 / 73
Variables aleatorias
DefiniciónLa varianza de una variable aleatoria X de una media µ es un númerono negativo definido por>
Var(X) = E((X− µ)2)
La desviación estándar de X es la raíz cuadrada no negativa de Var(X).
Si una variable aleatoria tiene poca varianza, entonces gradesvariaciones de la media podrían no ser observadas. . .
Matemáticas aplicadas a la criptografía Teoría de la información 48 / 73
Variables aleatorias
Inequalidad de ChebyshevSea X una variable aleatoria con media µ = E(X) y una varianzaσ2 = Var(X), entonces para todo t > 0:
P(|X− µ| ≥ t) ≤ σ2
t2.
Matemáticas aplicadas a la criptografía Teoría de la información 49 / 73
Entropía
• Sea X una variable aleatoria a partir de un conjunto finito devalores x1, x2, . . . , xn con probabilidad P(X = xi) = pi, donde0 ≤ pi ≤ 1 para cada i, 1 ≤ i ≤ n, y donde
∑ni=1 pi = 1. Sean Y y Z
variables aleatorias con valores dentro de conjuntos finitos.
• La entropía de X es la medida matemática de la cantidad deinformación proveída por una observación de X. En otraspalabras, es la incertidumbre acerca de los resultados a obtenerantes de la observación de X. La entropía es útil para aproximarel número promedio de bits requeridos para codificar loselementos de X.
Matemáticas aplicadas a la criptografía Teoría de la información 50 / 73
Entropía
DefiniciónLa entropía, o incertidumbre de X está definida como:
H(X) = −∑n
i=1 pilg pi =∑n
i=1 pilg(
1pi
)en donde, por convención,
pi · lg pi = pi · lg(
1pi
)= 0, si pi = 0.
Propiedades de la entropíaSea X una variable aleatorio que produce n valores:
• 0 ≤ H(X) ≤ lg n
• H(X) = 0 sí y sólo sí pi = 1 para i, con pj = 0 para todo j = i (nohay duda del siguiente valor)
• H(X) = lg n sí y sólo si pi = 1/n para todo i con 1 ≤ i ≤ n (todoslos valores son igualmente posibles)
Matemáticas aplicadas a la criptografía Teoría de la información 51 / 73
Entropía
DefiniciónLa entropía conjunta de X y Y está definida como:
H(X, Y) = −∑x,y
P(X = x, Y = y)lg(P(X = x, Y = y))
en donde los índices x y y de la suma pasan por todos los valores de Xy Y respectivamente.
ObservaciónSi X y Y son variables alreatorias, entonces H(X, Y) ≤ H(X) + H(Y) yviceversa, sí y sólo sí X y Y son independientes.
Matemáticas aplicadas a la criptografía Teoría de la información 52 / 73
Entropía
DefiniciónSi X, Y son variables aleatorias, la entropía condicional de X dado Y = y es:
H(X|Y = y) = −P(X=x|Y=y)lg(P(X=x|Y=y))∑
x
en donde el índice x de la suma toma todos los valores de X. Laentropía condicional de X dado Y también conocida como laequivocación de Y acerca de X es:
H(X|Y) =∑y
P(Y = y)H(X|Y = y)
en donde el índice y de la suma toma todos los valores de Y.
Matemáticas aplicadas a la criptografía Teoría de la información 53 / 73
Entropía
Propiedades de la entropía condicionalSean X y Y variables aleatorias:
• H(X|Y) mide la cantidad de incertidumbre restante de X despuésde que Y ha sido observado
• H(X|Y) ≥ 0, y H(X|X) = 0
• H(X, Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)• H(X|Y) ≤ H(X), con equalidad sí y sólo sí X y Y son independientes
Matemáticas aplicadas a la criptografía Teoría de la información 54 / 73
Información mutua
DefiniciónLa información mutua o transinformación de las variables aleatorias X yY se denota como: I(X; Y) = H(X)− H(X|Y). Similarlmente, latransinformación de X y la pareja Y y Z se define como:I(X; Y,Z) = H(X)− H(X|Y,Z).
Matemáticas aplicadas a la criptografía Teoría de la información 55 / 73
Información mutua
Propiedades de la transinformación mutua
• La cantidad I(X; Y) se puede interpretar como la cantidad deinformación que Y revela sobre X. Similarmente, I(X; Y,Z) sería lacantidad de información que Y y Z conjuntamente revelan sobre X
• I(X; Y) ≥ 0
• I(X; Y) = 0 sí y sólo si X y Y son independientes (esto es, que Y norevela nada sobre X)
• I(X; Y) = I(Y; X)
Matemáticas aplicadas a la criptografía Teoría de la información 56 / 73
Información mutua
DefiniciónLa transinformación condicional del par X, Y dado Z se define como:
IZ(X; Y) = H(X|Z)− H(X|Y,Z)
propiedades de la transinformación condicional
• La cantidad IZ(X; Y) puede ser interpreatada como la cantidad deinformación que Y provee acerca de X, una vez que Z ya ha sidoobservada.
• I(X; Y,Z) = I(X; Y) + IY(X;Z)
• IZ(X; Y) = Iz(Y;Z)
Matemáticas aplicadas a la criptografía Teoría de la información 57 / 73
Contenido de la sección 7
Introducción
Tipos de números
Teorema, lema, etc
Teoría de conjuntos
Teoría de probabilidad
Teoría de la información
Teoría de la complejidad
Matemáticas aplicadas a la criptografía Teoría de la complejidad 58 / 73
Teoría de la complejidad
El principal objetivo de la teoría de la complejidad es proveer demecanismos para clasificar los problemas computacionales deacuerdo a los recursos necesarios para resolverlos.
DefiniciónUn algoritmo es un procedimiento computacional bien definido quetoma una variable de entrada y se detiene con una salida
``Bien definido'' es un concepto muy ambigüo. Cuando un algoritmose desea formalizar, se utilizan máquinas de Turín, máquinas deacceso aleatorio, o circuitería booleana.
Matemáticas aplicadas a la criptografía Teoría de la complejidad 59 / 73
Conceptos
DefiniciónEl tamaño de la entrada es el número total de nits necesarios pararepresentar la entrada en notación binaria, ya codificada.
DefiniciónEl tiempo de ejecución de un algoritmo para una entrada en particulares el número de operaciones primiticas, o ``pasos'' ejecutados.
Matemáticas aplicadas a la criptografía Teoría de la complejidad 60 / 73
Conceptos
DefiniciónEl tiempo de ejecución en el peor escenario de un algoritmo es el límitesuperior del tiempo de ejecución para cualquier valor de entrada,expresado como una función de tamaño de entrada
DefiniciónEl tiempo de ejecución en el caso promedio de un algoritmo es el tiempode ejecución promedio de todas las entradas de un tamaño deentrada fijo, expresado como una función del tamaño de entrada
Matemáticas aplicadas a la criptografía Teoría de la complejidad 61 / 73
Notación
En algunas ocasiones es difícil estimar el tiempo de ejecución exactode un algoritmo, por lo que en ocasiones uno hace aproximaciones, yuno termina derivando el tiempo de ejecución asintótico; esto es,variando el tiempo de ejecución de acuerdo al tamaño de los datos deentrada.
Matemáticas aplicadas a la criptografía Teoría de la complejidad 62 / 73
Notación de orden
• El límite superior asintótico f(n) = O(g(n)), si hay una constantepositiva c, y un entero positivo n0 tal que 0 ≤ f(n) ≤ cg(n) paratodo n ≥ n0
• El límite inferior asintótico f(n) = Ω(g(n)), si existe una constantepositiva c, y un entero positivo n0 tal que 0 ≤ cg(n) ≤ f(n) paratodo n ≥ n0
• El límite justo asintótico f(n) = Θ(g(n)), si existen constantespositivas c1, y c− 2, y un entero positivo n0 tal quec1g(n) ≤ f(n) ≤ c2g(n) para todo n ≥ n0
• o-notation f(n) = o(g(n)), si para cualquier constante positivac > 0 existe una constante n0 > 0 tal que 0 ≤ f(n), cg(n) para todon ≥ n0
Matemáticas aplicadas a la criptografía Teoría de la complejidad 63 / 73
Clases de complejidad
DefiniciónUn algoritmo de tiempo polinomial es un algoritmo cuyo tiempo deejecución en el peor escenario es de la forma O(nk), donde n es eltamaño de la entrada, y k es una constante. Cualquier algoritmo cuyotiempo de ejecución no pueda delimitarse, se considera algoritmo detiempo exponencial
Los algoritmos de tiempo polinomial se definen como buenos, oeficientes, mientras que los exponenciales como ineficientes.
Matemáticas aplicadas a la criptografía Teoría de la complejidad 64 / 73
Clases de complejidad
DefiniciónUn algoritmo de tiempo sub-exponencial es un algoritmo cuyo tiempode ejecución en el peor escenario es de la forma eO(n), donde n es eltamaño de la entrada
Un algoritmo de tiempo sub-exponencial es asintóticamente máslento que un algoritmo de tiempo polinomial, pero más rápido queun algoritmo de tiempo exponencial.
Matemáticas aplicadas a la criptografía Teoría de la complejidad 65 / 73
P, NP
DefiniciónLa clase de complejidad P es el conjunto de problemas decisionalesque se pueden resolver en tiempo polinomial
DefiniciónLa clase de complejidad NP es el conjunto de problemas decisionalespara los cuales un SÍ como respuesta puede verificarse en tiempopolinomial siempre y cuando exista cierta información adicional(llamada certificado)
DefiniciónLa clase de complejidad co-NP es el conjunto de problemasdecisionales para los cuales un NO como respuesta puede verificarseen tiempo polinomial co el certificado apropiado
Matemáticas aplicadas a la criptografía Teoría de la complejidad 66 / 73
Sobre P, y NP
ObservaciónP ⊆ NP, y P ⊆ co-NP
Preguntas:
• P ?= NP
• NP ?= co-NP
• P ?= NP ∩ co-NP
Matemáticas aplicadas a la criptografía Teoría de la complejidad 67 / 73
Reducciones
Sean L1, y L2 tres problemas decisionales. . .
DefiniciónSe dice que L1 reduce polinomialmente a L2, denotado como L1 ≤P L2,si existe un algoritmo que resuelva L1 utilizando como subrutina, unalgoritmo que resuelve L2, el cual sea de tiempo polynomial tantopara L1 como para L2
DefiniciónSi L1 ≤P L2, y L2 ≤P L1, entonces L1 y L2 son computacionalmenteequivalentes.
Matemáticas aplicadas a la criptografía Teoría de la complejidad 68 / 73
Reducciones
Sean L1, L2, y L3 tres problemas decisionales. . .
Observaciones
• (transitividad): Si L1 ≤P L2, u L2 ≤P L3, entonces L1 ≤P L3• Si L1 ≤P L2, y L2 ∈ P, entonces L1 ∈ P.
DefiniciónSe dice que un problema decisional L es NP-completo si:
• L ∈NP, y
• L1 ≤P L para cada L1 ∈NP
La clase que agrupa a todos los problemas NP-completos se denotacomo NPC. Dicha clase agrupa a los problemas más difíciles, ya queson cuando menos tanto como otros problemas NP
Matemáticas aplicadas a la criptografía Teoría de la complejidad 69 / 73
Reducciones
Observaciones
• Si L1 es NP-completo, y L1 ∈ P, entonces P = NP
• Si L1 ∈ NP, L2 is NP-completo, y L2 ≤ L1, entonces L1 también esNP-completo
• Si L1 es NP-completo, y L1 ∈ co-NP, entonces NP = co-NP
Matemáticas aplicadas a la criptografía Teoría de la complejidad 70 / 73
Reducciones
DefiniciónUn problema es NP-duro si existe algún problema NP-completo quelo reduzca a tiempo polinomial.
Matemáticas aplicadas a la criptografía Teoría de la complejidad 71 / 73
Tiempos de complejidad
Descripción Notación Ejemplo
Tiempo constante O(1) Determinar si un entero es parT. Logarítmico O(log n) Búsqueda binariaT. Linear O(n) Buscar un elemento en una listaT. linearitmico O(nlog n) Método quicksortT. quadrático O(n2) Método de la burbujaT. cúbico O(n3) Multiplicación de 2 matrices n× nT. polinomial 2O(log n) Pruebas de primalidadT. exponencial 2O(n) Problema del vendedor viajeroT. factorial 2O(n!) . . . por fuerza bruta
Matemáticas aplicadas a la criptografía Teoría de la complejidad 72 / 73
• Fin de la unidad 1
Top Related