Hârtia Relația dintre ruperea protocolului Diffie-Hellman și calcularea logaritmilor discreti conține unele rezultate de interes, deși sunt oarecum tehnice.
Mai exact, are nevoie de:
Ipoteza de netezime: Pentru $n\în\mathbb{N}$, defini
$\nu(n)$ sa fie minim, peste $d\în [n-2\sqrt{n}+1, n+2\sqrt{n}+1]$ a celui mai mare factor prim al $d$.
The ipoteza de netezime este asta $\nu(n) = (\log n)^{O(1)}$.
În această setare, dacă cineva are un mic „șir de sfaturi” specific pentru $G$ (Lucrarea afirmă că avem nevoie de factorii primi mari ai $|G|$ și anumiți parametri ai curbelor eliptice --- sfatul total este de lungime $O(\log |G|)$, atunci:
Corolarul 5. Dacă ipoteza de netezime este adevărată, atunci există un algoritm generic (neuniform) în timp polinomial care calculează logaritmi discreti în grupuri ciclice de ordine $n$, efectuând apeluri către un oracol DH pentru același grup, dacă și numai dacă toți factorii primi multipli ai $n$ sunt de ordine $(\log n)^{O(1)}$.
Aici, „factori primi multipli” înseamnă puteri prime $p^e \mid n$ pentru $e > 1$.
Dacă toți factorii primi ai $n$ sunt „singuri” (de ex. $n$ este fără pătrat), se pare că se pot descurca ceva mai bine --- teorema lor 2 acoperă acest caz și pare să înlăture cerința de cunoaștere a curbelor eliptice + ipoteza de netezime (încă mai are nevoie de factorizare) și ele în mod explicit evaluează complexitatea reducerii. Nu o voi copia aici, deoarece afirmația teoremei este oarecum lungă.
Toate acestea înseamnă că, sub o anumită ipoteză teoretică a numărului, în contextul neuniform nu există nicio decalaj între DLOG și CDH.
