Physical Sciences and Mathematics Commons^™

Towards A Novel Generalized Chinese Remainder Algorithm For Extended Rabin Cryptosystem, Justin Zhan, Peter J. Shiue, Shen C. Huang, Benjamin J. Lowe

Mathematical Sciences Faculty Research

This paper proposes a number of theorems and algorithms for the Chinese Remainder Theorem, which is used to solve a system of linear congruences, and the extended Rabin cryptosystem, which accepts a key composed of an arbitrary finite number of distinct primes. This paper further proposes methods to relax the condition on the primes with trade-offs in the time complexity. The proposed algorithms can be used to provide ciphertext indistinguishability. Finally, this paper conducts extensive experimental analysis on six large data sets. The experimental results show that the proposed algorithms are asymptotically tight to the existing decryption algorithm in the …