Introducción a la Teoría de Números
La teoría de números es una rama de las matemáticas que se dedica al estudio de las propiedades de los números enteros. Es una disciplina rica y antigua que tiene aplicaciones en diversas áreas, incluyendo la criptografía, la computación, y la teoría de la información.
Algoritmo de Euclides para el Máximo Común Divisor (MCD)
El algoritmo de Euclides es uno de los algoritmos más antiguos conocidos y es utilizado para encontrar el máximo común divisor (MCD) de dos enteros. Este algoritmo se basa en la propiedad de que el MCD de dos números también divide su diferencia.
def euclides(a, b):
while b != 0:
a, b = b, a % b
return a
# Ejemplo de uso
print(euclides(48, 18)) # Salida: 6
Criba de Eratóstenes
La criba de Eratóstenes es un algoritmo eficiente para encontrar todos los números primos menores que un número dado. Este método elimina iterativamente los múltiplos de cada número primo comenzando desde 2.
def criba_eratostenes(n):
primos = [True] * (n + 1)
p = 2
while p ** 2 <= n:
if primos[p]:
for i in range(p * p, n + 1, p):
primos[i] = False
p += 1
return [p for p in range(2, n + 1) if primos[p]]
# Ejemplo de uso
print(criba_eratostenes(30)) # Salida: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Teorema de Fermat Pequeño
El teorema de Fermat Pequeño es una herramienta fundamental en la teoría de números y tiene aplicaciones en la criptografía. Establece que si \(p\) es un número primo y \(a\) es un número entero no divisible por \(p\), entonces \(a^{(p-1)} \equiv 1 \ (\text{mod} \ p)\).
Algoritmo de Exponenciación Modular
El algoritmo de exponenciación modular se utiliza para calcular grandes potencias módulo un número. Es fundamental en algoritmos criptográficos, como RSA. Este algoritmo reduce el problema a una serie de multiplicaciones modulares más pequeñas.
def exp_modular(base, exp, mod):
result = 1
base = base % mod
while exp > 0:
if (exp % 2) == 1:
result = (result * base) % mod
exp = exp >> 1
base = (base * base) % mod
return result
# Ejemplo de uso
print(exp_modular(2, 10, 1000)) # Salida: 24
Algoritmo de Miller-Rabin para la Prueba de Primalidad
El algoritmo de Miller-Rabin es una prueba probabilística para determinar si un número es primo. Es ampliamente utilizado debido a su eficiencia y es adecuado para números grandes.
import random
def es_primo(n, k=5): # Número de pruebas
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0:
return False
def prueba_miller(d, n):
a = random.randint(2, n - 2)
x = exp_modular(a, d, n)
if x == 1 or x == n - 1:
return True
while d != n - 1:
x = (x * x) % n
d *= 2
if x == 1:
return False
if x == n - 1:
return True
return False
d = n - 1
while d % 2 == 0:
d //= 2
for _ in range(k):
if not prueba_miller(d, n):
return False
return True
# Ejemplo de uso
print(es_primo(31)) # Salida: True
print(es_primo(18)) # Salida: False
Conclusión
Los algoritmos de teoría de números son fundamentales en diversas aplicaciones matemáticas y computacionales. Dominar estos algoritmos en Python proporciona una base sólida para abordar problemas complejos en criptografía, teoría de la información y otros campos relacionados.