Advertisement
Published in:
2006 | OriginalPaper | Chapter
Efficient Exponentiation in GF(p m ) Using the Frobenius Map
Authors : Mun-Kyu Lee, Howon Kim, Dowon Hong, Kyoil Chung
Published in: Computational Science and Its Applications - ICCSA 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The problem of exponentiation over a finite field is to compute
A
e
for a field element
A
and a positive integer
e
. This problem has many useful applications in cryptography and information security. In this paper, we present an efficient exponentiation algorithm in optimal extension field (OEF)
GF
(
p
m
), which uses the fact that the Frobenius map, i.e., the
p
-th powering operation is very efficient in OEFs. Our analysis shows that the new algorithm is twice as fast as the conventional square-and-multiply exponentiation. One of the important applications of our new algorithm is random generation of a base point for elliptic curve cryptography, which is an attractive public-key mechanism for resource-constrained devices. We present a further optimized exponentiation algorithm for this application. Our experimental results show that the new technique accelerates the generation process by factors of 1.62–6.55 over various practical elliptic curves.