Запрещает ли общая групповая модель черного ящика MSB дискретного логарифма?

что я не уверен, что модели Black Box запрещают"

Модель «черного ящика» запрещает выполнение любых операций над элементами группы, кроме определенного набора операций. В вашем случае разрешенными операциями будут:

• Групповая операция (данная $А$ и $В$, возвращаться $А\раз В$)

• Операция группового обращения.

• Сравнение двух групповых элементов на равенство.

• Ваш оракул msbit (потому что вы расширяете модель черного ящика, чтобы включить эту операцию).

Любые другие операции над элементами группы запрещены.

С другой стороны, любые операции, не являющиеся элементами группы, являются честной игрой. Например, ваш оракул msbit возвращает бит; этот бит не является групповым элементом, поэтому он делает такие вещи, как:

 если (oracle_returned_a_one) {
     сделай это();
 } еще {
     сделай это();
 }

отлично в игре.

Таким образом, если простое число не выше степени двойки, то есть $p = 2^k + \ell$ за $2^k / \text{polylog}(p) < \ell < 2^k$, должно быть очевидно, что вы можете вычислить дискретный журнал с полиномиальным числом запросов (в частности, $k + \text{polylog}(p)$ запросы)