The CREW PRAM complexity of modular inversion
Given relatively prime \(x\) and \(M\) with \(1\leq x<M\), we are to compute a \(y\) satisfying \(1\leq y<M\) and \(x\cdot y \equiv 1 \bmod M\). The goal of the present paper is to determine a lower bound for the complexity of this problem in terms of \(n\), the number of bits of \(M\), using the CREW PRAM model, i.e., a parallel random access machine that allows concurrent read access but only exclusive write access to a memory location. The authors succeed in proving a lower bound \(\Omega(\log n)\) for odd square-free \(M\) that satisfy the inequality \[ \omega(M)\leq 0.49 \ln M/\ln\ln M, \] where \(\omega(M)\) denotes the number of distinct prime divisors of \(M\). This yields an infinite sequence of moduli \(M\) for which the known upper bound is matched up to a constant factor. The proof is based on estimates for exponential sums. For the entire collection see [Zbl 0889.00032].
This page was built for publication: The CREW PRAM complexity of modular inversion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3839011)