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?
 A: 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).
