# Is there a linear time algorithm for integer multiplication verification?

Is there a similar trick to 'verify given three integers $$n,a,b$$ if $$n=ab$$ holds?' in $$O(\log n)$$ time?

• Should be $O(\log n)$ or else it would be exponential time. – 1.. Jan 26 at 22:38
• I am a bit surprised by the downvotes. This question appears very natural to me, and my impression is that Kaminski's result (cf my answer) is not very well-known. – Bruno Feb 8 at 15:21

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.

• It still seems we require $(\log n)(f(n))$ at an $f(n)\in\omega(1)$ (might be at any $f(n)\in\omega(1)$) to achieve $1-o(1)$ probability of success. So to achieve $1-o(1)$ error there is no $O(\log n)$ complexity algorithm? – 1.. Feb 9 at 12:05
• 'at any' gives $O(\log n)$ but 'at any' doesn't. – 1.. Feb 10 at 4:59
• No, Kaminski's algorithm has a probability of failure $1/n^{O(1)}$, not a constant probability. What is not yet known is whether there exists a deterministic linear-time algorithm. – Bruno Feb 10 at 11:05
• Probability of success of $1-\frac{\mathsf{polylog}(n)}{n}$ on a single trial is deterministic $O(\log n)$. But if it were even $1-\frac{2^{\mathsf{polyloglog(n)}}}{n}$ it would not be. So it depends on what $O(1)$ is. If error $\geq\frac{1}{n^{O(1)}}$ means error $\geq\frac{2^{\mathsf{polyloglog}(n)}}{n}$ we would require $\omega(\log n)$ randomized trials. So randomized in $O(\log n)$ would itself be unsolved. – 1.. Feb 10 at 12:20
• I cannot make any sense of what you write. If this is the question, no we don't know any $O(\log n)$ algorithm with error probability smaller than $1/n^{O(1)}$, for instance error $1/2^n$. – Bruno Feb 10 at 13:44

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).

• @EmilJeřábek, you're right, I got confused. Thank you. – D.W. Jan 26 at 22:20
• So to get to $o(1)$ probability of certifying inequality it needs $\Omega(\log\log n)$ trials? – 1.. Jan 26 at 23:52
• @1.. No. First, $k$ needs to be at least about $\log\log n$ so that the probability of error is $<1$ in the first place. But after that, the probability is $O(2^{-k}\log n)$, thus $k=\log\log n+O(1)$ is enough to get the probability down to, say, $1/2$, in which case $\omega(1)$ trials will make the probability $o(1)$; and if $k=\log\log n+\omega(1)$, a single trial will already give probability $o(1)$. – Emil Jeřábek Jan 27 at 15:31
• By the way, it is simpler to do the test modulo arbitrary random $k$-bit numbers rather than just primes. Then one doesn’t have to bother with primality testing, rejection sampling, etc. Again, $k$ needs to be above roughly $\log\log n$, and then the error is something like $\rho(k/\log\log n)$, where $\rho$ is the Dickman function. In particular, $k\sim c\log\log n$ for a constant $c>1$ will give error probability bounded away from $1$, and $k=\omega(\log\log n)$ will give $o(1)$. – Emil Jeřábek Jan 27 at 15:37
• Is there a similar complexity derandomization? What is the best derandomization we know? Randomized time complexity is $O((\log n)(\log\log\log n)f(n))$ at any $f(n)\in\omega(1)$ which is faster compared to complexity of integer multiplication. – 1.. Jan 27 at 17:04