Publicado · en mejora
Algorithm
MCD y mcm, aritmética modular e inversos, exponenciación rápida, criba de Eratóstenes y nCr mod p: la teoría de números para algoritmos.
La teoría de números estudia los enteros, en especial la divisibilidad y los restos. En algoritmos significa calcular el MCD y el mcm con el algoritmo de Euclides, manejar valores enormes mediante aritmética modular y hallar inversos modulares con el algoritmo de Euclides extendido o el pequeño teorema de Fermat. La exponenciación rápida, la criba de Eratóstenes, la factorización en primos y los coeficientes binomiales módulo un primo completan el conjunto de herramientas.
Estas herramientas aparecen constantemente en entrevistas técnicas y concursos de programación como «imprime la respuesta módulo 10^9 + 7», y en producción sostienen la criptografía de clave pública como RSA y Diffie-Hellman, las funciones hash, los generadores de números aleatorios y los dígitos de control. Casi todas se ejecutan en tiempo logarítmico o casi lineal, así que entenderlas convierte cálculos que nunca terminarían en operaciones de milisegundos.
Empieza siguiendo a mano las reglas de la aritmética modular y el algoritmo de Euclides, y después implementa tú mismo la exponenciación rápida y la criba. Continúa con los inversos modulares y nCr mod p, y si programas en C++ o Java, practica el manejo del desbordamiento en multiplicaciones y de los restos negativos. Aprende también las funciones estándar, como pow(a, e, m) y math.gcd de Python.
Repetir mcd(a, b) = mcd(b, a mod b) obtiene el MCD en O(log n); la versión extendida devuelve además los coeficientes de ax + by = mcd(a, b).
La suma, la resta y la multiplicación conservan los restos, así que se reduce tras cada paso; la división pasa a ser una multiplicación por un inverso modular.
Elevar al cuadrado la base siguiendo los bits del exponente calcula a^e mod m con unas log e multiplicaciones en lugar de e.
Tachar los múltiplos de cada primo desde i × i encuentra todos los primos hasta n en O(n log log n); una tabla del menor factor primo permite factorizar rápido.
gcd calcula el máximo común divisor con el algoritmo de Euclides, y el mínimo común múltiplo se obtiene como a // gcd(a, b) * b. mod_pow es la exponenciación rápida: recorre los bits del exponente elevando al cuadrado y multiplicando, y con un módulo primo p, a^(p-2) da el inverso modular de a. sieve usa la criba de Eratóstenes para listar todos los primos hasta 30. Guarda el archivo y ejecuta python number_theory.py.
number_theory.py
import math
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
def mod_pow(base: int, exp: int, mod: int) -> int:
result, base = 1 % mod, base % mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
def sieve(n: int) -> list[int]:
is_prime = [False, False] + [True] * (n - 1)
for i in range(2, math.isqrt(n) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i, p in enumerate(is_prime) if p]
MOD = 10**9 + 7
print(gcd(84, 36), 84 // gcd(84, 36) * 36) # 12 252
print(mod_pow(3, 200, 13)) # 9
print(mod_pow(3, MOD - 2, MOD)) # 333333336, the inverse of 3
print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
python number_theory.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Matemáticas y teoría de números.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Matemáticas y teoría de números.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.