1999/05/01 by Oded Goldreich, O. Goldreich, D. Ron +3 · 1 citation
Computer Science · #Cryptography and Data Security #Coding theory and cryptography #Complexity and Algorithms in Graphs
paper · doi:10.1109/18.850672
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</spl Pi//sub i=1//sup k/p/sub i/ such that (m mod p/sub i/)=r/sub i/ for at least t values of i/spl isin/1, /spl middot//spl middot//spl middot/, n, provided t=/spl Omega/(/spl radic/(kn(log p/sub n//log p/sub 1/))). For n/spl Gt/k (and p/sub n//spl les/p/sub 1//sup O(1)/), the fraction of error corrected by the algorithm is almost twice that corrected by the previous work. More significantly, the algorithm recovers the message even when the amount of agreement between the "received word" and the "codeword" is much smaller than the number of errors.