On enumerating solutions of certain equations over Z_m and an effective algorithm for factoring integers
Guangkui Xu, Xiwang Cao · International Journal of Applied Mathematics & Statistics/International journal of applied mathematics and statistics · 2013
Factoring a large integer is a hard work in number theory. The security of the RSA public-key cryptosystem is based on the difficulty of factoring the product of two large prime numbers. This paper presents an efficient algorithm of factoring of integers, which is based on Berlekamp algorithm. By analysing the time complexity, our algorithm can be estimated to be much faster than the known algorithms. Meanwhile, We study the links between the number of solutions of certain equations over Z_m and the number of primitive idempotents in Z_m. We then apply the links to give the number of solutions of certain equations over Z_m.