Timeline for calculate function from its divizor
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 12, 2013 at 20:15 | comment | added | James Weigandt | I seem to remember that Miller's algorithm tackles the first question in a fast way. Although the algorithm is more concerned with writing a program to compute the function than expressing the function itself, it might be a good place to start. crypto.stanford.edu/miller/miller.pdf | |
| Feb 11, 2013 at 7:53 | answer | added | François Brunault | timeline score: 5 | |
| Feb 11, 2013 at 7:53 | comment | added | François Brunault | Vélu's formulas will be helpful only for divisors with special form, see my answer for a general method. | |
| Feb 9, 2013 at 18:28 | comment | added | François Brunault | 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. | |
| Feb 9, 2013 at 17:35 | comment | added | Alexey | Yes, I meant that Michael wrote | |
| Feb 9, 2013 at 17:24 | comment | added | Michael Zieve | 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))$. | |
| Feb 9, 2013 at 16:23 | comment | added | François Brunault | 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? | |
| Feb 9, 2013 at 14:22 | history | edited | Alexey |
edited tags
|
|
| Feb 9, 2013 at 11:01 | history | asked | Alexey | CC BY-SA 3.0 |