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.

PDF Restricted to Repository staff only

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.

Item ID:	2254
Item Type:	Article (Research - C1)
ISSN:	1446-8735
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%
Downloads:	Total: 3
	More Statistics