<p>Yes.  One algorithm is: pick a random <span class="math-container">$k$</span>-bit prime <span class="math-container">$p$</span>; reduce <span class="math-container">$n,a,b$</span> modulo <span class="math-container">$p$</span>, and then check whether <span class="math-container">$n \equiv ab \pmod p$</span>.  The chance of failing to detect an error is exponentially small in <span class="math-container">$k$</span>, and the running time is something like <span class="math-container">$O(k \log n)$</span> (can probably be reduced to something like <span class="math-container">$O((\log k)(\log n))$</span> in theory by using efficient multiplication/division algorithms).</p>

CC BY-SA 4.0
2021-01-26T23:52:55.867Z
So to get to $o(1)$ probability of certifying inequality it needs $\Omega(\log\log n)$ trials?
Turbo
CC BY-SA 4.0
2021-01-27T15:31:55.260Z
@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
CC BY-SA 4.0
2021-01-27T15:37:29.617Z
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](https://en.wikipedia.org/wiki/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
CC BY-SA 4.0
2021-01-27T17:04:53.883Z
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.
Turbo
CC BY-SA 4.0
2021-01-26T20:38:15.133Z
2021-01-26T22:20:33.360Z
2021-01-26T22:20:33.360Z
D.W.
<p>There is a linear time randomized algorithm, that is of complexity <span class="math-container">$O(\log n)$</span>: <em>Cf</em> M. Kaminski, <a href="https://dl.acm.org/doi/abs/10.1145/58562.214082" rel="nofollow noreferrer">A note on probabilistically verifying integer and polynomial products</a>, J. ACM 36(1), pp. 142–149, Jan. 1989. Actually, two such algorithms are provided.</p>
<h5>First algorithm</h5>
<p>The standard algorithm of checking <span class="math-container">$n = ab\bmod p$</span> for some prime <span class="math-container">$p$</span> with <span class="math-container">$O(\log ℓ)$</span> bits, where <span class="math-container">$ℓ = \log n$</span>, actually runs in linear time. This is due to <a href="https://dl.acm.org/doi/abs/10.1145/31846.31850" rel="nofollow noreferrer">another algorithm of Kaminski</a> that allows to compute <span class="math-container">$n\bmod p$</span> in <span class="math-container">$O(ℓ)$</span> bit operations. (Note that this reduction algorithm is far from obvious, and only sketched in the reference.) Therefore, the algorithm is:</p>
<ol>
<li>First find a <span class="math-container">$O(\log ℓ)$</span>-bit prime <span class="math-container">$p$</span> in <span class="math-container">$\log^{O(1)}(ℓ)$</span> bit operations;</li>
<li>Compute <span class="math-container">$n_p=n\bmod p$</span>, <span class="math-container">$a_p=a\bmod p$</span> and <span class="math-container">$b_p=b\bmod p$</span> in <span class="math-container">$O(ℓ)$</span> bit operations;</li>
<li>Check whether <span class="math-container">$n_p = a_pb_p\bmod p$</span> in <span class="math-container">$\log^{O(1)}(ℓ)$</span> bit operations.</li>
</ol>
<p>The algorithm fails if <span class="math-container">$n≠ ab$</span> but <span class="math-container">$p$</span> divides <span class="math-container">$n-ab$</span>: Since this is a <span class="math-container">$O(ℓ)$</span>-bit integer, it has at most <span class="math-container">$O(ℓ)$</span> prime divisors. If we uniformly sample a <span class="math-container">$O(\log ℓ)$</span>-bit prime, the probability that is divides <span class="math-container">$n-ab$</span> is constant. Therefore, the algorithm has a constant probability of success, that can be amplified using repetition.</p>
<h5>Second algorithm</h5>
<p>This is the main algorithm described in the paper. The basic idea is to replace the prime number <span class="math-container">$p$</span> in the first algorithm by some random integer <span class="math-container">$2^i-1$</span> where <span class="math-container">$i = O(ℓ^{1-ε})$</span> for some <span class="math-container">$ε\in (0,½)$</span>. The algorithm becomes:</p>
<ol>
<li>Take a random integer <span class="math-container">$i = O(ℓ^{1-ε})$</span> in <span class="math-container">$O(ℓ^{1-ε})$</span> bit operations;</li>
<li>Compute <span class="math-container">$n_i = n\bmod 2^i-1$</span>, <span class="math-container">$a_i = a\bmod 2^i-1$</span> and <span class="math-container">$b_i=b\bmod 2^i-1$</span> in <span class="math-container">$O(ℓ)$</span> bit operations;</li>
<li>Check whether <span class="math-container">$n_i = a_ib_i\bmod 2^i-1$</span> in <span class="math-container">$(ℓ^{1-ε})^{O(1)}$</span> bit operations.</li>
</ol>
<p>Kaminski proves that if <span class="math-container">$0&lt;ε&lt;½$</span>, this algorithm is correct with good probability. Note though that for this algorithm to run in <span class="math-container">$O(ℓ)$</span> bit operations, one needs <span class="math-container">$(ℓ^{1-ε})^{O(1)}$</span> to be <span class="math-container">$O(ℓ)$</span> in step 3. This means that the product cannot be performed naively in quadratic time (since <span class="math-container">$O((ℓ^{1-ε})^2) = O(ℓ^{2-2ε})$</span> is not linear). Therefore the algorithm requires a fast multiplication algorithm (Karatsuba's is sufficient).</p>
<p>Another remark is that the integer <span class="math-container">$2^i-1$</span> chosen in this algorithm is much larger than the prime number in the first algorithm: <span class="math-container">$O(ℓ^{1-ε})$</span> bits vs. <span class="math-container">$O(\log ℓ)$</span> bits. In the first algorithm, the reduction <span class="math-container">$n\bmod p$</span> is linear using a clever algorithm for small modulus. In the second algorithm, the reduction is linear since reducing <span class="math-container">$\bmod 2^i-1$</span> is <span class="math-container">$O(ℓ^ε)$</span> additions of <span class="math-container">$O(ℓ^{1-ε})$</span>-bit integers.</p>
<p>[edited: The answer initially presented only the second algorithm, while the first is also of interest!]</p>

CC BY-SA 4.0
2021-02-09T12:05:41.240Z
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?
Turbo
CC BY-SA 4.0
2021-02-10T04:59:22.710Z
'at any' gives $O(\log n)$ but 'at any' doesn't.
Turbo
CC BY-SA 4.0
2021-02-10T11:05:49.500Z
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
CC BY-SA 4.0
2021-02-10T12:20:35.570Z
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.
Turbo
CC BY-SA 4.0
2021-02-10T13:44:21.847Z
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
CC BY-SA 4.0
2021-02-11T16:08:30.530Z
This is indeed an intriguing paper. And so is https://dl.acm.org/doi/abs/10.1145/31846.31850 that it cites.
Emil Jeřábek
CC BY-SA 4.0
2024-10-23T14:27:13.363Z
It seems you are assuming that 2^i-1 is a Mersenne prime, otherwise the error bounds in the paper would not hold.
Gregory Morse
CC BY-SA 4.0
2024-10-28T09:32:12.243Z
@GregoryMorse No! Two answers: 1. The simplest way is to read the (short, well-written) paper! 2. An important point in this result is that $2^i-1$ is *large*, much larger than a prime number $p$ one would take to perform the test $\bmod p$; It is just slightly smaller than the inputs themselves so that the multiplication $\bmod 2^i-1$ can be performed in time linear in the input sizes.
Bruno
CC BY-SA 4.0
2024-10-29T10:22:39.200Z
Yea I did read the paper which is excellent though the typesetting on epsilon bounds is messed up, 0 to -2?  Section 4 proves 2^n-1. Anyhow in practice you might need multiple primes or 2^n-1 values.  In which case it is hard to say which has better complexity.  The paper gives a minimum error bound but when using multiple verifications the error bound seems to decrease more rapidly than the worst case in a significant way.
Gregory Morse
CC BY-SA 4.0
2024-10-29T14:05:55.433Z
The $ε$ bound in Theorem 1 is $0 < ε < ½$. (The "$1$" is indeed barely readable since it is stuck between the "e" and "m" of "Theorem".) I agree that the error bounds are probably not the best one can have, but I do not think much is to be gained though. (And I update my answer: Using the second paper mentioned by @EmilJeřábek, there is another linear-time algorithm.)
Bruno
CC BY-SA 4.0
2021-02-08T15:19:56.117Z
2024-10-29T14:54:45.537Z
2024-10-29T14:54:45.537Z
Bruno
<p>There is a <a href="https://en.wikipedia.org/wiki/Freivalds%27_algorithm" rel="noreferrer">quadratic randomized algorithm for matrix product verification</a>.</p>
<p>Is there a similar trick to 'verify given three integers <span class="math-container">$n,a,b$</span> if <span class="math-container">$n=ab$</span> holds?' in <span class="math-container">$O(\log n)$</span> time?</p>

<ds.algorithms><randomized-algorithms>
Is there a linear time algorithm for integer multiplication verification?
Turbo
# Is there a linear time algorithm for integer multiplication verification?

(Asked by: username_0 on 2021-01-26)

There is a [quadratic randomized algorithm for matrix product verification](https://en.wikipedia.org/wiki/Freivalds%27_algorithm).

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

**Tags:** ds.algorithms, randomized-algorithms


---

## 2 answers

### Answer by username_3 on 2021-02-08. Score: 12 | Accepted answer

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](https://dl.acm.org/doi/abs/10.1145/58562.214082), J. ACM 36(1), pp. 142–149, Jan. 1989. Actually, two such algorithms are provided.

##### First algorithm

The standard algorithm of checking $n = ab\bmod p$ for some prime $p$ with $O(\log ℓ)$ bits, where $ℓ = \log n$, actually runs in linear time. This is due to [another algorithm of Kaminski](https://dl.acm.org/doi/abs/10.1145/31846.31850) that allows to compute $n\bmod p$ in $O(ℓ)$ bit operations. (Note that this reduction algorithm is far from obvious, and only sketched in the reference.) Therefore, the algorithm is:

1. First find a $O(\log ℓ)$-bit prime $p$ in $\log^{O(1)}(ℓ)$ bit operations;
2. Compute $n\_p=n\bmod p$, $a\_p=a\bmod p$ and $b\_p=b\bmod p$ in $O(ℓ)$ bit operations;
3. Check whether $n\_p = a\_pb\_p\bmod p$ in $\log^{O(1)}(ℓ)$ bit operations.

The algorithm fails if $n≠ ab$ but $p$ divides $n-ab$: Since this is a $O(ℓ)$-bit integer, it has at most $O(ℓ)$ prime divisors. If we uniformly sample a $O(\log ℓ)$-bit prime, the probability that is divides $n-ab$ is constant. Therefore, the algorithm has a constant probability of success, that can be amplified using repetition.

##### Second algorithm

This is the main algorithm described in the paper. The basic idea is to replace the prime number $p$ in the first algorithm by some random integer $2^i-1$ where $i = O(ℓ^{1-ε})$ for some $ε\in (0,½)$. The algorithm becomes:

1. Take a random integer $i = O(ℓ^{1-ε})$ in $O(ℓ^{1-ε})$ bit operations;
2. Compute $n\_i = n\bmod 2^i-1$, $a\_i = a\bmod 2^i-1$ and $b\_i=b\bmod 2^i-1$ in $O(ℓ)$ bit operations;
3. Check whether $n\_i = a\_ib\_i\bmod 2^i-1$ in $(ℓ^{1-ε})^{O(1)}$ bit operations.

Kaminski proves that if $0<ε<½$, this algorithm is correct with good probability. Note though that for this algorithm to run in $O(ℓ)$ bit operations, one needs $(ℓ^{1-ε})^{O(1)}$ to be $O(ℓ)$ in step 3. This means that the product cannot be performed naively in quadratic time (since $O((ℓ^{1-ε})^2) = O(ℓ^{2-2ε})$ is not linear). Therefore the algorithm requires a fast multiplication algorithm (Karatsuba's is sufficient).

Another remark is that the integer $2^i-1$ chosen in this algorithm is much larger than the prime number in the first algorithm: $O(ℓ^{1-ε})$ bits vs. $O(\log ℓ)$ bits. In the first algorithm, the reduction $n\bmod p$ is linear using a clever algorithm for small modulus. In the second algorithm, the reduction is linear since reducing $\bmod 2^i-1$ is $O(ℓ^ε)$ additions of $O(ℓ^{1-ε})$-bit integers.

[edited: The answer initially presented only the second algorithm, while the first is also of interest!]

> **Comments:**
> **username_0**: 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?  
> **username_0**: 'at any' gives $O(\log n)$ but 'at any' doesn't.  
> **username_3**: 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.  
> **username_0**: 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.  
> **username_3**: 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$.  
> **username_2**: This is indeed an intriguing paper. And so is https://dl.acm.org/doi/abs/10.1145/31846.31850 that it cites.  
> **username_4**: It seems you are assuming that 2^i-1 is a Mersenne prime, otherwise the error bounds in the paper would not hold.  
> **username_3**: @GregoryMorse No! Two answers: 1. The simplest way is to read the (short, well-written) paper! 2. An important point in this result is that $2^i-1$ is *large*, much larger than a prime number $p$ one would take to perform the test $\bmod p$; It is just slightly smaller than the inputs themselves so that the multiplication $\bmod 2^i-1$ can be performed in time linear in the input sizes.  
> **username_4**: Yea I did read the paper which is excellent though the typesetting on epsilon bounds is messed up, 0 to -2?  Section 4 proves 2^n-1. Anyhow in practice you might need multiple primes or 2^n-1 values.  In which case it is hard to say which has better complexity.  The paper gives a minimum error bound but when using multiple verifications the error bound seems to decrease more rapidly than the worst case in a significant way.  
> **username_3**: The $ε$ bound in Theorem 1 is $0 < ε < ½$. (The "$1$" is indeed barely readable since it is stuck between the "e" and "m" of "Theorem".) I agree that the error bounds are probably not the best one can have, but I do not think much is to be gained though. (And I update my answer: Using the second paper mentioned by @EmilJeřábek, there is another linear-time algorithm.)  

---

### Answer by username_1 on 2021-01-26. Score: 3

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

> **Comments:**
> **username_0**: So to get to $o(1)$ probability of certifying inequality it needs $\Omega(\log\log n)$ trials?  
> **username_2**: @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)$.  
> **username_2**: 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](https://en.wikipedia.org/wiki/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)$.  
> **username_0**: 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.  

---

