Paper 2024/1906

On Efficient Computations of Koblitz Curves over Prime Fields

Abstract

The family of Koblitz curves $E_b:y^2=x^3+b/{\mathbb{F}}_p$ over primes fields has notable applications and is closely related to the ring $\mathbb{Z}[\omega ]$ of Eisenstein integers. Utilizing nice facts from the theory of cubic residues, this paper derives an efficient formula for a (complex) scalar multiplication by $\tau =1-\omega$. This enables us to develop a window $\tau$-NAF method for Koblitz curves over prime fields. This probably is the first window $\tau$-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.