Fast evaluation of iterated multiplication of very large polynomials: An application to chinese remainder theory


  • David Laing
  • Bruce Litow



We consider the problem of exactly computing the number of integers in a Chinese Remainder Representation (CRR) whose pseudorank does not equal the rank. We call this number the census. The rank is key in developing CRR-intrinsic methods for comparing integers in CRR, a problem known to be notoriously difficult. Pseudorank can be computed in highly restrictive computation models. We have developed and implemented a fast, efficient algorithm for computing the census based on using a variant of the FFT to compute iterated products of polynomials of very large degree, and with arbitrary size integer coefficients. Experimental census results are tabulated. This census information makes possible a new approach to exploring the fine structure of CRR. References
  • J. Hee. Fast convolution using polynomial transforms., 2004.
  • W. Hesse. Division is in uniform tc0. In ICALP '01: Proceedings of the 28th International Colloquium on Automata, Languages and Programming, pages 104--114, London, UK, 2001. Springer--Verlag. Also available as whesse/
  • D. Knuth. Seminumerical Algorithms, volume 1 of The Art of Computer Programming, section 4.3.2. Addison--Wesley, third edition, 1997.
  • W. Kuich and A. Salomaa. Semirings,Automata,Languages. Springer-Verlag, 1986.
  • B. Litow and D. Laing. A census algorithm for chinese remainder pseudorank with experimental results. James Cook University, School of IT Tech Report, 2005.
  • H. J. Nussbaumer. Fast Fourier Transform and Convolution Algorithms. Springer, 1982. 2nd ed.
  • A. Salomaa and S. Soittola. Automata Theoretic Aspects of Formal Power Series. Springer--Verlag, 1978.
  • M. P. Schutzenberger. On a theorem of {Jungen}. Proc. Am. Math. Soc., 13:885--890, 1962.
  • R. Tanaka and N. Szabo. Residue Arithmetic and its Application to Computer Technology. McGraw--Hill, 1968.
  • S. P. Tarasov and M. N. Vyalyi. Semidefinite programming and arithmetic circuit evaluation. Technical report, 2005. Available as
  • G. Davida A. Chiu and B. Litow. Division in logspace-uniform NC$^1$. Theoretical Informatics and Applications, 35:259--275, 2001. doi:10.1051/ita:2001119
  • I. M. Vinagradov. Elements of Number Theory. Dover, 1954.
  • S. A. Cook and S. O. Aanderaa. On the minimum computation time of functions. Transactions of the American Mathematical Society, 142:291--314, Aug 1969.
  • K. Culik and J. Kari. Handbook of Formal Languages, chapter 10, pages 599--616. Springer, 1997.
  • G. Davida and B. Litow. Fast parallel arithmetic via modular representation. SIAM J. Comp., 20,4:756--765, 1991. doi:10.1137/0220048





Proceedings Computational Techniques and Applications Conference