Logaritme discret

En matemàtiques, en particular en àlgebra abstracta i les seves aplicacions, els logaritmes discrets són anàlegs als logaritmes ordinaris però aplicats a un grup. En particular, un logaritme ordinari $\log _{a}(b)$ és una solució de l'equació $a^{x}=b$ sobre nombres reals o complexos. De manera similar, si $g$ i $h$ són elements d'un grup cíclic $G$, llavors d'una solució $x$ de l'equació $g^{x}=h$ se'n diu un logaritme discret en base $g$ de $h$ en el grup $G$.

Exemple

Els logaritmes discrets potser són més fàcils d'entendre en el grup multiplicatiu d'enters mòdul n Z_p)^×. Aquest és el conjunt de les Classes de congruències {1, …, p − 1} amb la multiplicació mòdul el nombre primer p.

Si es vol trobar la potència k-èsima d'un dels nombres d'aquest grup, es pot fer, trobant la seva potència k-èsima com un enter i llavors trobant el residu de dividir-lo entre p. D'aquest procés se'n diu exponenciació discreta. Per exemple, si s'agafa (Z₁₇)^×. Per a calcular 3⁴ en aquest grup, primer es calcula 3⁴ = 81, i llavors es divideix 81 entre 17, i es troba que el residu és 13. Per tant 3⁴ = 13 en el grup (Z₁₇)^×.

El logaritme discret és precisament l'operació inversa. Per exemple, si s'agafa l'equació 3^k ≡ 13 (mod 17) amb la incògnita k. Tal com s'ha vist més amunt k=4 és una solució, però aquesta no és l'única solució. Com que 3¹⁶ ≡ 1 (mod 17) això fa que si n és un enter qualsevol, llavors 3^{4+16 n} ≡ 13 x 1ⁿ ≡ 13 (mod 17). Per tant l'equació té una quantitat infinita de solucions de la forma 4 + 16n. És més, com que 16 és l'enter positiu m més petit que satisfà 3^m ≡ 1 (mod 17), és a dir 16 és l'ordre multiplicatiu de 3 en (Z₁₇)^×, aquestes són totes les solucions. De forma equivalent, la solució es pot expressar com k ≡ 4 (mod 16).

Definició

En general, sigui G un grup cíclic finit amb n elements. Se suposa que el grup s'escriu de forma multiplicativa. Sigui b un generador de G; llavors cada element g de G es pot escriure de la forma g = b^k per algun enter k. És més, qualsevol parella d'enters que representin g seran congruents mòdul n. Per tant es pot definir la funció

$\log _{b}:\ G\ \rightarrow \ \mathbf {Z} _{n}$

(on Z_n denota l'anell d'enters mòdul n) a base d'assignar a g la classe d'equivalència k mòdul n. Aquesta funció és un isomorfisme de grup, anomenat el logaritme discret en base b.

La fórmula familiar de canvi de base dels logaritmes també es compleix: Si c és un altre generador de G, llavors es té

$\log _{c}(g)=\log _{c}(b)\cdot \log _{b}(g).$

Algorismes

No es coneix cap algorisme eficient per a calcular logaritmes discrets en general $\log _{b}\;g$. L'algorisme ingenu és elevar b a potències k més i més grans fins a trobar el g desitjat. Aquest algorisme de força bruta s'anomena de vegades el mètode de multiplicació i tempteig. Aquest algorisme necessita un temps d'execució lineal amb la mida del grup G i, per tant, exponencial amb el nombre de dígits necessaris per escriure la mida del grup. Hi ha un algorisme quàntic eficient obra de Peter Shor.

Existeixen algorismes més sofisticats, normalment inspirats en algorismes per a la factorització entera. Aquests algorismes s'executen més ràpid que l'algorisme ingenu, però cap s'executa en temps polinòmic.

• Algorisme pas d'infant pas de gegant
• Algorisme rho de Pollard per al logaritme
• Algorisme lambda de Pollard
• Algorisme de Pohlig-Hellman
• Algorisme de càlcul índex
• garbell sobre el cos de nombres generalitzat
• garbell sobre cossos de funcions

Comparació amb la factorització entera

Tot i que el problema de calcular logaritmes discrets i el problema de descomposició en factors primers són problemes diferents comparteixen algunes propietats. Tots dos són computacionalment costosos (no es coneixen algorismes eficients si no és per a ordinadors quàntics), per tots dos problemes es coneixen algorismes eficients per ordinadors quàntics, els algorismes per un dels problemes sovint s'adapten per a resoldre l'altre i la dificultat de tots dos problemes s'ha fet servir per construir diversos sistemes de codificació criptogràfics.

Criptografia

El càlcul de logaritmes discrets és aparentment difícil. No només no es coneix cap algorisme eficient pel pitjor cas, sinó que fent servir l'autoreductibilitat aleatòria es pot demostrar que per al cas mitjà la complexitat és tan dura com en pitjor cas. Al mateix temps, el problema invers, l'exponenciació discreta no ho és (es pot calcular de forma eficient emprant la exponenciació binària, per exemple). Aquesta asimetria és anàloga a la que hi ha entre la factorització dels enters i la multiplicació dels enters. Les dues asimetries s'han explotat en la construcció de sistemes criptogràfics.

Eleccions molt habituals del grup G en el logaritme discret en criptografia són els grups cíclics (Z_p)^×; vegeu xifratge El Gamal, intercanvi de claus Diffie-Hellman i els algorismes de signatura digital.

Aplicacions criptogràfiques més modernes fan servir logaritmes discrets en subgrups cíclics de corbes el·líptiques sobre cossos finits; vegeu criptografia de corba el·líptica.

Bibliografia

• Crandall, Richard; Pomerance, Carl B. «5. Exponential factoring algorithms». A: Prime numbers: A Computational Perspective (en anglès). 2a edició. Springer, 2001. ISBN 978-0-387-28979-3. 
• Stinson, Douglas R. Cryptography: Theory and Practice (en anglès). 3a edició. CRC Press, 2005. ISBN 978-1584885085.