Note on probabilistic algorithms in integer and polynomial arithmetic

ABSTRACT

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&equil;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. In this paper we present linear probabilistic algorithms for verification of the validity of the integer equality f1(x1,...,xN)&equil;f2(x1,...,xN) for rational functions f1 and f2, which can be of the form of a rational combination of rational functions.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Pollard J. "Theorems on Factorisation and Primality Testing", Proc. Cambridge Phylos. Soc. 76(1974), 521-528
• 3: Rabin M.O. "Probabilistic Algorithms", "Algorithms and Complexity: New Directions and Recent Results", Traub J.F., ed., Academic Press, New-York, 1976, 21-39
• 4: Rabin M.O. "Probabilistic Algorithms for Testing Primality", J. Number Theory 12 (1980) 128-138
• 5: Schonhage A., "Schnelle Multiplikation von Polynomen uber Korpen der Charakteristic 2", Acta Informatica, 7 (1977) 395-398
• 6: Jacob T. Schwartz, Probabilistic algorithms for verification of polynomial identities (invited), Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.200-215, June 01, 1979
• 7: Andrew C Yao, A lower bound to palindrome recognition by probabilistic Turing machines, Stanford University, Stanford, CA, 1977
• 8: Zippel R.E., "Probabilistic Algorithm for Sparse Polynomials", Ph.D. thesis, Massachusetts Institute of Technology (1979)

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory