Integer Factorization of Semi-Primes Based on Analysis of a Sequence of Modular Elliptic Equations
- 1
Abstract
In this paper is demonstrated a method for reduction of integer factorization problem to an analysis of a sequence of modular elliptic equations. As a result, the paper provides a non-deterministic algorithm that computes a factor of a semi-prime integer <i>n=pq</i>, where prime factors <i>p</i> and <i>q</i> are unknown. The proposed algorithm is based on counting points on a sequence of at least four elliptic curves <i>y<sup>2</sup>=x(x<sup>2</sup>+b<sup>2</sup>)(</i>mod<i>n)</i> , where <i>b</i> is a control parameter. Although in the worst case, for some <i>n</i> the number of required values of parameter <i>b</i> that must be considered (the number of basic steps of the algorithm) substantially exceeds <i>four</i>, hundreds of computer experiments indicate that the average number of the basic steps does not exceed six. These experiments also confirm all important facts discussed in this paper.
- R. Crandall and C. Pomerance, “Prime Numbers: A Computational Perspective,” Springer, New York, 2001.
- H. Cohen, “A Course in Computational Algebraic Number Theory,” Springer-Verlag, New York, 1996.
- D. Shanks, “Class Number, a Theory of Factorization and Genera,” Proceedings of Symposium of Pure Mathematics, Vol. 20, 1969, pp. 415-440.
- S. Lehman, “Factoring Large Integers,” Mathematics of Computation, Vol. 28, 1974, pp. 637-646. doi:10.1090/S0025-5718-1974-0340163-2
- J. Pollard, “Theorems on Factorization and Primality Testing,” Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 76, 1974, pp. 521-528. doi:10.1017/S0305004100049252
- J. Pollard, “Factoring with Cubic Integers,” The Development of the Number Field Sieve, Lecture Notes in Mathematics, Vol. 1554, 1993, pp. 4-10. doi:10.1007/BFb0091536
- C. Pomerance, “Analysis and Comparison of Some Integer Factoring Algorithms,” In: H. W. Lenstra and R. Tijdeman, Eds., Computational Methods in Number Theory, Math Centre Tracts—Part 1, Math Centrum, Amsterdam, 1982, pp. 89-139.
- C. Pomerance, “The Quadratic Sieve Factoring Algorithm,” Advances in Cryptology, Proceedings of Eurocrypt’84, LNCS, Springer-Verlag, Berlin, 1985, 169-182.
- R. D. Silverman, “The Multiple Polynomial Quadratic Sieve,” Mathematics of Computation, Vol. 48, 1987, pp. 329-339. doi:10.1090/S0025-5718-1987-0866119-8
- J. Buhler, H. W. Lenstra and C. Pomerance, “Factoring Integers with the Number Field Sieve,” In: A. K. Lenstra and H. W. Lenstra, Eds., The Development of the Number Field Sieve, Lecture Notes in Mathematics, Springer-Verlag, Berlin, Vol. 1554, 1993, pp. 50-94. doi:10.1007/BFb0091539
- A. K. Lenstra and A. Shamir, “Analysis and Optimization of the TWINKLE Factoring Device,” Advances in Cryptology—EUROCRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, New York, Vol. 1807, 2000, pp. 35-52.
- A. Shamir and E. Tromer, “Factoring Large Numbers with the TWIRL Device,” Advances in Cryptology— CRYPTO 2003, Lecture Notes in Computer Science, Springer-Verlag, New York, Vol. 2729, 2003, pp. 1-26.
- P. W. Shor, “Polynomial-Time Algorithms for Prime Fac- torization and Discrete Logarithms on a Quantum Com- puter,” SIAM Journal on Computing, Vol. 26, No. 5, 1997, pp. 1484-1509. doi:10.1137/S0097539795293172
- R. P. Brent, “Some Integer Factorization Algorithms Using Elliptic Curves,” Proceedings of 9th Australian Computer Science Conference, Canberra, January 1985.