Why does 4 | E(K) for Montgomery curves?

Question

Given a Montgomery curve over some finite field $K$ in the form $E/K: by^2 = x^3 + ax^2 + x$ and using $E(K)$ for the $K$-rational points. I've just read that the number of points in $E(K)$ is always divisible by 4.

This is from crypto and usually it is assumed that $\operatorname{char}(K) \neq 2$ and $\neq 3$. In this specific case we also have $K = \mathbb{F}_{p^2}$ for some prime $p$.

Can somebody tell me why this is the case or if I have overlooked something?

Answer 1

Quoting from: Montgomery: Speeding the Pollard and Elliptic Curve Methods of Factorization, Mathematics of Computation, Volume 48. Number 177, January 1987, pages 243–264:

[p. 260:] $$\tag{10.3.1.1} By^2 = x^3 + Ax^2 + x$$ [p. 262:]

Let $p$ be a prime which does not divide $B(A + 2)(A - 2)$. Suyama [31] observes that the order of the group associated with $(10.3.1.1)$ modulo $p$ will always be divisible by $4$. If $B(A + 2)$ is a quadratic residue, then the point $(1, \sqrt{(A + 2)/B})$ has order $4$. If $B(A - 2)$ is a quadratic residue, then the point $(-1, \sqrt{(A - 2)/B})$ has order $4$. If $(A + 2)(A - 2)$ is a quadratic residue, then the cubic has three linear factors, and again there is a subgroup of order $4$.

[p. 264:]

31. Hiromi Suyama, "Informal preliminary report (8)," 25 Oct. 1985

For easier understanding, note that:

• Doubling the mentioned points of order $4$ gives the point $(0,0)$ of order $2$.
• The discriminant of the cubic's quadratic factor is $A^2-4$.
• If the cubic has three linear factors, then the three roots correspond to points of order $2$ which generate a subgroup isomorphic to $\mathbb{Z}_2\times\mathbb{Z}_2$.

Following the quoted snippet, further conditions are mentioned, given by Suyama, ensuring the existence of points of order $3$, hence of group order divisible by $12$.