4
$\begingroup$

Consider an elliptic curve $E: y^2 = x^3 + ax + b$ over some finite field $F_{q^k}$ and a point $P$ on $E$ of order $n$.

Miller's algorithm tells us how to efficiently construct a rational function $f_{n,P}(x,y)$ on $E$ with divisor $div f = n [P] - n [\mathcal{O}]$.

I have worked through examples and exercises and have understood how and why Miller's algorithm works.

But I cannot answer the following question: Why can't we just take $f_{n,P} = (y-y_P)^n$? It obviously has an $n^{\rm th}$ order root at $P$ and $n^{\rm th}$ order pole at $\mathcal{O}$. It's also obvious that it doesn't have any other poles or roots, because only the point $P$ has $y$-coordinate $y_P$. What am I missing?

$\endgroup$
4
$\begingroup$

Every statement you've claimed is "obvious" is false at least some of the time.

First, $y-y_P$ does not have a zero of order $1$ at $P$ for some choices of $P$. For instance, for any point $P$ with horizontal tangent line, $y-y_P$ vanishes to order two at $P$. Next, $y-y_P$ has a pole of order three at $O$: the line $V(Y-y_PZ)$ has three points of intersection with your elliptic curve away from $Z=0$; the line $V(Z)$ has a triple intersection at $O$; thus their ratio has a triple pole at $O$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.