Algorithms for Integer Factorization Based on Counting Solutions of Various Modular Equations
- 1
Abstract
This paper is a logical continuation of my recently-published paper. Security of modern communication based on RSA cryptographic protocols and their analogues is as crypto-immune as integer factorization (<i>iFac</i>) is difficult. In this paper are considered enhanced algorithms for the <i>iFac</i> that are faster than the algorithm proposed in the previous paper. Among these enhanced algorithms is the one that is based on the ability to count the number of integer solutions on quadratic and bi-quadratic modular equations. Therefore, the <i>iFac</i> complexity is at most as difficult as the problem of counting. Properties of various modular equations are provided and confirmed in numerous computer experiments. These properties are instrumental in the proposed factorization algorithms, which are numerically illustrated in several examples.
- R. L. Rivest, A. Shamir and L. M. Adleman, “A Method for Obtaining Digital Signature and Public-Key Cryptosystems,” Communications of ACM, Vol. 21, No. 2, 1978, pp. 120-126. doi:10.1145/359340.359342
- H. Elkamchouchi, K. Elshenawy and H. Shaban, “Extended RSA Cryptosystem and Digital Signature Schemes in the Domain of Gaussian Integers,” Proceedings of the 8th International Conference on Communication Systems, Singapore City, Vol. 1, 25-28 November 2002, pp. 91-95.
- M. O. Rabin, “Digitalized Signatures and Public Key Func- tions as Intractable as Factorization,” Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science, Cambridge, January 1979.
- Boris S. Verkhovsky, “Integer Factorization of Semi- primes Based on Analysis of a Sequence of Modular Elliptic Equations,” International Journal of Communications, Network and System Sciences, Vol. 4, No. 10, 2011, pp. 609-615. doi:10.4236/ijcns.2011.410073
- C. Pomerance, “The Quadratic Sieve Factoring Algorithm,” Advances in Cryptology, Proceedings of Eurocrypt’84, LNCS, Vol. 209, Springer-Verlag, Berlin, 1985, pp. 169- 182.
- R. Schoof, “Counting Points on Elliptic Curves over Finite Fields,” Journal de Theorie des Nombres de Bordeaux, Vol. 7, No. 1, 1995, pp. 219-254. doi:10.5802/jtnb.142
- K. Rubin and A. Silverberg, “Ranks of Elliptic Curves,” Bulletin (New Series) of the American Mathematical Society, Vol. 39, No. 4, 2002, pp. 455-474.
- L. Dewaghe, “Remarks on the Schoof-Elkies-Atkin Al- gorithm,” Mathematics of Computation, Vol. 67, No. 223, 1998, pp. 1247-1252. doi:10.1090/S0025-5718-98-00962-4
- C. F. Gauss, “Theoria Residuorum Biquadraticorum,” 2nd Edition, Chelsea Publishing Company, New York, 1965, pp. 534-586.