Speed up rational point scalar multiplications on elliptic curves by Frobenius equations

Let q be a power of a prime and ϕ be the Frobenius endomorphism on \(E(\mathbb{F}_{q^k } )\), then q = tϕ − ϕ2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integers s such that q s can be represented as some very sparse ϕ-polynomial is proposed. If a Normal Basis (NB) or Optimal Normal Basis (ONB) is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about 42% to 74% less than q-ary method. For some elliptic curves, our algorithm is also faster than Muller’s algorithm. In addition, an effective algorithm is provided for finding such integer s.