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

## DOI:

https://doi.org/10.21914/anziamj.v48i0.112## 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

## Published

2007-12-27

## Issue

## Section

Proceedings Computational Techniques and Applications Conference