|
Abstract : |
z The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p 1; : : : ; p k, provided m! Q k i=1 p i. Thus the residues of m modulo relatively prime integers p 1! p 2! \Delta \Delta \Delta! pn form a redundant representation of m if m! Q k i=1 p i and k! n. This suggests a number-theoretic construction of an "error-correcting code " that has been implicitly considered often in the past. In this paper we provide a new algorithmic tool to go with this error-correcting code: namely, a polynomialtime algorithm for error-correction. Specifically, given n residues r 1; : : : ; r n and an agreement parameter t, we find a list of all integers m! Q k i=1 p i such that (m mod p i) = r i for at least t values of i 2 f1; : : : ; ng, provided t = \Omega\Gamma, |
