How to judge that a Boolean polynomial cannot be divisible by another?

Question

Let $f(x),g(x)\in\mathbb{F}_2[x]$, and assume that $f(x)\nmid g(x)$, $\deg (f) \ll \deg(g)$

So how to confirm this fact $(f(x)\nmid g(x))$ as soon as possible?

Further more, is there an algorithm with $O(\deg(f)^k)$ complexity? $k\in\mathbb{N}$