Logaritmo discret

En àlgebra abstracta, es coneix com logaritmo discret de i en base g, a on g i i són elements d'un grup cíclico finito G, a la solució x de l'equació g^x = i. Açò, es pot denotar matemàticament com:

$x={\log }_g(y)⟺g^x=y$

Els logaritmos discrets són anàlecs en teoria de grups als logaritmos ordinaris en anàlisis. Mentres que el càlcul de la seua inversa — la exponenciación discreta — és una tasca molt senzilla en térmens computacionals, el càlcul del logaritmo discret no és senzill en molts grups. El fet de que el problema siga «irresoluble» en un temps raonable si s'utilisa aritmètica modular fa que açò s'use en criptografia, en el método d'intercanvi de claus de Diffie-Hellman o en el sistema de ElGamal.

Eixemple

Els logaritmos discrets són potser més senzills d'entendre en el grup (Z_p)^&claves;, o siga el grup multiplicativo mòdul un primer p.

La k-ésima potencia d'un dels números en este grup pot ser calculada trobant la potencia k-ésima com un sancer i després obtenint el restant despuix de la seua divisió per p. Este procés és cridat Exponenciación modular. Per eixemple, considerant (Z₁₇)^&claves;, per a considerar 3⁴ en este grup, primer es calcula 3⁴ = 81 i despuix es dividix 81 entre 17 obtenint de restant 13. Açò és 3⁴ = 13 en el grup (Z₁₇)^&claves;. En la pràctica s'utilisa el método de l'exponenciación binaria, reduint en cada pas.

El logaritmo discret és l'operació inversa. Per eixemple, considerant l'equació 3^k ≡ 13 (mod 17) per a k. De l'eixemple de dalt, una solució és k = 4, pero esta no és l'única solució. ya que 3¹⁶ ≡ 1 (mod 17) — com indica el Menuda teorema de Fermat — , es deduïx que, si n és un sancer, llavors 3⁴⁺¹⁶ⁿ ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 &claves; 1ⁿ ≡ 13 (mod 17). Per lo tant l'equació té infinites solucions de la forma 4 + 16n. Per una atra part, com 16 és el menor número entero positiu m que complix 3^m ≡ 1 (mod 17) (en atres paraules, 16 és l'orde de 3 en (Z₁₇)^&claves;), estes són les úniques solucions. Equivalentement, el conjunt de totes les possibles solucions pot ser expressat per la restricció k ≡ 4 (mod 16).

Definició

Siga (G,·) un grup cíclico finito d'orde n — en n elements —, és dir, G={i,g,g²,...,g^n-1} per a cert element g de G. Donat h pertanyent a G existix un k pertanyent a Z tal que h = g^k. Este valor de k és el logaritmo discret de h en base g.

Més formalment, es definix:

${\log }_g:G\to \mathbb{Z}/n\mathbb{Z}$

com la funció que assigna valors de la següent manera:

${\log }_g(x)=k$ tal que $x\equiv g^k$.

Vore també

• Logaritmo
• Raïl primitiva mòdul n
• Classe d'equivalència potencial