Giấy Mối quan hệ giữa việc phá vỡ giao thức Diffie-Hellman và tính toán logarit rời rạc chứa một số kết quả đáng quan tâm, mặc dù chúng hơi mang tính kỹ thuật.
Cụ thể, nó cần:
Giả định độ mịn: Vì $n\in\mathbb{N}$, định nghĩa
$\nu(n)$ là tối thiểu, hơn $d\in [n-2\sqrt{n}+1, n+2\sqrt{n}+1]$ của thừa số nguyên tố lớn nhất của $d$.
Các giả định êm dịu đó là $\nu(n) = (\log n)^{O(1)}$.
Trong cài đặt này, nếu một người có một số "chuỗi lời khuyên" nhỏ dành riêng cho $G$ (bài báo nói rằng người ta cần các thừa số nguyên tố lớn của $|G|$ và một số thông số nhất định của đường cong elip --- tổng chiều dài $O(\log |G|)$, sau đó:
Hệ quả 5. Nếu giả định về độ trơn là đúng, thì tồn tại một thuật toán tổng quát thời gian đa thức (không đồng nhất) tính toán các logarit rời rạc trong các nhóm thứ tự tuần hoàn $n$, thực hiện các cuộc gọi đến một nhà tiên tri DH cho cùng một nhóm, khi và chỉ khi tất cả các thừa số nguyên tố của $n$ theo thứ tự $(\log n)^{O(1)}$.
Ở đây, "nhiều thừa số nguyên tố" có nghĩa là lũy thừa nguyên tố $p^e \mid n$ vì $e > 1$.
Nếu tất cả các thừa số nguyên tố của $n$ là "độc thân" (ví dụ: $n$ là không bình phương), có vẻ như họ có thể làm tốt hơn một chút --- định lý 2 của họ giải quyết trường hợp này và dường như loại bỏ yêu cầu về kiến thức về các đường cong elliptic + giả định về độ trơn (người ta vẫn cần phân tích thành thừa số), và họ rõ ràng đánh giá độ phức tạp của việc giảm. Tôi sẽ không sao chép nó ở đây, vì phát biểu của định lý hơi dài.
Tất cả điều này để nói rằng theo một giả định lý thuyết số nhất định, trong cài đặt không đồng nhất, không có khoảng cách giữa DLOG và CDH.
