1 | initial version |

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.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.