Usuario:Óscar Baños Campos/Taller

PERMUTACIONES CIRCULARES: Definición:

Demostracion

    Supongamos una reunión de n personas que se sientan en torno a una mesa circular con n sillas, una silla para cada persona, ¿De cuántas formas diferentes se pueden distribuir las personas en los asientos disponibles teniendo en cuenta que la mesa es circular?

Para ello se requiere que los asientos sean indistinguibles, es decir, si solo se sentase una persona no importa en cual de ellos se siente pues una circunferencia no tiene principio ni final, solo se le asigna un punto arbitrario como referencia. Los objetos a colocar deben ser distinguibles o en su caso de multiconjuntos distinguibles de elementos indistinguibles, ejemplo el conjunto $C_{1}$ = {1, 1, 1} El orden importa, pues no es lo mismo que una persona se siente a la derecha o a la izquierda de otra.

Teniendo esto en cuenta se toma la primera n-persona como punto de referencia sentándola en una silla cualquiera de la mesa, después de esto se coloca la siguiente n-1 persona en otra n-1 silla de las disponibles, se repite el mismo proceso para la n-2, n-3 ... n-n personas con lo cual al final al aplicar la propiedad multiplicativa obtenemos que las permutaciones cíclicas de n elementos son $PC_{n}=(n-1)!$ formas diferentes.

Ejemplos practicos:

   Dadas 5 personas en torno a una mesa redonda, ¿De cuántas formas distintas podemos sentarlas?

En este caso estamos ante una permutación circular sin restricción ni condición alguna, para ello procedemos a asignar a un elemento una posición concreta de la mesa para tomarlo como punto de referencia y permutamos a los restantes en torno a él, esto nos deja con $PC_{5}=(5-1)!=4!=24$ formas distintas pues lo que se debe permutar son los demás elementos del conjunto.

   Dadas 5 personas en torno a una mesa redonda tal que la persona S y T quieran sentarse siempre juntas, ¿De cuántas formas distintas podemos sentarlas?

En este caso tenemos 4 elementos dentro del conjunto, 3 personas sean U, V y W y otras dos que forman un multiconjunto $(S,T)$

  Fijar personas de dicho conjunto.

TEMA 1. FUNDAMENTOS:

Funciones: Funciones Hash y su uso en la criptografía.

Definición de función Hash

Una función Hash comúnmente denotada H, es una función para la cual un elemento de un conjunto se proyecta sobre otro conjunto asegurando que para el elemento del primer conjunto le corresponde un único elemento del conjunto imagen, en cambio a los elementos del conjunto imagen les pueden o no corresponder uno, varios o incluso ningún elemento del primer elemento.

Cuando a un elemento del conjunto imagen le corresponden múltiples elementos del conjunto generador al cual se le aplica la función se dice que existen colisiones.

$f:A\rightarrow B$

$h(x)\rightarrow y$

(Siendo x comúnmente llamada llave e y clave)

Uso de las funciones SHA

Una característica principal de las funciones SHA es la capacidad de no reflexividad, es decir, dado una cadena de bits del buffer de salida resulta prácticamente imposible intentar hallar una cadena origen que devuelva el mismo contenido, además de disponer de una gran cantidad de combinaciones posibles que evitan que se puedan dar duplicado de datos o colisiones las cuales pueden comprometer la seguridad de diferentes archivos.

Las funciones SHA permiten la creación de cadenas diferentes que facilitan seguir un registro de cambios en la seguridad de diferentes archivos conocida como huella digital, esto sirve de especial importancia en aplicaciones tales como la creación de cuentas asociadas a contraseñas que solo un usuario debe conocer, claves de desencriptado de ficheros o usos en la creación de cadenas de bloques en criptomonedas como el bitcoin.

En teoría una función SHA perfecta no debería tener ninguna colisión pero debido a que están pensadas para trabajar con cadenas de texto indeterminadas, las posibilidades de que exista una colisión imprevista no son nulas pero si son increíblemente bajas pues, tomando el ejemplo de SHA-1 de 160 bits tendríamos hasta $2^{160}$ combinaciones posibles el cual es un número tan grande que esperar que se dé una colisión de manera fortuita resulta inviable, sin embargo no significa que sea totalmente seguro pues con métodos avanzados se ha logrado desencriptar sin necesidad de recurrir a ataques de fuerza llegando a encontrar colisiones y forzando a la creación de nuevas formas de encriptado para aumentar la seguridad.

$Hash(cadena,sLL)=clave$

$verificacion(cadena,clave,pLL)=Verdadero/Falso$

La primera permite a un usuario crear una firma digital para verificar que un mensaje dentro de una transacción ha sido emitida por él mismo y la segunda permite que el receptor verifique que el emisor fue el autor original de dicha transacción.

Esta firma digital permite crear un sistema de confianza el cual se basa en que si ningún otro usuario conoce tu llave secreta, nadie podrá ser capaz de falsificar una transacción realizada a tu nombre. La importancia radica en que la firma digital varia con cada mensaje, es decir que para cada transacción de una criptomoneda se tendría que crear una nueva clave de la cual solo el usuario original conoce la llave secreta, debido a que el SHA de mayor uso extendido es de 256 bits (bitcoin lo utiliza aunque algunas otras criptomonedas utilizan el 512 bits para seguridad añadida) eso deja una posibilidad de 1 entre $2^{256}$ posibles combinaciones.

Este número es lo suficientemente grande como para evitar que se pueda buscar una llave probando combinaciones y asegurar que la probabilidad de colisión sea tan baja que resulte inviable encontrar un brecha, cabe mencionar que a día de hoy sigue sin haberse encontrado una brecha o colisión que provoque una vulnerabilidad al sistema. pero si se llegó a encontrar en SHA menores como el de 160 bits o 128.

