Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

Efficient exponentiation in software and hardware
Joachim von zur Gathen, Universitaet Paderborn, Germany
Friday, September 13, 2002, at U. of Waterloo.


Efficient exponentiation is a fundamental task in several areas, including computer algebra and cryptography. Fast algorithms for this problem are presented. One of them is faster than allowed by a lower bound on the complexity of general exponentiation; the trick is a clever choice of data structure in a special situation. These methods work very well in software, and we also mention a hardware implementation on an FPGA.


Last modified on Sunday, 04 November 2012, at 15:42 hours.