|
1
|
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)$? |
|||||||||||||||
|
|
2
|
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. I'm currently writing a PARI/GP script which takes as input a divisor on elliptic curve, checks if it's principal and if so outputs a rational function with this divisor. If you or other people are interested I could put the link here. 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$. |
||
|
|
