- 期刊
Analysis of Two Outsourcing Algorithms for Solving Quadratic Congruence
摘要
We show that the outsourcing algorithms [IEEE ITJ, 7(4), 2020, 2968-2981] for solving quadratic congruence in the Internet of Things are flawed. (1) The Cipolla algorithm is unsuitable for the discussed scenario. The underlying modulus is generally a composite containing two strong primes to resist some factorization algorithms. Besides, the Rabin cryptosystem explicitly requires that p ≡ q ≡ 3 mod 4. In this case, the Cipolla algorithm is unnecessary. (2) The outsourcer can finish the computation solely, even if p ≢ 3 mod 4 and q≢3 mod 4. He doesn't have to outsource the original problem because he must pay out equal-cost O(log^3 p) in the proposed outsourcing scenario.
延伸閱讀
- Chen, Q. (2011). Algorithms for some combinatorial optimization problems [doctoral dissertation, The University of Hong Kong]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0029-1812201200019107
- Yu, C. C. (2015). Analysis and Comparison of Weighted Combinatorial Algorithms for Test Suite Reduction [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-0312201510303680
- REICH, S., & XU, H. K. (2003). AN ITERATIVE APPROACH TO A CONSTRAINED LEAST SQUARES PROBLEM. Abstract and Applied Analysis, 2003(), 503-512. https://doi.org/10.1155/S1085337503212082
- HILTON, P., & PEDERSEN, J. (1987). ON THE COMPLEMENTARY FACTOR IN A NEW CONGRUENCE ALGORITHM. International Journal of Mathematics and Mathematical Sciences, 1987(), 113-123. https://doi.org/10.1155/S0161171287000140
- Schöne, R., & Hanning, T. (2012). Least Squares Problems with Absolute Quadratic Constraints. Journal of Applied Mathematics, 2012(), 1615-1626-200. https://doi.org/10.1155/2012/312985