Computing the trace of an algebraic point on an elliptic curve (Q6056564)

In this paper the authors present an efficient algorithm to compute the trace of an \(L\)-rational point of an elliptic curve defined over \(K\), where \(L\) is a finite field extension of \(K\). Their algorithm is more efficient than an algorithm that naively computes the splitting field of the minimal polynomial associated with the point whose trace is being computed. The authors have already implemented their proposed algorithm which is distributed in the latest version of PARI/GP. The algorithm assumes that the fields are computable and that the field extension \(L\) is simple with a known primitive element. First, the authors propose an algorithm for the case when the finite field extension \(L/K\) is separable. They then show that the algorithm can easily be extended to compute the trace for a general finite field extension; If the inseparable degree is not trivial, we know that the characteristic of \(L\) is some prime number \(p\). In this case, the inseparable degree is some power of \(p\), say \(p^d\). The extended algorithm simply returns the trace of the \(p^d\) multiple (in the sense of elliptic curve arithmetic) of the given point. The time complexity of the algorithms proposed is dominated by the computation of a matrix kernel, computation of a minimal polynomial and the arithmetic of the ground field \(K\) and its polynomials. Thus, the time complexity is at worst polynomial in terms of \([L:K]\). The authors provide examples for when \(K\) is a finite field, when \(K\) is an algebraic number field, and when \(K\) is the field of rational functions over a finite field.