Highly parallel computations modulo a number having only small prime factors

AbstractHighly parallel algorithms computing the inverse, discrete roots, or a large power modulo a number that has only small prime factors are presented. The elaborated uniform families of Boolean circuits simultaneously achieve depth O(log n) and size O(n0(1)) for P-uniformity and depth O(log n log log n) and size O(n0(1)) for log-space uniformity