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


  [1]: http://arxiv.org/pdf/0905.1642%2522%2520/