Fast evaluation of iterated multiplication of very large polynomials: an application to Chinese remainder theory
Laing, D., and Litow, B. (2007) Fast evaluation of iterated multiplication of very large polynomials: an application to Chinese remainder theory. ANZIAM Journal, 48. pp. 709-724.
Restricted to Repository staff only
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.
|Item Type:||Article (Refereed Research - C1)|
|Keywords:||Chinese remainder representation; census algorithms; convolution|
|Date Deposited:||10 Jun 2009 23:17|
|FoR Codes:||08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080299 Computation Theory and Mathematics not elsewhere classified @ 100%|
|SEO Codes:||97 EXPANDING KNOWLEDGE > 970101 Expanding Knowledge in the Mathematical Sciences @ 100%|