# Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?

Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice completely silly because you only start to see advantages on numbers with an absurd number of digits.

But suppose that we only wanted a probabilistic multiplication circuit, which returned the wrong result with probability at most epsilon. Then maybe certain shortcuts could be taken, in order to avoid the most inconvenient parts of multiplying two numbers.

For a fixed acceptable failure rate epsilon, is there an O(n log n) multiplication algorithm that achieves this failure rate without being horrendously inefficient in practice?

• This does not answer the question. Whether a probabilistic multiplication circuit using $O(n \log n)$ gates has any practical use is irrelevant to the question, which is whether such a circuit exists. Also, a bounded-error probabilistic algorithm by definition will not get any product consistently wrong, but only wrong with a bounded probability over the random bits. – Aaron Rotenberg Jan 14 '20 at 23:37