# calculate function from its divizor

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)$?

-
The way you write $f$ is not unique. The standard form for rational functions on an elliptic curve is rather $f=f_1(x)+yf_2(x)$ for some rational functions $f_1(x),f_2(x)$. Your second question is not clear to me : can you clarify? – François Brunault Feb 9 '13 at 16:23
Presumably the second question is asking for an explicit function $H\colon\mathbb{N}\to\mathbb{N}$ such that: for any $q$ and any elliptic curve $C$ over $\mathbb{F}_q$ as in the question, every rational function $f$ on $C$ can be written as (in your version) $f=f_1(x)+y f_2(x)$ where $f_i\in\mathbb{F}_q(x)$ and $\deg(f_i)\le H(\deg(f))$. – Michael Zieve Feb 9 '13 at 17:24
Yes, I meant that Michael wrote – Alexey Feb 9 '13 at 17:35
The degree of a rational function $f$ on an elliptic curve is equal to the degree of the positive (or negative) part of its divisor. From this it is easy to get $\deg(f+g) \leq \deg(f)+\deg(g)$ which is optimal if (and only if) the set of poles of $f$ and $g$ are disjoint. Since $f_1$ is just the trace of $f$ with respect to the involution $P \mapsto -P$, we get $\deg(f_1) \leq 2\deg(f)$ and $\deg(f_2) \leq 2\deg(f)+\deg y \leq 2 \deg(f)+3$. Not sure about the best way to handle your first question, but you certainly want to have a look at Vélu's formulas. – François Brunault Feb 9 '13 at 18:28
Vélu's formulas will be helpful only for divisors with special form, see my answer for a general method. – François Brunault Feb 11 '13 at 7:53

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.

-
Dear François, I'm indeed interested in the script you mentioned in your answer, could you please put the link to the script here? That will be very helpful. Thank you in advance. – Hicham Sep 12 '13 at 9:39
Dear Hicham, I edited my answer to give the link to the Pari/GP script. – François Brunault Oct 31 '13 at 12:13