Division by $n$ in elliptic curves

Let $E/\mathbb F_{p^m}$ be an arbitrary elliptic curve over the Galois field $\mathbb F_{p^m}$, and let $$[n]^{-1}(P)\cap E(\mathbb F_{p^m})=\{Q\in E(\mathbb F_{p^m})\mid nQ=P\}.$$ Also let $N=\#E(\mathbb F_{p^m})$. Is the following claim true?

If $\gcd(n,N)=1$, then the only point in $[n]^{-1}(P)\cap E(\mathbb F_{p^m})$ is $(n^{-1} \bmod N)P$.

If this claim is evident, why are powerful programs such as the MAGMA Computational Algebra System unable to compute this point in acceptable time?

• If I understand correctly, you are asking whether multiplication by $n$ in a finite abelian group of order prime to $n$ is bijective. The answer is yes, but the question is not appropriate for this site. – abx Dec 25 '15 at 14:37
• Multiplication by $n$ is a bijection on any finite group of order prime to $n$. – jdh Dec 25 '15 at 15:47
• Voting to reopen. The question of why it takes so long to compute $Q$ is on topic. The answer is that computing $\#E$ is nontrivial (it's polynomial time but the algorithm is not obvious and the exponent of $\log p^m$ is large enough to noticeably slow the calculation). The alternative technique of solving the equations for $Q$ directly is not feasible except when $n$ is a product of small primes, because it requires finding a solution of a polynomial of degree $l^2$ for each prime factor $l \mid n$. – Noam D. Elkies Dec 25 '15 at 15:55
• Now that the question has been reopened, it should be answered by somebody who (unlike me) knows Magma well enough to tell which if either of those two explanations is correct. – Noam D. Elkies Dec 25 '15 at 19:04
• "DivisionPoints" does not seem to be defined in the package files of the Magma distribution, so we cannot see what it does. But I would assume that it tries to find all the $n$-division points of $P$ directly, without first checking (or computing) the group order. – Michael Stoll Dec 25 '15 at 21:27

Disclaimer: I am not speaking for the Magma group.

Even though Magma tries to provide the best (i.e., most efficient) algorithms, it is very hard to make sure that all possible cases are taken care of. From experiments with Magma's DivisionPoint function, it looks like the shortcut you propose is not implemented. I would recommend that you contact the Magma group and suggest to include the shortcut in the implementation. Including a link to this MO question in your message might also be helpful.

To deal with your problem right away, write your own function, e.g.,

function myDivisionPoints(pt, n)
N := #Parent(pt);
g, m := XGCD(n, N);
pt1 := m*pt;
if g eq 1 then return [pt1]; else return DivisionPoints(pt1, g); end if;
end function;

Judging from timing "N := #E;" twice in a row, Magma caches the group order after it was computed, so the first line in the function body will not recompute N every time the function is called with a point on the same curve (but just fetch the cached value).

• Dear Michael, I contacted the Magma group and explained this problem. Thanks for your good answer. – Meysam Ghahramani Dec 26 '15 at 11:45