Proof of associativity for elliptic curve point addition: Trouble understanding lines intersecting ellipic curves lemma

236 Views Asked by At

From Elliptic Curves Number Theory and Cryptography by Washington:

$P_K^1$ is the 1-dimensional projective space.

Lemma 2.2:

Let $G(u,v)$ be a nonzero homogeneous polynomial and let $(u_0:v_0) \in P_K^1$. Then there exists an integer $k \geq 0$ and a polynomial $H(u,v)$ with $H(u_0,v_0)\neq0$ such that $G(u,v)=(v_ou-u_0v)^kH(u,v)$.

Proof: Suppose $v_0\neq 0$. Let $m$ be the degree of $G$. Let $g(u) = G(u, v_0)$. By factoring out as large a power of $u-\frac{u_0}{v_0}$ as possible, we can write $g(u)=(v_0u-u_0)^kh(u)$ for some $k$ and for some polynomial $h$ of degree $m-k$ with $h(u_0)\neq 0$. Let $H(u,v) = v^{m-k}h(u/v)$, so $H(u,v)$ is homogeneous of degree $m-k$. Then $G(u,v)=v^mg(u/v)=(v_0u-u_0v)^kH(u,v)$, as desired.

The parts I'm having trouble with are:

(1) If you can "factor out" polynomials, why bother with defining $g(u)$ by fixing $v_0$ at all? Wouldn't you be able to factor out $(v_0u-u_0v)$ from $G(u,v)$ and be done with it?

(2) Why does $h(u_0)\neq 0$? We factored out $u-\frac{u_0}{v_0}$ from the polynomial, which assumes that $u-\frac{u_0}{v_0} \neq 0$ or that $u\neq \frac{u_0}{v_0}$. I can't figure out why this is stated.

(3) How does this help us get the order to which a line intersects a curve at a point?

1

There are 1 best solutions below

0
On

The idea behind this lemma is to look for zeros of $G(u,v)$ and see how many times it's a zero at $G(u,v)$. Given $G(u,v)$ is a homogeneous polynomial, the choice of $(u_0:v_0)$ is to represent any zero for the function. The question is, how many times is it a zero?

On the $P^k_1$ projective space, when $v_0\neq 0$, we can have any number for $u_0$, essentially making a line. The only other point is $(1:0)$ which is the point at infinity. So fixing $v_0$ doesn't limit the domain of $G(u,v)$ very much, just ignores 1 point (the point at infinity). The proof thus fixes $v_0$ and defines $g(u)=G(u,v_0)$

Now notice how if $G(u_0,v_0) \neq 0$, that the lemma is trivially true since we can make $k=0$ and $H=G$. It's really only when $G(u_0,v_0) = 0$ that we have anything interesting.

$g(u)$ is a polynomial, so we can factor out any polynomials that go in evenly. $g(u_0/v_0)=0$ implies $g(u)=(u-u_0/v_0)p(u)$ where p(u) is a polynomial. If $p(u_0/v_0)=0$, we can do the same thing and get $p(u)=(u-u_0/v_0)q(u)$ where $q(u)$ is a polynomial. $g(u)=(u-u_0/v_0)p(u)=(u-u_0/v_0)(u-u_0/v_0)q(u)=(u-u_0/v_0)^2q(u)$

We keep going until we get to the point where $h'(u_0/v_0)\neq 0$, which is $k$ times and get:

$g(u)=(u-u_0/v_0)^kh'(u)=\frac{v_0^k}{v_0^k}(u-u_0/v_0)^kh'(u)=(uv_0-u_0)^kh(u)$ where $h(u)=h'(u)/v_0^k$

$h'(u_0/v_0)\neq 0$ implies that $h(u_0/v_0)\neq 0$.

$H(u,v)=v^{m-k}h(u/v)$ means that $H(u_0/v_0)=v_0^{m-k}h(u_0/v_0)$ which since $v_0\neq 0$ and $h(u_0/v_0)\neq 0$, $H(u_0/v_0)\neq 0$.

The rest of the proof goes through.

Edit: Looks like the proof in the book was in error: http://www.math.umd.edu/~lcw/ECerrata.pdf