Strong Diffie Hellman în grupuri biliniare

The $n$-puternicul Diffie Hellman afirmă că dat fiind submulțimea $\{g, g^s,\cdots,g^{s^n}\} \subseteq \mathbb{G}$ într-un grup ciclic $\mathbb{G}$ de ordin prim $p$, un algoritm PPT nu poate ieși $g^{\frac{1}{s+\alpha}}$ pentru orice $\alpha \in \mathbb{F}_p$ cu excepția unei probabilități neglijabile.

Implică cumva că niciun algoritm PPT nu poate scoate un polinom ireductibil $f(X)\in \mathbb{F}_p[X]$ și elementul $g^{\frac{1}{f(s)}}$? Sau asta implică o presupunere strict mai puternică?

Dacă vă înțeleg cuantificările (pentru orice ireductibil dat $f(x)$, nu există un astfel de algoritm), atunci este o presupunere mai puternică și una care este puțin probabil să fie adevărată ca $n$ dezvoltă. În primul rând, rețineți că dacă scriem $x_i$ pentru $g^{s_i}$ apoi gradul (cel mult) $n$ polinom $\sum c_este^i$ dă $$g^{\sum c_is^i}=\prod x_i^{c_i}$$ la fel de uşor de calculat.

Acum pentru orice polinom $h(x)$ de grad cel mult $n$ fara radacini mod $p$, lăsa $f(x)$ fi o solutie la $$f(x)h(x)\equiv 1\pmod {p, x^p-x}$$ Atunci $$g^{1/f(s)}=g^{h(s)}$$ și astfel se poate calcula cu ușurință. La fel de $n$ crește numărul de posibile $h(x)$ crește și în curând ni se va garanta că unul dintre noi $f(x)$ este ireductibil.