4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Should be $O(\log n)$ or else it would be exponential time. $\endgroup$ – 1.. Jan 26 at 22:38
  • $\begingroup$ 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. $\endgroup$ – Bruno Feb 8 at 15:21
9
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ – 1.. Feb 9 at 12:05
  • $\begingroup$ 'at any' gives $O(\log n)$ but 'at any' doesn't. $\endgroup$ – 1.. Feb 10 at 4:59
  • 2
    $\begingroup$ 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. $\endgroup$ – Bruno Feb 10 at 11:05
  • $\begingroup$ 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. $\endgroup$ – 1.. Feb 10 at 12:20
  • 3
    $\begingroup$ 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$. $\endgroup$ – Bruno Feb 10 at 13:44
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ @EmilJeřábek, you're right, I got confused. Thank you. $\endgroup$ – D.W. Jan 26 at 22:20
  • $\begingroup$ So to get to $o(1)$ probability of certifying inequality it needs $\Omega(\log\log n)$ trials? $\endgroup$ – 1.. Jan 26 at 23:52
  • $\begingroup$ @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)$. $\endgroup$ – Emil Jeřábek Jan 27 at 15:31
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Emil Jeřábek Jan 27 at 15:37
  • $\begingroup$ 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. $\endgroup$ – 1.. Jan 27 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.