Computing Large Polynomial Powers Very Fast in Parallel

Abstract Very fast parallel algorithms computing the inverse and large powers of polynomials over finite fields are presented provided the modulus has only small prime factors. The elaborated uniform families of Boolean circuits simultaneously achieve depth O(log n) and size O(n o(1) ) for P-uniformity and depth O(log n loglog n) and size O(n o(1) ) for log-space uniformity.

Authors

• Thomas Zeugmann

Keywords

No keywords are indexed for this paper.