0
$\begingroup$

We have $A$, $B \in GF(q^k)$

We want to find polynomial $h \in GF(q)[x]$ where

$h(A) = B$

What is the lowest degree of $h$?

How to find $h$ with the lowest degree and what is complexity of this algorithm?

$\endgroup$
3
  • 1
    $\begingroup$ Without additional assumptions it seems impossible to find such an h; is there sum assumption on the degree of A and B? $\endgroup$
    – user9072
    Feb 18, 2013 at 19:07
  • 3
    $\begingroup$ This won't work unless $b$ is in the subfield generated by $A$. If it is, then the lowest degree is at most the degree of $B$ minus $1$, and you can find it by computing the powers of $B$ and applying linear algebra over $\mathbb F_q$, which shouldn't take too long. $\endgroup$
    – Will Sawin
    Feb 18, 2013 at 19:08
  • $\begingroup$ So, probably $O(k^w\text{poly}(\log (q) ))$. $\endgroup$ Feb 18, 2013 at 19:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.