Logaritmo discreto
De Wikipedia, la enciclopedia libre
El logaritmo discreto consiste en resolver la ecuación:
- x = ay mod n
donde x, a y n son constantes e y es la incógnita que se busca.
- y = log disca(x)
Es clara la similitud de esta ecuación con la ecuación del logaritmo. Sin embargo, el uso de aritmética modular introduce una complejidad grande al problema. Por esta complejidad el logaritmo discreto es empleado en criptografía, siendo la base de algoritmos como ElGamal y DSA.
Veamos más en detalle
Dado x, 0 < x < p, existe un único y, 0 <= y <= p-2, tal que:
x ≡ ay (mod p)
y a es una raíz primitiva (mod p)
