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

Abstract

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. http://jenshee.dk/signalprocessing/polytrans.pdf, 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 http://people.clarkson.edu/ whesse/div.ps.
• 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 http://www.cs.jcu.edu.au/ftp/pub/techreports/2005-3.pdf, 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 http://arxiv.org/abs/cs/0512035v1.
• 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