Me and Mystiz went for the hard way and tried recovering the curve directly. Others simply solved for a rational map from the curve to GF(p).