Mô hình hộp đen nhóm chung có cấm MSB logarit rời rạc không?

mà tôi không chắc các mô hình Hộp đen cấm"

Điều mà mô hình Hộp đen cấm là thực hiện bất kỳ thao tác nào trên các phần tử nhóm ngoài một tập hợp thao tác cụ thể. Trong trường hợp của bạn, các hoạt động được phép sẽ là:

• Hoạt động nhóm (đã cho $A$ và $B$, trở lại $A \times B$)

• Hoạt động đảo ngược nhóm.

• So sánh hai phần tử nhóm cho bằng nhau.

• Tiên tri msbit của bạn (vì bạn đang mở rộng mô hình hộp đen để chứa thao tác này).

Bất kỳ hoạt động nào khác trên các phần tử nhóm đều bị cấm.

Mặt khác, bất kỳ hoạt động nào là những thứ không phải là yếu tố nhóm đều là trò chơi công bằng. Ví dụ: tiên tri msbit của bạn trả về một chút; bit này không phải là một phần tử nhóm và do đó, thực hiện những việc như:

 nếu (oracle_returned_a_one) {
     làm cái này();
 } khác {
     làm điều đó();
 }

đang chơi một cách hoàn hảo.

Vì vậy, trừ khi số nguyên tố ngay trên lũy thừa 2, nghĩa là, $p = 2^k + \ell$ vì $2^k / \text{polylog}(p) < \ell < 2^k$, rõ ràng là bạn có thể tính toán nhật ký rời rạc với số truy vấn đa thức (cụ thể là, $k + \text{polylog}(p)$ truy vấn)