Time complexity to compute f(k).

Question

Suppose that $f(x)$ is polynomial, over finite field, of degree $n$. What is the time complexity to compute $f(k)$ for a given $k$?

It would be a great help!

Thank you.

Answer 1

By Horner's method, at most $O(n)$ multiplications need to be performed. Based on the recent breakthrough, each multiplication takes time at most $O(\log q\log\log q)$ (under some plausible number theoretical assumption). Since the time needed for additions is dominated by multiplications, the complexity can be made $O(n\log q \log\log q)$ for $k\simeq\mathbb F_q$. (Note that $\log q$ is the number of bits needed to encode elements of $\mathbb F_q$.)