TEMA 2. TEORIA DE NUMEROS

Números primos y Teorema de Dirichlet

El teorema de Dirichlet sobre progresiones aritméticas es un resultado de la teoría analítica de números demostrado por el matemático Dirichlet. Este teorema sobre la distribución de los números primos en $\mathbb {N}$ , fue conjeturado por Gauss y finalmente demostrado en 1837 por Dirichlet, nombre por el que actualmente se le conoce.

Enunciado

Sea $a,\,d\in \mathbb {N}$ tal que el máximo común divisor $\operatorname {mcd} (a,d)=1$ , entonces la progresión aritmética $a_{n}=a+n\cdot d$ contiene infinitos números primos.

Dirichlet

Esto quiere decir que los números a+nd forman una progresión aritmética

a,\ a+d,\ a+2d,\ a+3d,\ \dots ,\

en la que hay infinitos números primos, o dicho de otra manera, hay infinitos números primos congruentes con a módulo d.

Por ejemplo, el teorema asegura que hay una cantidad infinita de números primos que terminen en 7, ya que los números que terminan en 7 forman una progresión aritmética (7, 17, 27, 37, ...) es decir, es una sucesión de números de la forma a+nd con a=7 y d=10, siendo estos primos entre sí, luego su máximo común divisor es 1.

Enunciado extendido

El enunciado anterior esta formulado para la base decimal o base 10 pero se puede extender a diferentes bases.

$Sea\,a,b\in \mathbb {N} \,\,\,\,b\,una\,base\,numerica,\,mcd(a,b)=1$

Siempre que a sea $a\in {2,3,...,(b-1)}$ es decir, a está comprendida entre el menor número primo, 2, y el número menor inmediato a la base, obtendremos distintas clases de congruencias en dicha base.

Es decir, aquellos número coprimos con la base b serán válidos para verificar que $a_{n}=a+n*b$ ,solo es necesario comprobar con las primeras clases pues, tomando el ejemplo de la base 10

$mcd(7,10)=1$ podemos afirmar que en la sucesión 17, 27, 37... habrá números primos, al igual con la sucesión de la clase del 1,3 y 9 pero sería redundante aplicarlo a la clase del 17 que esta contenida a su vez en la del 7.

De aquí se puede deducir aplicando la función $\phi$ de Euler para la base b, habrá 'd' distintas clases de equivalencias.

En la base decimal

$\phi (10)=4$ clases de equivalencia distintas que son 1,3,7,9 es decir, todos los números acabados en esas cifras o que sean pertenecientes a su clase de equivalencia podrán ser números primos.

Esto se debe a que la función de Euler se puede utilizar para calcular la cantidad de número coprimos a un número dado, en el caso del 10 son 4 número coprimos.

Para ilustrar el teorema extendido a bases numéricas diferentes tomemos el ejemplo de la base 10 o decimal.

cuando hacemos una tabla que contiene a los números naturales nos fijamos

que solo los número acabados en 1, 3, 7 o 9 pueden ser número primos (a excepción del 2 y 5) pues todos los demás que acaben en cifra par o 5 serán múltiplos de estos números

Esto es fácilmente visualizable pues el 10 esta compuesto por 2 y 5; $10=2*5$


0 mod 10	0	10	20	30	40	50	60	70	80	90
1 mod 10	1	11	21	31	41	51	61	71	81	91
2 mod 10	2	12	22	32	42	52	62	72	82	92
3 mod 10	3	13	23	33	43	53	63	73	83	93
4 mod 10	4	14	24	34	44	54	64	74	84	94
5 mod 10	5	15	25	35	45	55	65	75	85	95
6 mod 10	6	16	26	36	46	56	66	76	86	96
7 mod 10	7	17	27	37	47	57	67	77	87	97
8 mod 10	8	18	28	38	48	58	68	78	88	98
9 mod 10	9	19	29	39	49	59	69	79	89	99

En este caso tenemos 4 clases de equivalencias que se corresponden al residuos 1, 3, 7, 9 congruentes con módulo 10

$X\equiv 1(mod10)$

$X\equiv 3(mod10)$

$X\equiv 7(mod10)$

$X\equiv 9(mod10)$

Cualquier X que verifique dicha congruencia podrá ser número primo, es decir, si un número no cumple con lo anterior podemos afirmar que es imposible que sea número primo.

Una conclusión que se puede extraer es que para todas las clases tendrán un número aproximado de primos, es decir, que dado un número primo aleatorio las probabilidades de que pertenezca a una clase o a otra son las mismas por tanto si fuésemos añadiendo números primos sucesivos observaríamos que se distribuyen equitativamente entre la clase del 1, 3, 7, 9 para la base 10 y esto se puede aplicar a cualquier base distinta.

De aquí se puede concluir que las distribuciones de números primos suelen tener un aspecto uniforme esto es fácilmente observable en distintas representaciones gráficas en las cuales los números primos tienen a formar grupos pero no es resultado de una propiedad de los números primos sino que a la hora de obtener diferentes clases de equivalencia los número primos se agrupan en las clases que son coprimas con la base en la cual se representa.

Demostración

La demostración del teorema utiliza las propiedades de ciertas funciones multiplicativas (conocidas como funciones-L de Dirichlet) y varios resultados sobre aritmética de números complejos y es suficientemente compleja como para que algunos textos clásicos de teoría de números decidan excluirla de su repertorio de demostraciones.^[1]