Fast Sign Detection for RNS $(2^{n}-1,2^{n},2^{n}+1)$

In this paper, we propose a fast algorithm for sign-extraction of a number given in the Residue Number System $(2^{n}-1,2^{n},2^{n}+1)$ . The algorithm can be implemented using three $n$-bit wide additions, two of which can be done in parallel. It can be used in a wide variety of problems, i.e., in algorithms for dividing numbers in the RNS, or in evaluating the sign of determinant in computational geometry, etc.