Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657023 | Journal of Algorithms | 2005 | 17 Pages |
Abstract
Von zur Gathen proposed an efficient parallel exponentiation algorithm in finite fields using normal basis representations. In this paper we present a processor-efficient parallel exponentiation algorithm in GF(qn) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(qn) can be done in O((log2n)2/logqn) time using n/(log2n)2 processors. Hence we get a processor-time bound of O(n/logqn), which matches the best known sequential algorithm. Finally, we present an efficient on-line processor assignment scheme which was missing in von zur Gathen's algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mun-Kyu Lee, Yoonjeong Kim, Kunsoo Park, Yookun Cho,