El algoritmo de Pasos Pequeños y Grandes (conocido internacionalmente como BSGS o Baby Step Giant Step) es una técnica eficiente para resolver el problema del logaritmo discreto en aritmética modular. Este método permite encontrar exponentes en ecuaciones de la forma:
Algoritmo BSGS Básico
El algoritmo BSGS se aplica cuando el máximo común divisor entre la base \(a\) y el módulo \(p\) es 1, es decir, \((a, p) = 1\).
Enfoque Brute Force
Un método simple sería verificar todos los valores posibles de \(x\) desde 0 hasta \(p-1\), lo que nos daría una complejidad temporal de \(O(p)\). Para valores grandes de \(p\), este enfoque se vuelve impracticable.
Algoritmo BSGS Optimizado
El algoritmo BSGS optimizado divide el problema en dos partes:
- Pasos pequeños: Calcular y almacenar los valores de \(a^j \pmod{p}\) para \(j = 0, 1, ..., m-1\)
- Pasos grandes: Calcular \(a^{im} \pmod{p}\) para \(i = 1, 2, ..., m\) y buscar coincidencias con los valores almacenados
Donde \(m\) se elige como \(\lceil \sqrt{p} \rceil\). Este enfoque reduce la complejidad temporal a \(O(\sqrt{p})\).
function resolverBSGS(base, resultado, modulo) { if (resultado === 1) return 0;
const m = Math.ceil(Math.sqrt(modulo));
const tablaHash = new Map();
let valorActual = resultado % modulo;
// Pasos pequeños: almacenar valores de base^j
for (let j = 0; j < m; j++) {
tablaHash.set(valorActual, j);
valorActual = (valorActual * base) % modulo;
}
const baseM = potenciaModular(base, m, modulo);
valorActual = 1;
// Pasos grandes: buscar coincidencias
for (let i = 1; i <= m; i++) {
valorActual = (valorActual * baseM) % modulo;
if (tablaHash.has(valorActual)) {
return i * m - tablaHash.get(valorActual);
}
}
return "Sin solución";
}
function potenciaModular(base, exponente, modulo) { let resultado = 1; base = base % modulo;
while (exponente > 0) {
if (exponente % 2 === 1) {
resultado = (resultado * base) % modulo;
}
exponente = Math.floor(exponente / 2);
base = (base * base) % modulo;
}
return resultado;
}
</details>Algoritmo BSGS Extendido
------------------------
¿Qué sucede cuando \\((a, p) \\neq 1\\)? En este caso, necesitamos una versión extendida del algoritmo.
Sea \\(d = (a, p)\\). La ecuación origianl \\(a^x \\equiv b \\pmod{p}\\) solo tiene solución si \\(d\\) divide a \\(b\\). Si no es así, el problema no tiene solución.
Podemos transformar la ecuación dividiendo por \\(d\\) repetidamente hasta que la base y el módulo sean coprimos:
<div>\[\frac{a}{d} \cdot a^{x-1} + k \cdot \frac{p}{d} = \frac{b}{d}\]</div>Donde \\(k\\) es un entero. Este proceso se repite hasta que \\((a/d, p/d) = 1\\).
<details><summary>Ver implementación del algoritmo BSGS extendido</summary>```
function resolverBSGSExtendido(base, resultado, modulo) {
if (resultado === 1) return 0;
let coeficiente = 1;
let contador = 0;
let d;
while (true) {
d = gcd(base, modulo);
if (d === 1) break;
if (resultado % d !== 0) return "Sin solución";
modulo = Math.floor(modulo / d);
resultado = Math.floor(resultado / d);
contador++;
coeficiente = (coeficiente * Math.floor(base / d)) % modulo;
if (resultado === coeficiente) return contador;
}
const m = Math.ceil(Math.sqrt(modulo));
const tablaHash = new Map();
let valorActual = resultado;
// Pasos pequeños
for (let j = 0; j < m; j++) {
tablaHash.set(valorActual, j);
valorActual = (valorActual * base) % modulo;
}
const baseM = potenciaModular(base, m, modulo);
valorActual = coeficiente;
// Pasos grandes
for (let i = 1; i <= m; i++) {
valorActual = (valorActual * baseM) % modulo;
if (tablaHash.has(valorActual)) {
return i * m - tablaHash.get(valorActual) + contador;
}
}
return "Sin solución";
}
function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
El algoritmo BSGS es fundamental en criptografía, especialmente en sistemas que dependen de la dificultad del problema del logaritmo discreto. Es utilizado en:
- Análisis de criptosistemas basados en logaritmos discretos
- Resolución de problemas de matemática modular
- Implementación de algoritmos criptográficos como Diffie-Hellman
Implementación Completa
A continuación se presenta una implementación completa en JavaScript que incluye ambas variantes del algoritmo:
class SolucionadorLogaritmo { constructor() { this.tablaHash = new Map(); this.tamanoTabla = 0; }
limpiar() {
this.tablaHash.clear();
this.tamanoTabla = 0;
}
insertar(valor, indice) {
this.tablaHash.set(valor, indice);
this.tamanoTabla++;
}
buscar(valor) {
return this.tablaHash.has(valor) ? this.tablaHash.get(valor) : -1;
}
resolver(base, resultado, modulo) {
this.limpiar();
if (resultado === 1) return 0;
// Caso extendido cuando (base, modulo) ≠ 1
if (this.gcd(base, modulo) !== 1) {
return this.resolverExtendido(base, resultado, modulo);
}
// Caso básico cuando (base, modulo) = 1
const m = Math.ceil(Math.sqrt(modulo));
let valorActual = resultado % modulo;
// Pasos pequeños
for (let j = 0; j < m; j++) {
this.insertar(valorActual, j);
valorActual = (valorActual * base) % modulo;
}
const baseM = this.potenciaModular(base, m, modulo);
valorActual = 1;
// Pasos grandes
for (let i = 1; i <= m; i++) {
valorActual = (valorActual * baseM) % modulo;
const indice = this.buscar(valorActual);
if (indice !== -1) {
return i * m - indice;
}
}
return "Sin solución";
}
resolverExtendido(base, resultado, modulo) {
if (resultado === 1) return 0;
let coeficiente = 1;
let contador = 0;
let d;
while (true) {
d = this.gcd(base, modulo);
if (d === 1) break;
if (resultado % d !== 0) return "Sin solución";
modulo = Math.floor(modulo / d);
resultado = Math.floor(resultado / d);
contador++;
coeficiente = (coeficiente * Math.floor(base / d)) % modulo;
if (resultado === coeficiente) return contador;
}
const m = Math.ceil(Math.sqrt(modulo));
let valorActual = resultado;
// Pasos pequeños
for (let j = 0; j < m; j++) {
this.insertar(valorActual, j);
valorActual = (valorActual * base) % modulo;
}
const baseM = this.potenciaModular(base, m, modulo);
valorActual = coeficiente;
// Pasos grandes
for (let i = 1; i <= m; i++) {
valorActual = (valorActual * baseM) % modulo;
const indice = this.buscar(valorActual);
if (indice !== -1) {
return i * m - indice + contador;
}
}
return "Sin solución";
}
potenciaModular(base, exponente, modulo) {
let resultado = 1;
base = base % modulo;
while (exponente > 0) {
if (exponente % 2 === 1) {
resultado = (resultado * base) % modulo;
}
exponente = Math.floor(exponente / 2);
base = (base * base) % modulo;
}
return resultado;
}
gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
}
// Ejemplo de uso const solucionador = new SolucionadorLogaritmo(); console.log(solucionador.resolver(2, 11, 19)); // Ejemplo: 2^x ≡ 11 (mod 19)
</details></div>