Сильный Диффи Хеллман в билинейных группах

$n$- сильное предположение Диффи Хеллмана о том, что для заданного подмножества $\{g, g^s,\cdots,g^{s^n}\} \subseteq \mathbb{G}$ в циклической группе $\mathbb{G}$ первого порядка $р$, алгоритм PPT не может выводить $ г ^ {\ гидроразрыва {1} {s + \ альфа}} $ для любой $\alpha \in\mathbb{F}_p$ разве что с незначительной вероятностью.

Означает ли это как-то, что ни один алгоритм PPT не может вывести неприводимый полином $f(X)\in\mathbb{F}_p[X]$ и элемент $ г ^ {\ гидроразрыва {1} {f (s)}} $? Или это влечет за собой строго более сильное предположение?

Если я понимаю ваши количественные оценки (для любого заданного неприводимого $ф(х)$, такого алгоритма не существует), то это более сильное предположение, которое вряд ли будет верным, поскольку $n$ растет. Во-первых, заметим, что если мы напишем $x_i$ за $г^{s_i}$ тогда степень (не более) $n$ многочлен $\сумма c_is^i$ дает $$g^{\sum c_is^i}=\prod x_i^{c_i}$$ как легко вычислить.

Теперь для любого многочлена $ч(х)$ степени не более $n$ мод без корней $р$, позволять $ф(х)$ быть решением $$f(x)h(x)\equiv 1\pmod {p, x^p-x}$$ затем $$g^{1/f(s)}=g^{h(s)}$$ и так можно легко вычислить. Как $n$ растет количество возможных $ч(х)$ растет, и вскоре мы будем уверены, что один из наших $ф(х)$ является неприводимым.