5
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ 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. $\endgroup$
    – abx
    Dec 25, 2015 at 14:37
  • 1
    $\begingroup$ Multiplication by $n$ is a bijection on any finite group of order prime to $n$. $\endgroup$
    – The Thin Whistler
    Dec 25, 2015 at 15:47
  • 8
    $\begingroup$ 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$. $\endgroup$
    – Noam D. Elkies
    Dec 25, 2015 at 15:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – Noam D. Elkies
    Dec 25, 2015 at 19:04
  • 1
    $\begingroup$ "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. $\endgroup$
    – Michael Stoll
    Dec 25, 2015 at 21:27

1 Answer 1

Reset to default
5
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dear Michael, I contacted the Magma group and explained this problem. Thanks for your good answer. $\endgroup$
    – Meysam Ghahramani
    Dec 26, 2015 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.