Note on probabilistic algorithms in integer and polynomial arithmetic
Michael Kaminski · 1981
For many computational problems it is not known whether verification of a result can be done faster than its computation. For instance, it is unknown whether the verification of the validity of the integer equality x*y=z needs fewer bit operations than a computation of the product x*y. It is sometimes much easier, however, to speed up the computation probabilistically if just the verification of the result is involved.