Revision history [back]

I assume FF is a finite field. One approach is to randomly choose the polynomial $a$ and then try and solve for a polynomial $b$. The condition you have to meet is that for every irreducible factor $x_i$ of $a$, a root $r_i$ of $a_i$ is an $x$-coordinate of a point on the hyperelliptic curve defined over $FF(r_i)$, say with $y$-coordinate $y_i$. So the probability you choose a polynomial $a$ that works is $(1/2)^m$, where $m$ is the number of irreducible factors of $m$.

Recovering $b$ is now a matter of interpolating the points $(x_i,y_i)$ and their conjugates. Make sure to properly randomize the sign choice in the square roots that you end up taking.