0Pricing
Cryptology Academy · Lección

MCD, función phi de Euler e introducción a la teoría de números

Aplique el MCD y la función phi de Euler a problemas criptográficos reales.

MCD, función phi de Euler e introducción a la teoría de números es una lección gratuita de Cryptology Academy en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Cryptology Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Cryptology Academy incluye 4 lecciones en total.

Bienvenida

El GCD y la función phi de Euler son herramientas esenciales en RSA y en muchos otros sistemas de clave pública. Vamos a dominarlos con ejemplos.

Máximo común divisor (GCD)

GCD(a, b) es el entero más grande que divide tanto a como a b sin dejar resto. GCD(12, 8) = 4. Si GCD(a, m) = 1, decimos que a y m son coprimos o primos entre sí.

Algoritmo euclídeo

GCD(a, b) = GCD(b, a mod b), caso base GCD(a, 0) = a. GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

Algoritmo euclídeo extendido

La versión extendida encuentra enteros x, y tales que ax + by = GCD(a,b). Cuando GCD(a,m)=1, x es el inverso modular de a módulo m. Así es como RSA calcula las claves privadas.

Función phi de Euler φ(n)

φ(n) cuenta los enteros del 1 al n que son coprimos con n. φ(10) = 4 porque {1, 3, 7, 9} son coprimos con 10. φ(p) = p-1 para cualquier primo p.

Phi de un producto

Para RSA: n = p×q (p,q primos). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Ejemplo: p=5, q=11: φ(55) = 4×10 = 40. Por eso factorizar n rompe RSA: revela φ(n).

Teorema de Euler

Si GCD(a,n)=1: a^φ(n) ≡ 1 (mod n). Esta es la base matemática del descifrado RSA: M = C^d mod n porque e×d ≡ 1 (mod φ(n)).

Cálculo de d en RSA

Elija e = 65537 (exponente público habitual de RSA). Calcule d = e^(-1) mod φ(n) mediante el algoritmo euclídeo extendido. Verifique que e×d mod φ(n) == 1.

Phi en Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Lambda de Carmichael

El RSA moderno utiliza la función lambda de Carmichael λ(n) = lcm(p-1, q-1) en lugar de φ(n). Proporciona un módulo equivalente más pequeño. PKCS#1 v2 y NIST recomiendan λ(n).

Resumen de la aplicación práctica

GCD: comprueba que e sea coprimo con φ(n). Algoritmo euclídeo extendido: calcula la clave privada d. Phi: determina el grupo de exponentes para la exponenciación modular. Las tres herramientas se utilizan en cada generación de claves RSA.

Comprobación rápida

Para RSA con p=7 y q=11, ¿cuánto vale φ(n)?

Recapitulación

¡Excelente! El GCD, el algoritmo euclídeo y la función phi de Euler ya forman parte de su conjunto de herramientas. A continuación estudiaremos XOR y las operaciones bit a bit, los componentes básicos de los cifrados simétricos.

Preguntas frecuentes

¿La lección «MCD, función phi de Euler e introducción a la teoría de números» es gratis?

Sí — el texto completo de «MCD, función phi de Euler e introducción a la teoría de números» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Cryptology Academy, actualiza a CoddyKit PRO. El curso de Cryptology Academy incluye 4 lecciones en total.

¿Qué aprenderé en «MCD, función phi de Euler e introducción a la teoría de números»?

Aplique el MCD y la función phi de Euler a problemas criptográficos reales. Practicas Cryptology Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Cryptology Academy?

No se requiere experiencia previa. Cryptology Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.

¿Cuánto tiempo toma la lección «MCD, función phi de Euler e introducción a la teoría de números»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Cryptology Academy?

Sí. Cada lección de Cryptology Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Fundamentos del sistema binario y hexadecimal
  2. Fundamentos de la aritmética modular
  3. Números primos y factorización
  4. MCD, función phi de Euler e introducción a la teoría de números
← Volver a Cryptology Academy