Modelul de cutie neagră de grup generic interzice MSB de logaritm discret?

pe care nu sunt sigur că modelele Black Box îl interzic”

Ceea ce interzice modelul Black Box este efectuarea oricărei operațiuni asupra elementelor grupului, în afară de un set specific de operații. În cazul dumneavoastră, operațiunile permise ar fi:

• Operația de grup (dată $A$ și $B$, întoarcere $A \times B$)

• Operația de inversare a grupului.

• Compararea a două elemente de grup pentru egalitate.

• Oracolul dvs. msbit (pentru că extindeți modelul cutiei negre pentru a conține această operație).

Orice alte operațiuni asupra elementelor grupului sunt interzise.

Pe de altă parte, orice operațiuni sunt lucruri care nu sunt elemente de grup sunt un joc corect. De exemplu, oracolul dvs. msbit returnează un pic; acest bit nu este un element de grup, deci fac lucruri precum:

 if (oracol_returned_a_one) {
     fa asta();
 } altfel {
     fa aia();
 }

sunt perfect în joc.

Deci, cu excepția cazului în care primul este chiar peste o putere de 2, adică $p = 2^k + \ell$ pentru $2^k / \text{polylog}(p) < \ell < 2^k$, ar trebui să fie evident că puteți calcula jurnalul discret cu un număr polinom de interogări (în special, $k + \text{polilog}(p)$ întrebări)