International Association for Cryptologic Research

International Association
for Cryptologic Research


Haining Fan


Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithm
We describe how a recently proposed way to split input operands allows for fast VLSI implementations of GF(2)[x] Karatsuba-Ofman multipliers. The XOR gate delay of the proposed multiplier is better than that of previous Karatsuba-Ofman multipliers. For example, it is reduced by about 33% and 25% for n = 2^i and n = 3^i (i > 1), respectively.
Normal Basis Multiplication Algorithms for GF(2n) (Full Version)
Haining Fan Duo Liu Yiqi Dai
In this paper, we propose a new normal basis multiplication algorithm for GF(2n). This algorithm can be used to design not only fast software algorithms but also low complexity bit-parallel multipliers in some GF(2n)s. Especially, for some values of n that no Gaussian normal basis exists in GF(2n), i.e., 8|n, this algorithm provides an alternative way to construct low complexity normal basis multipliers. Two improvements on a recently proposed software normal basis multiplication algorithm are also presented. Time and memory complexities of these normal basis multiplication algorithms are compared with respect to software performance. It is shown that they have some specific behavior in different applications. For example, GF(2571) is one of the five binary fields recommended by NIST for ECDSA (Elliptic Curve Digital Signature Algorithm) applications. In this field, our experiments show that the new algorithm is even faster than the polynomial basis Montgomery multiplication algorithm: 525 us v. 819 us.
Two Software Normal Basis Multiplication Algorithms for GF(2n)
Haining Fan Yiqi Dai
In this paper, two different normal basis multiplication algorithms for software implementation are proposed over GF(2n). The first algorithm is suitable for high complexity normal bases and the second algorithm is fast for type-I optimal normal bases and low complexity normal bases. The ANSI C source program is also included in this paper.
New GF(2n) Parallel Multiplier Using Redundant Representation
Haining Fan Yiqi Dai
A new GF(2n) redundant representation is presented. Squaring in the representation is almost cost-free. Based on the representation, two multipliers are proposed. The XOR gate complexity of the first multiplier is lower than a recently proposed normal basis multiplier when CN (the complexity of the basis) is larger than 3n-1.


Yiqi Dai (3)
Ming Gu (1)
Kwok-Yan Lam (1)
Duo Liu (1)
Jiaguang Sun (1)
Xi Xiong (1)
Jiajun Zhang (1)