Modular Linear Equation
Resolver la ecuación lineal modular ax≡b (mod n): las soluciones existen si y solo si gcd(a,n) divide a b, y hay exactamente gcd(a,n) de ellas.
Propósito
Resolver ecuaciones modulares y comprender cuándo es posible la división en aritmética modular.
Mecanismo
Sea d=gcd(a,n). Si d no divide a b, no hay solución. En caso contrario, se usa el algoritmo extendido de Euclides para hallar la solución única de (a/d)·x0 ≡ b/d (mod n/d); todas las soluciones son x0 + k*(n/d) mod n para k=0..d-1.
Casos de uso
- Resolución de ecuaciones criptográficas
- Aritmética modular
- Cómputo en teoría de números