Welcome to the resource topic for 2024/1906
Title:
On Efficient Computations of Koblitz Curves over Prime Fields
Authors: Guangwu Xu, Ke Han, Yunxiao Tian
Abstract:The family of Koblitz curves E_b: y^2=x^3+b/\mathbb{F}_p over primes fields has close connections 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 \tau^2 can be done more efficiently that makes the average cost of \tau to be close to 2.5\mathbf{S}+3\mathbf{M} ( \mathbf{S} and \mathbf{M} denote the costs for field squaring and multiplication, respectively); (2) the pre-computation for the window \tau-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 11\%. The paper also suggests a simplified modular reduction for Eisenstein integers where the division operations are eliminated. The efficient formula of \tau P can be further used to speed up the computation of 3P, compared to 10\mathbf{S}+5\mathbf{M} , our new formula just costs 4\mathbf{S}+6\mathbf{M}. As a main ingredient for double base chain method for scalar multiplication, the 3P formula will contribute to a greater efficiency.
ePrint: https://eprint.iacr.org/2024/1906
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .