Finding function field interpolation

In the previous post, I mentioned that we can efficiently find $f\in \mathbb{F}(E)$ such that

$$\mathrm{div}(f)=\sum _{i=0}^{n-1}[P_i]-n[O]$$

if given $P_i$ satisfies $\sum P_i=O$. Here are two methods to do this. You may skip the first technical writing with a simple idea.

Incremental construction

Suppose $n=2^k$ and $y(P_i)\ne 0$ for each $i$. The first method to find divisor witness is multiplying each line which interpolates $P_i$. Let $L_i^{(0)}$ be the line interpolating $P_{2i}$ and $P_{2i+1}$ for $0\le i\le n/2$. Each $L_i^{(0)}$ intersects with $E({\mathbb{F}}_q)$ at another point $P_i^{(1)}$. Now, find $L_i^{(1)}$ interpolating $-P_i^{(1)}$ and $-P_{i+1}^{(1)}$ for $0\le i\le n/4$. And, $L_i^{(1)}$ intersects at another $P_i^{(2)}$. Repeating this process, we will have $L_i^{(0)},L_i^{(1},\dots ,L_i^{(k-1)}$. Multiplying all the lines,

$$\begin{array}{rl}\mathrm{div}(\prod _{j=0}^{k-1}\prod _{i=0}^{2^{k-j-1}-1}{L}_i^{(j)})=(\sum _{i=0}^{2^k-1}[P_i]+\sum _{i=0}^{2^{k-1}-1}[P_i^{(1)}])& +(\sum _{i=0}^{2^{k-1}-1}[-P_i^{(1)}]+\sum _{i=0}^{2^{k-2}-1}[P_i^{(2)}])\\ & +\cdots +(\sum _{i=0}^1[-P_i^{(k-1)}]+[P_0^{(k)}])-3\cdot 2^k[O]\end{array}$$

Our assumption $\sum P_i=O$ implies $P_0^{(k)}=O$. To remove each $P_i^{(j)}$ and $(-P_i^{(j)})$, we divide $x-x(P_i^{(j)})$ which is the line interpolates $P_i^{(j)},(-P_i^{(j)}),O$.

Mumford representation

The main reference is Chapter 10 of Mathematics of Public Key Cryptography by Steven Galbraith. We define the notion of a semi-reduced divisor, a divisor

$$\sum _{P\in E(\mathbb{F})\mathrm{\setminus }\{O\}}{n}_P[P]-n[O]$$

is called semi-reduced if $n_Q=0$ or $1$ for $y(Q)=0$, and $n_P>0$ implies $n_{-P}=0$. Given $P_i$, we can assume $\sum [P_i]-n[O]$ is semi-reduced. If not, deleting an even number of $Q$ for $y(Q)=0$ and a pair $P,-P$ makes it semi-reduced. Later we multiply a factor $x-x(Q)$ or $x-x(P)$ since

$$\mathrm{div}(x-x(Q))=2[Q]-2[O]$$

$$\mathrm{div}(x-x(P))=[P]+[-P]-2[O]$$

Now, let

$$u(x)=\prod _{i=0}^{n-1}(x-x(P_i))$$

Then, we can construct $v(x)\in {\mathbb{F}}_q[x]$ such that $\mathrm{deg}v<n$, $v(x(P_i))=y(P_i)$, and

$$v(x{)}^2\equiv x^3+Ax+B\text{ mod }u(x)$$

I will refer to Lemma 10.3.5 in the book for the construction. Note that $gcd(u,v)=1$ since $v(x(P_i))\ne 0$ for all $i$. By the Euclidean algorithm, consider the remainder sequence starting from $u,v$.

$$(r_0=u,1,0),(r_1=v,0,1),(r_2,s_2,t_2),\dots ,(1,s_k,t_k)$$

such that $r_i=u{s}_i+b{t}_i$. In the sequence, we have $r_{l-1}$ and $r_l$ such that $\mathrm{deg}{r}_{l-1}>\frac{n}{2}$ and $\mathrm{deg}{r}_l\le \frac{n}{2}$. Then, 

$$r_l(x)=s_l(x)u(x)+t_l(x)v(x)$$

At each step, the degree increase of $t_{i+1}$ compared to $t_i$ is at most $\mathrm{deg}{r}_i-\mathrm{deg}{r}_{i-1}$. So,

$$\mathrm{deg}{t}_l\le \mathrm{deg}u-\mathrm{deg}{r}_{l-1}<\frac{n}{2}$$

The half-GCD algorithm computes $s_l(x),t_l(x),r_l(x)$ in $O(n^2\log n)$ (or $O(n{\log }^{2}n)$ with FFT) multiplications (Theorem 8.17, 8.18 in [AHU]). Say $(a,b,c)=(r_l,t_l,s_l)$. Squaring

$$bv\equiv a\text{ mod }u$$

induces

$$b^2(x^3+Ax+B)\equiv a^2\text{ mod }u$$

Consider

$$f(x,y)=a(x)-yb(x)\in \mathbb{F}(E)$$

The zeros of $f(x,y)f(x,-y)$ is either $P$ or $-P$, which have the same $x$-coordinate.

$$f(x,y)f(x,-y)=a(x{)}^2-(x^3+Ax+B)b(x{)}^2$$

is divided by $u$, so $f$ has zeros at $P_i$. It is known that the number of zeros of $f$ equals $\mathrm{deg}f$ which is defined by

$$\mathrm{deg}f=max\{2\mathrm{deg}a,2\mathrm{deg}b+3\}$$

From the above, we know that $\mathrm{deg}a\le \frac{n}{2}$ and $\mathrm{deg}b<\frac{n}{2}$. If $n=2k$ is even, then $\mathrm{deg}b\le k-1$ so

$$\mathrm{deg}f\le max\{2k,2(k-1)+3\}=n+1$$

If $n=2k+1$ is odd, then $\mathrm{deg}a\le k$ and $\mathrm{deg}b<k+\frac{2}{1}$ so

$$\mathrm{deg}f\le max\{2k,2k+3\}=n+2$$

In both cases, $\mathrm{deg}f\le n+2$. We already have $n$ zeros of $f$, so suppose we have other zeros $P,Q$ of $f$. Then,

$$\mathrm{div}(f)=\sum _{i=0}^{n-1}[P_i]+[P]+[Q]-(n+1)[O]$$

This implies that $\sum _{i=0}^{n-1}{P}_i=-P-Q=O$. So, $Q=-P$. Suppose $P\ne O$ and $b(x(P))\ne 0$. Then, $y(P)=\frac{a(x(P))}{b(x(P))}$ is uniquely determined so $Q=P=-P=O$, which is contradiction. Only possible case is $b(x(P))=0$, which implies $a(x(P))=c(x(P))=0$. So, we may divide $f$ by $(x-x(P))$ to make $\mathrm{deg}f=n$. With the assumption that have another one zero, that zero must be $O$. So, we obtained the desired $f$ automatically.