Paper 2024/1906

On Efficient Computations of Koblitz Curves over Prime Fields

Abstract

The family of Koblitz curves $$ over primes fields has notable applications and is closely related to the ring $$ of Eisenstein integers. Utilizing nice facts from the theory of cubic residues, this paper derives an efficient formula for a (complex) scalar multiplication by $$. This enables us to develop a window $$-NAF method for Koblitz curves over prime fields. This probably is the first window $$-NAF method to be designed for curves over fields with large characteristic. Besides its theoretical interest, a higher performance is also achieved due to the facts that (1) the operation $$ can be done more efficiently that makes the average cost of $$ to be close to $$ ( $$ and $$ denote the costs for field squaring and multiplication, respectively); (2) the pre-computation for the window $$-NAF method is surprisingly simple in that only one-third of the coefficients need to be processed. The overall improvement over the best current method is more than $$. The paper also suggests a simplified modular reduction for Eisenstein integers where the division operations are eliminated. The efficient formula of $$ can be further used to speed up the computation of $$, compared to $$ , our new formula just costs $$. As a main ingredient for double base chain method for scalar multiplication, the $$ formula will contribute to a greater efficiency.