1
$\begingroup$

I'm reading about Hidden Field Equations Multivariate scheme. My lecture states that the central map is a univariate polynomial $$P(X)=\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}p_{ij}x^{q^i+q^j} \in K[X]$$ where $K$ is a extension field of the finite field $k=\mathbb{F}_q$ of degree $n$ and $r$ is a small constant chosen in a way such that $P(x)$ can efficiently inverted.

$r$ is a small constant chosen in a way such that $P(x)$ can efficiently inverted.

I would like an example about the last claim please.

$\endgroup$
  • 2
    $\begingroup$ I don't understand what you're asking. The question you appear to be asking can be answered by saying "Let $r=1$", which is surely not what you mean. $\endgroup$ – figlesquidge Dec 9 '13 at 18:46
  • $\begingroup$ I edit my question $\endgroup$ – juaninf Dec 9 '13 at 20:21
  • $\begingroup$ When $r$ is small, the degree of $P$ is at most $2q^{r-1}$. We assume this value is small. You can find several algorithms to find the root of P in textbooks on computer algebra or find programs implementing them; sage, pari, and so on. $\endgroup$ – xagawa Dec 10 '13 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.