Diffie Hellman mạnh mẽ trong các nhóm song tuyến tính

Các $n$-trạng thái giả định Diffie Hellman mạnh mẽ đã cho tập hợp con $\{g, g^s,\cdots,g^{s^n}\} \subseteq \mathbb{G}$ trong một nhóm tuần hoàn $\mathbb{G}$ theo thứ tự chính $p$, thuật toán PPT không thể xuất ra $g^{\frac{1}{s+\alpha}}$ bất cứ gì $\alpha \in \mathbb{F}_p$ ngoại trừ với xác suất không đáng kể.

Có phải bằng cách nào đó nó ngụ ý rằng không có thuật toán PPT nào có thể tạo ra một đa thức bất khả quy $f(X)\in \mathbb{F}_p[X]$ và phần tử $g^{\frac{1}{f(s)}}$? Hay điều đó đòi hỏi một giả định mạnh mẽ hơn?

Nếu tôi hiểu định lượng của bạn (đối với bất kỳ bất khả quy nhất định $f(x)$, không tồn tại một thuật toán như vậy), thì đó là một giả định mạnh hơn và khó có thể đúng như $n$ mọc. Đầu tiên, lưu ý rằng nếu chúng ta viết $x_i$ vì $g^{s_i}$ sau đó là mức độ (nhiều nhất) $n$ đa thức $\sum c_is^i$ cho $$g^{\sum c_is^i}=\prod x_i^{c_i}$$ như có thể tính toán dễ dàng.

Bây giờ cho bất kỳ đa thức $h(x)$ tối đa bằng cấp $n$ mod không root $p$, để cho $f(x)$ là một giải pháp cho $$f(x)h(x)\equiv 1\pmod {p, x^p-x}$$ sau đó $$g^{1/f(s)}=g^{h(s)}$$ và do đó có thể được tính toán dễ dàng. Như $n$ phát triển số lượng có thể $h(x)$ phát triển và chúng tôi sẽ sớm được đảm bảo rằng một trong những $f(x)$ là không thể giảm được.