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) \neq 0$ for each $i$. The first method to find divisor witness is multiplying each line which interpolates $P_i$. Let $L^{(0)}_i$ be the line interpolating $P_{2i}$ and $P_{2i+1}$ for $0\leq i \leq n/2$. Each $L^{(0)}_i$ intersects with $E(\mathbb{F}_q)$ at another point $P^{(1)}_i$. Now, find $L^{(1)}_i$ interpolating $-P^{(1)}_i$ and $-P^{(1)}_{i+1}$ for $0\leq i \leq n/4$. And, $L^{(1)}_i$ intersects at another $P^{(2)}_i$. Repeating this process, we will have $L^{(0)}_i, L^{(1}_i, \ldots, L^{(k-1)}_i$. Multiplying all the lines,
$$\begin{align*} \mathrm{div}(\prod_{j=0}^{k-1} \prod_{i=0}^{2^{k-j-1}-1} L^{(j)}_i) = \left( \sum_{i=0}^{2^k-1} [P_i] + \sum_{i=0}^{2^{k-1}-1} [P^{(1)}_i] \right) &+ \left( \sum_{i=0}^{2^{k-1}-1} [-P^{(1)}_i] + \sum_{i=0}^{2^{k-2}-1} [P^{(2)}_i] \right) \\ &+ \cdots + \left( \sum_{i=0}^{1} [-P^{(k-1)}_i] + [P^{(k)}_0] \right) - 3 \cdot 2^k [O] \end{align*}$$
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})\backslash \{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} \left( x-x(P_i) \right)$$
Then, we can construct $v(x) \in \mathbb{F}_q[x]$ such that $\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)) \neq 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), \ldots, (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 $\deg r_{l-1} > \frac{n}{2}$ and $\deg r_l \leq \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 $\deg r_i - \deg r_{i-1}$. So,
$$\deg t_l \leq \deg u - \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
$$b v \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 $\deg f$ which is defined by
$$\deg f = \max \{ 2 \deg a , 2 \deg b + 3 \}$$
From the above, we know that $\deg a \leq \frac{n}{2}$ and $\deg b < \frac{n}{2}$. If $n = 2k$ is even, then $\deg b \leq k-1$ so
$$\deg f \leq \max \{2k, 2(k-1)+3 \} = n+1$$
If $n = 2k+1$ is odd, then $\deg a \leq k$ and $\deg b < k + \frac{2}{1}$ so
$$\deg f \leq \max \{ 2k, 2k +3 \} = n+2$$
In both cases, $\deg f \leq 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 \neq O$ and $b(x(P)) \neq 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 $\deg f = n$. With the assumption that have another one zero, that zero must be $O$. So, we obtained the desired $f$ automatically.
댓글
댓글 쓰기