Multi-Stage Robust Chinese Remainder Theorem

DOI10.1109/TSP.2014.2339798zbMATH Open1394.94942arXiv1303.3251OpenAlexW1976826674MaRDI QIDQ4579446FDOQ4579446

Authors: Li Xiao, X.-G. Xia, Wenjie Wang 

Publication date: 22 August 2018

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: It is well-known that the traditional Chinese remainder theorem (CRT) is not robust in the sense that a small error in a remainder may cause a large error in the reconstruction solution. A robust CRT was recently proposed for a special case when the greatest common divisor (gcd) of all the moduli is more than 1 and the remaining integers factorized by the gcd of all the moduli are co-prime. In this special case, a closed-form reconstruction from erroneous remainders was proposed and a necessary and sufficient condition on the remainder errors was obtained. It basically says that the reconstruction error is upper bounded by the remainder error level $au$ if $au$ is smaller than a quarter of the gcd of all the moduli. In this paper, we consider the robust reconstruction problem for a general set of moduli. We first present a necessary and sufficient condition for the remainder errors for a robust reconstruction from erroneous remainders with a general set of muduli and also a corresponding robust reconstruction method. This can be thought of as a single stage robust CRT. We then propose a two-stage robust CRT by grouping the moduli into several groups as follows. First, the single stage robust CRT is applied to each group. Then, with these robust reconstructions from all the groups, the single stage robust CRT is applied again across the groups. This is then easily generalized to multi-stage robust CRT. Interestingly, with this two-stage robust CRT, the robust reconstruction holds even when the remainder error level $au$ is above the quarter of the gcd of all the moduli. In this paper, we also propose an algorithm on how to group a set of moduli for a better reconstruction robustness of the two-stage robust CRT in some special cases.

Full work available at URL: https://arxiv.org/abs/1303.3251

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Cited In (3)

• Scalable antinoise-robustness estimation of frequency and direction of arrival based on the relaxed sparse array
• On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors
• On the continued fraction with rational partial quotients

This page was built for publication: Multi-Stage Robust Chinese Remainder Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579446)