Elliptic Curve Division Points

Question

There is a statement about the number of division points, which I've read in a few papers, but it never seems to have any references where it comes from or why it is true. The statement is the following:

Let $[n]$ be the multiplication-by-n map and let $Q\in E(\mathbb{\overline K})$ be a point on an elliptic curve, then there are $n^2$ points $P_i$, where $i=1,\dots,n^2$, for which it holds that $$ [n]P_i = Q. $$

I am currently working with cyclic groups on elliptic curves over finite fields, and this statement doesn't really seem to hold there, or maybe I'm just understanding it wrong. But let me make an example, and maybe you'll figure out what I'm doing wrong.

So let $$\langle A \rangle=\{A,[2]A,[3]A,[4]A,[5]A,[6]A,[7]A,O\}$$ be a cyclic group of order 8 on $E$ generated by $A$, where $O$ is the neutral element (point at infinity). If, for example, I choose $Q=[5]A$ and $n=3$, I can only find a single $P_i$ that satisfies the upper equation, namely $$ [3]P_i = [3]([7]A) = [5]A = Q. $$

My question is, where are the rest of the $n^2=9$? Can there even be 9 when my group only has eight elements? Or can these elements be in different groups? Intuitively, if they are points of the same order, they should be in the same cyclic subgroup, right? What if $\langle A\rangle$ is the largest order subgroup on $E$?

Or do you know the source/proof of this statement by any chance? The papers I have found this statement in are the following

• https://eprint.iacr.org/2010/142.pdf (second sentence in introduction)
• https://eprint.iacr.org/2010/630.pdf (section 4.1)
• https://eprint.iacr.org/2009/586.pdf (just before theorem 1 on p.2)

Thank you for any help!

Answer 1

Try with $E:y^2=x^3+x+1$ over $\Bbb{F}_5$ in http://magma.maths.usyd.edu.au/calc/

       p := 5; Fp := GF(p);
    E := EllipticCurve([Fp | 1, 1]); E;
    O := Points(E)[1]; DivisionPoints(O,3);

    #DivisionPoints(O,3);

3

    q := 5^2; Fq<a> := GF(q); E_Fq := BaseChange(E,Fq); 
    O_Fq := Points(E_Fq)[1]; DivisionPoints(O_Fq,3);

    #DivisionPoints(O_Fq,3);

9