There is a quadratic randomized algorithm for matrix product verification.
Is there a similar trick to 'verify given three integers $n,a,b$ if $n=ab$ holds?' in $O(\log n)$ time?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityThere is a quadratic randomized algorithm for matrix product verification.
Is there a similar trick to 'verify given three integers $n,a,b$ if $n=ab$ holds?' in $O(\log n)$ time?
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 modulo $2^i-1$ is fast (faster than modulo a prime $p$) since only additions are required. And if you take $i = O(\log^{1-\epsilon} n)$, the computation of $(a\bmod 2^i-1)(b\bmod 2^i-1)$ can be done in (sub)linear time. Kaminski proves that if $n\neq ab$, $n\not\equiv ab\bmod 2^i-1$ with high probability.
Yes. One algorithm is: pick a random $k$-bit prime $p$; reduce $n,a,b$ modulo $p$, and then check whether $n \equiv ab \pmod p$. The chance of failing to detect an error is exponentially small in $k$, and the running time is something like $O(k \log n)$ (can probably be reduced to something like $O((\log k)(\log n))$ in theory by using efficient multiplication/division algorithms).