Test Tema 6 — Teoría de números, congruencias y criptografía¶

Practica las 15 preguntas del test. Marca una respuesta por pregunta y pulsa Corregir test para ver la nota, las respuestas correctas y explicaciones paso a paso.

Puntuación

Las preguntas 1–5 y 11–15 valen 0,70 puntos; las preguntas 6–10 valen 0,60 puntos. Total: 10 puntos.

Chuleta final — Teoría de números y criptografía¶

1. Máximo común divisor (MCD) y algoritmo de Euclides¶

El MCD de dos enteros es el mayor entero positivo que divide a ambos.

Algoritmo de Euclides:

\[ a=bq+r \quad\Longrightarrow\quad \operatorname{mcd}(a,b)=\operatorname{mcd}(b,r) \]

Se repite hasta obtener resto cero. El último resto no nulo es el MCD.

Ejemplo:

\[ \begin{aligned} 48&=1\cdot30+18\\ 30&=1\cdot18+12\\ 18&=1\cdot12+6\\ 12&=2\cdot6+0 \end{aligned} \]

Por tanto, \(\operatorname{mcd}(48,30)=6\).

2. Identidad de Bézout¶

Para enteros \(a,b\), no ambos cero, existen enteros \(x,y\) tales que:

\[ ax+by=\operatorname{mcd}(a,b) \]

El algoritmo extendido de Euclides permite encontrar esos coeficientes. Si el MCD es 1, los números son coprimos.

3. Teorema Fundamental de la Aritmética¶

Todo entero mayor que 1 se descompone de forma única (salvo el orden) como producto de primos.

Ejemplo:

\[ 360=2^3\cdot3^2\cdot5 \]

4. Congruencias¶

\[ a\equiv b\pmod n \]

Significa que \(a\) y \(b\) tienen el mismo resto al dividir entre \(n\), o que \(n\mid(a-b)\).

Una congruencia lineal tiene la forma:

\[ ax\equiv b\pmod n \]

Tiene solución si y solo si \(\operatorname{mcd}(a,n)\) divide a \(b\). Si \(a\) y \(n\) son coprimos, existe una solución única módulo \(n\).

5. Pequeño teorema de Fermat¶

Si \(p\) es primo y \(p\nmid a\):

\[ a^{p-1}\equiv1\pmod p \]

Forma equivalente, válida para todo entero \(a\):

\[ a^p\equiv a\pmod p \]

Ejemplo: con \(a=3\) y \(p=7\):

\[ 3^6=729=7\cdot104+1 \quad\Longrightarrow\quad 3^6\equiv1\pmod7 \]

Sirve para simplificar potencias en aritmética modular.

6. Teorema chino del resto (TCR)¶

Si los módulos \(n_1,\ldots,n_k\) son coprimos dos a dos, el sistema

\[ \begin{cases} x\equiv a_1\pmod{n_1}\\ x\equiv a_2\pmod{n_2}\\ \vdots\\ x\equiv a_k\pmod{n_k} \end{cases} \]

tiene una solución única módulo \(N=n_1n_2\cdots n_k\).

7. Criptografía¶

La criptografía utiliza técnicas matemáticas para proteger información: confidencialidad, integridad y autenticación.

Sistema	Idea matemática principal	Uso
Diffie-Hellman	Dificultad del logaritmo discreto	Acordar una clave compartida
RSA	Dificultad de factorizar el módulo compuesto	Cifrado y firmas digitales

Diffie-Hellman, idea básica:

Se acuerdan parámetros públicos \(p\) y \(g\).
Cada parte elige un exponente privado (secreto).
Calcula y comparte un valor público.
Cada parte combina el valor público recibido con su propio secreto y obtiene la misma clave compartida.

Nunca se intercambian los exponentes privados.

RSA, idea básica:

Se eligen dos primos grandes \(p\) y \(q\).
Se calcula \(n=pq\).
Se construyen una clave pública y una privada relacionadas matemáticamente.
Se usa para operaciones de clave pública, como cifrado o firmas digitales.

No confundas

Diffie-Hellman: logaritmo discreto.
RSA: factorización de enteros grandes.
MCD: máximo común divisor; mcm: mínimo común múltiplo.
Bézout: expresa el MCD como combinación lineal.
El pequeño teorema de Fermat requiere que el módulo sea primo en la formulación \(a^{p-1}\equiv1\pmod p\) y que \(a\) no sea múltiplo de \(p\).
RSA puede utilizarse para firmas y cifrado, pero no es la técnica adecuada para almacenar contraseñas: para ello se usan funciones específicas de derivación de contraseñas, como Argon2id, scrypt o bcrypt.