Is there a linear time algorithm for integer multiplication verification?
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.