Cred că totul ar trebui să fie posibil cu condiția ca probabilitățile să fie independente/necorelate cu biții înalți ai logaritmului discret.
Luați în considerare un oracol de algoritm de tip 1 în care probabilitatea de succes este, să zicem, de aproximativ 1 la un milion. Având în vedere o problemă de logaritm discret $y=g^x$ (dat $y$ găsi $0\le x<\ell$) putem face o presupunere, să zicem, cei 4 biți de jos ai $x$ prin repetarea de 16 ori. Acest lucru va face problema noastră echivalentă cu rezolvarea $y'=g^{[x/16]}$ și bucățile de [x/16]$ sunt bucăți de $x$ deplasat în jos cu 4. Ca de obicei, recuperăm logaritmul discret pe biți și deplasăm. Pentru a recupera partea scăzută a [x/16]$ alegem câteva milioane la întâmplare $r$ în intervalul $[0,\ell-\ell/16]$ și rulați algoritmul nostru $y'g^r$ (care are logaritm discret $0\le [x/16]+r<\ell$. Ne așteptăm să reușim cel puțin o dată și puțin de [x/16]$ va fi bitul returnat de algoritmul nostru XOR cu bitul cel mai puțin semnificativ de $r$. clătiți; repeta.
La fel pentru un algoritm de tip 2 cu probabilitate, să zicem, 0,501 construim același $y'$ și din nou eșantionează, să zicem 100 de milioane $r$. Obținem 100 de milioane de predicții pentru cel mai puțin semnificativ [x/16]$ dintre care aproximativ 50.100.000 sunt corecte și aproximativ 49.900.000 sunt incorecte, șansa de a obține mai multe predicții incorecte decât cele corecte este foarte mică. clătiți; repeta.
În ambele cazuri, intrările la algoritmul presupus sunt selectate uniform dintr-un set mare de elemente (care acoperă cea mai mare parte a grupului nostru) ai căror logaritmi discreti se află într-un anumit interval. Cu excepția cazului în care puterea algoritmului nostru este concentrată pe elemente din afara unor astfel de mulțimi, ar trebui să putem recupera întregul logaritm discret.
