The last word on the second question is this [paper of Couveignes and Lercier.][1] The question is highly nontrivial.


  [1]: http://arxiv.org/abs/0905.1642