Abstract
Optimal sequential and parallel algorithms for exponentiation in a finite field containing F q are presented, assuming thatqth powers can be computed for free.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
G. B. Agnew, R. C. Mullin, andS. A. Vanstone, Fast exponentiation inGF(2n). InAdvances in Cryptology—EUROCRYPT'88, ed.C. G. Günther, vol. 330 ofLecture Notes in Computer Science. Springer (Berlin), 1988, 251–255.
J. Berstel andS. Brlek, On the length of word chains.Inform. Process. Lett. 26 (1987), 23–28.
T. Beth, B. M. Cook, andD. Gollmann, Architectures for exponentiation inGF(2n). InAdvances in Cryptology—CRYPTO'86, ed.A. M. Odlyzko, vol. 263 ofLecture Notes in Computer Science. Springer (Berlin), 1986, 302–310.
F. Fich andM. Tompa, The parallel complexity of exponentiating polynomials over finite fields.J. Assoc. Comput. Mach. 35 (1988), 651–667.
J. von zur Gathen, Computing powers in parallel.SIAM J. Comput. 16 (1987), 930–945.
J. von zur Gathen, Inversion in finite fields using logarithmic depth.J. Symb. Comp. 9 (1990), 175–183.
J. von zur Gathen, Processor-efficient exponentiation in finite fields. Inform. Process. Lett., to appear, 1992.
J. von zur Gathen andM. Giesbrecht, Constructing normal bases in finite fields.J. Symb. Comp. 10 (1990), 547–570.
J. von zur Gathen andG. Seroussi, Boolean circuits versus arithmetic circuits.Inform. and Comput. 91 (1991), 142–154.
P. N. Golovanov andV. I. Solodovnikov, Rapid parallel calculation of degrees in a quotient ring of polynomials over a finite field.Mathematical Notes 42 (1987), 987–992.
D. E. Knuth,The Art of Computer Programming, Vol. 2, Seminumerical Algorithms. Addison-Wesley (Reading MA), 2 edition, 1981.
Th. Lengauer and K. Mehlhorn, VLSI complexity, efficient VLSI algorithms and the HILL design system. InAlgorithmics for VLSI, ed.C. Trullemans. Academic Press, 1986, 33–89.
G. W. Reitwiesner, Binary arithmetic.Advances in computers, ed. F. L. Alt 1 (1960), 231–308.
D. R. Stinson, Some observations on parallel algorithms for fast exponentiation inGF(2n).SIAM J. Comput. 19 (1990), 711–717.
C. C. Wang, T. K. Truong, H. M. Shao, L. J. Deutsch, J. K. Omura, andI. S. Reed, VLSI architectures for computing multiplications and inverses inGF(2m).IEEE Trans. Comput. C-34 (1985), 709–717.