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?



Division by $n$ in elliptic curves
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](http://magma.maths.usyd.edu.au/magma/contact/) 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).


