Chinese remaindering with errors
Oded Goldreich, Dana Ron, Madhu Sudan · IEEE Transactions on Information Theory · 1999
The Chinese remainder theorem states that a positive integer m is uniquely specified by its remainder module k relatively prime integers p/sub 1/, /spl middot//spl middot//spl middot/, p/sub k/, provided m</spl Pi//sub i=1//sup k/p/sub i/. Thus the residues of m module relatively prime integers p/sub 1/<p/sub 2/</spl middot//spl middot//spl middot/<p/sub n/ form a redundant representation of m if m</spl Pi//sub i=1//sup k/p/sub i/ and k<n. This gives a number-theoretic construction of an "error-correcting code" that has been considered often in the past. In this code a "message" (integer) m</spl Pi//sub i=1//sup k/p/sub i/ is encoded by the list of its residues module p/sub 1/, /spl middot//spl middot//spl middot/, p/sub n/. By the Chinese remainder theorem, if a codeword is corrupted in e<(n-k)/2 coordinates, then there exists a unique integer m whose corresponding codesword differs from the corrupted word in at most e places. Furthermore, Mandelbaum (1976, 1978) shows how m can be recovered efficiently given the corrupted word provided that the p/sub i/s are very close to one another. To deal with arbitrary p/sub i/s, we present a variant of his algorithm that runs in almost linear time and recovers from e<(log p/sub 1/)/(log p/sub 1/+log p/sub n/)/spl middot/(n-k) errors. Our main contribution is an efficient decoding algorithm for the case in which the error e may be larger than (n-k)/2. Specifically, given n residues r/sub 1/, /spl middot//spl middot//spl middot/, r/sub n/ and an agreement parameter t, we find a list of all integers m