0
$\begingroup$

Let $f \in F_p[x] / q(x)$. I know for a fact that the inverse of $f$, $g$ exists in the field. Taking the regular inverse is easy, but I'm looking for the compositional inverse.

I'm looking for algorithms to find the inverse of $f$.

When can we find a $g(x) \in F_p[x]/q(x)$ so that $f(g(x)) =x$?

Additionally, if you know of any papers that talk about the existence of inverses that would also be useful.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Do you mean that you are looking for an algorithm to find the inverse of $f$, rather than of $g$? Also, to be clear, to you mean you want to find an inverse with respect to composition, rather than with respect to the field operation (which is multiplication)? $\endgroup$
    – Jared White
    Commented Aug 9, 2023 at 13:14
  • 1
    $\begingroup$ What is the source of your knowledge that $f$ is bijective? If this is just given to you as a black box promise, I don't see how you can do better than Lagrange interpolation. But there are only a few known classes of easily recognized permutation polynomials (see en.wikipedia.org/wiki/Permutation_polynomial ), so if your polynomial belongs to one of them, you might be able to do better. $\endgroup$
    – David E Speyer
    Commented Aug 9, 2023 at 14:04
  • 1
    $\begingroup$ EG If your polynomial is $x^3$ for $p^{\deg q} \equiv 2 \bmod 3$, then the inverse polynomial is $x^{(2 p^{\deg q} -1)/3}$. $\endgroup$
    – David E Speyer
    Commented Aug 9, 2023 at 14:06
  • 3
    $\begingroup$ It looks like there is a fair bit of literature in this area; the relevant search terms are "permutation polynomial" and "compositional inverse". $\endgroup$
    – David E Speyer
    Commented Aug 9, 2023 at 14:17
  • $\begingroup$ Question simulposted to m.se, math.stackexchange.com/questions/4750141/… in violation of rules on both sites. $\endgroup$
    – Gerry Myerson
    Commented Aug 10, 2023 at 4:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .