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.

[img] PDF
Restricted to Repository staff only

View at Publisher Website: http://anziamj.austms.org.au/ojs/index.p...

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 (Refereed Research - C1)
Keywords: Chinese remainder representation; census algorithms; convolution
ISSN: 1446-8735
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

Actions (Repository Staff Only)

Item Control Page Item Control Page