0

I'm busy self-studying Schoof's algorithm from Andrew Sutherland's notes.

In section 9.6, he states that when we happen to find some factor $g$ of the division polynomial $\psi_\ell$, then the roots of $g$ must be the $x$-coordinates of points in the kernel of some endomorphism $\alpha$.

How could we justify that such an endomorphism exists, and can we say what $\alpha$ would look like (besides simply having a factor $1 / g$ in one of its components)?

Watson
  • 23,793
gerardlouw
  • 456
  • The points $P=(x,y)$ such that $\psi_\ell(x)=0$ are $\ell$-torsion points of the curve $E$. So they are in the kernel of the endomorphism $[\ell]:E\to E$ at least. – Jyrki Lahtonen Jul 20 '16 at 12:12
  • It seems that the author is actually assuming more about the roots of $g$, specifically he seems to be assuming that if $g(x) = 0$ for some $P = (x, y)$, then $g(x') = 0$ for all $(x', y') \in \langle P \rangle$. – gerardlouw Jul 20 '16 at 12:23
  • This would of course follow if $g(x) = 0$ for all $(x, y) \in \ker(\alpha)$, but that would require constructing a different $\alpha$ than $[\ell]$, i.e. some $\alpha$ which only has $\ell$ of the $\ell$-torsion points in its kernel. – gerardlouw Jul 20 '16 at 12:28

1 Answers1

1

Answering my own question.

Turns out the $\alpha$ referred to in the notes is exactly the endomorphism which we are trying to reduce mod $\psi_\ell$, although it isn't made very clear.

Explanation: Let $\alpha = (\alpha_x(x), \alpha_y(x) y)$ be an endomorphism in $\text{End}(E)$, where $\alpha_x$ and $\alpha_y$ are rational functions. If the denominator of either $\alpha_x$ or $\alpha_y$ has a non-trivial common factor $g$ with $\psi_\ell$, this means that there is some point $P \in E[\ell]$ for which $\alpha(P) = 0$. Why? Well, writing $\alpha$ in its projective form would allow us to clear denominators, thus leaving the $Z$-component of $\alpha$ with the factor $g$, so that we would necessarily get $\alpha(P) = (0 : 1 : 0)$.

gerardlouw
  • 456