Tôi nghĩ rằng tất cả đều có thể xảy ra với điều kiện là các xác suất là độc lập/không tương quan với các bit cao của logarit rời rạc.
Hãy xem xét một tiên tri thuật toán loại 1 trong đó xác suất thành công là khoảng 1 trên một triệu. Cho một vấn đề logarit rời rạc $y=g^x$ (được cho $y$ tìm thấy $0\le x<\ell$) chúng ta có thể đưa ra giả định về 4 bit dưới cùng của $x$ bằng cách lặp lại 16 lần. Điều này sẽ làm cho bài toán của chúng ta tương đương với việc giải $y'=g^{[x/16]}$ và các bit của $[x/16]$ là các bit của $x$ dịch chuyển xuống 4. Như thường lệ, chúng tôi phục hồi logarit rời rạc theo từng bit và dịch chuyển. Để phục hồi bit thấp của $[x/16]$ chúng tôi chọn một vài triệu ngẫu nhiên $r$ trong phạm vi $[0,\ell-\ell/16]$ và chạy thuật toán của chúng tôi trên $y'g^r$ (có logarit rời rạc $0\le [x/16]+r<\ell$. Chúng tôi hy vọng sẽ thành công ít nhất một lần và ít nhất $[x/16]$ sẽ là bit được trả về bởi thuật toán XOR của chúng tôi với bit ít quan trọng nhất $r$. Rửa sạch; nói lại.
Tương tự như vậy đối với thuật toán loại 2 với xác suất, giả sử, 0,501, chúng tôi xây dựng tương tự $y'$ và một lần nữa lấy mẫu, giả sử 100 triệu $r$. Chúng tôi nhận được 100 triệu dự đoán cho phần ít quan trọng nhất $[x/16]$ trong đó khoảng 50.100.000 đúng và khoảng 49.900.000 sai cơ hội nhận được nhiều dự đoán sai hơn dự đoán đúng là rất nhỏ. Rửa sạch; nói lại.
Trong cả hai trường hợp, đầu vào của thuật toán giả định được chọn thống nhất từ một tập hợp lớn các phần tử (bao gồm hầu hết nhóm của chúng tôi) có logarit rời rạc nằm trong một khoảng cụ thể. Trừ khi sức mạnh thuật toán của chúng tôi tập trung vào các phần tử bên ngoài các tập hợp như vậy, chúng tôi sẽ có thể khôi phục logarit rời rạc đầy đủ.
