Compute a polynomial with a specific root by composing a set of other polynomials

Question

Let $G$ be a finite field. and let $S = \{f | f ∈ G[X]\}$ where $S$ is a finite set and the degree of any polynomial in $S$ is at most $n$. Is there a way to compute a polynomial $F = f_1 ∘ f_2 ∘ ... ∘ f_{k-1} ∘ f_k$ where $f_i ∈ S$ for $i=1,k$ such that $F(c) = 0$ where $c$ and $S$ and the structure of a given group $G$ are given?

Answer 1

I think you mean: you are given a finite subset $S$ of $G[X]$, $c \in G$, and positive integer $k$, and you want to find, if possible, $f_1, \ldots, f_k \in S$ such that $f_1 \circ \ldots \circ f_k(c) = 0$.

Consider the directed graph whose vertices are the members of $G$, with an arc $x \to y$ if $f(x) = y$ for some $f \in S$. Then such $f_1, \ldots, f_k$ exist if and only if there is a path of length $k$ starting at $c$ and ending at $0$. Moreover, if $c=x_0, x1, \ldots, x_k = 0$ is such a path, you can take $f_i$ to be a member of $S$ such that $f_i(x_{i-1}) = x_i$. Breadth-first search is an efficient way to find such a path, if it exists.