New answers tagged randomized-algorithms
9
There is a linear time randomized algorithm, that is of complexity $O(\log n)$: Cf M. Kaminski, A note on probabilistically verifying integer and polynomial products, J. ACM 36(1), pp. 142–149, Jan. 1989.
The basic idea: Instead of checking $n = ab$ modulo $p$ for some random prime number $p$, check it modulo $2^i-1$ for some integer $i$. The reduction ...
Top 50 recent answers are included
