There is elliptic curve $C (y^2 = x^3 + Ax + B)$ over $GF(q)$.
There is algebraic function f on C.
We have div(f).
How calculate f as rational function ( $f = (f_1(x) + yf_2(x)) / (g_1(x) + yg_2(x))$)?
What is bound $deg(f_i)$ and $deg(g_i)$ in depend of $deg(f)$?
Every principal divisor is a finite ${\bf Z}$-linear combination of divisors of the form $D=[P]+[Q]-[P+Q]-[O]$ with $P,Q \in C$. For such $D$, let $L:\lambda=0$ be the line through $P$ and $Q$.
If $P+Q=O$ then $L$ is vertical and $D={\rm div}(\lambda)={\rm div}(x-x_P)$.
If $P+Q \neq 0$ then ${\rm div}(\lambda)=[P]+[Q]+[-P-Q]-3[O]$ so that $D={\rm div}\bigl(\frac{\lambda}{x-x_{P+Q}}\bigr)$.
This method is ok if the coefficients of your divisor are reasonably small. Otherwise, you might consider using some kind of fast exponentiation. The idea is that a divisor $2N[P]$ is equivalent to $N[2P]+N[O]$ modulo the principal divisors. So you just need to compute a function $f$ such that ${\rm div} f=2[P]-[2P]-[O]$ and then compute $f^N$ by fast exponentiation. At each step the coefficient in your divisor has been divided by $2$, thus giving a logarithmic (instead of linear) number of steps.
Finally a precision on the decomposition $f=f_1(x)+yf_2(x)$ I mentioned in my comment. Since the function $x$ has degree $2$ on $C$, the degree of $f_1$ as a usual rational function is in fact $\leq \deg(f)$. A more careful analysis also shows $\deg(f_2) \leq \deg(f)$ since there is compensation when you divide by $y$.
EDIT (2013/10/31). I have written a PARI/GP script which takes as input a divisor on elliptic curve, checks if it is principal, and if so outputs a rational function with this divisor. This script can be found on my webpage.
