Integer Factorization of Semi-Primes Based on Analysis of a Sequence of Modular Elliptic Equations

Boris S. Verkhovsky

.

DOI: 10.4236/ijcns.2011.410073                

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 n=pq, where prime factors p and q are unknown. The proposed algorithm is based on counting points on a sequence of at least four elliptic curves y²=x(x²+b²)(modn) , where b is a control parameter. Although in the worst case, for some n the number of required values of parameter b that must be considered (the number of basic steps of the algorithm) substantially exceeds four, 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.

Keywords

Integer Factorization, Factorization of Semi-Primes, Non-Deterministic Algorithm, Elliptic Curves, Counting Points on Elliptic Curves, Crypto-Immunity, Dual Elliptic Curves

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. Crandall and C. Pomerance, “Prime Numbers: A Computational Perspective,” Springer, New York, 2001.
[2]	H. Cohen, “A Course in Computational Algebraic Number Theory,” Springer-Verlag, New York, 1996.
[3]	D. Shanks, “Class Number, a Theory of Factorization and Genera,” Proceedings of Symposium of Pure Mathematics, Vol. 20, 1969, pp. 415-440.
[4]	S. Lehman, “Factoring Large Integers,” Mathematics of Computation, Vol. 28, 1974, pp. 637-646. doi:10.1090/S0025-5718-1974-0340163-2
[5]	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
[6]	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
[7]	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.
[8]	C. Pomerance, “The Quadratic Sieve Factoring Algorithm,” Advances in Cryptology, Proceedings of Eurocrypt’84, LNCS, Springer-Verlag, Berlin, 1985, 169-182.
[9]	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
[10]	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
[11]	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.
[12]	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.
[13]	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
[14]	R. P. Brent, “Some Integer Factorization Algorithms Using Elliptic Curves,” Proceedings of 9th Australian Computer Science Conference, Canberra, January 1985.
[15]	H. W. Lenstra Jr., “Factoring Integers with Elliptic Cur- ves,” Annals of Mathematics, Vol. 126, No. 2, 1987, pp. 649-673. doi:10.2307/1971363
[16]	P. L. Montgomery, “A FFT Extension of the Elliptic Curve Method of Factorization,” PhD Thesis, University of California, Los Angeles, 1992.
[17]	R. Schoof, “Counting Points of Elliptic Curves over Finite Fields,” Journal de Théorie des Nombres de Bor- deaux, Vol. 7, No. 1, 1995, pp. 219-254. doi:10.5802/jtnb.142
[18]	R. Lencier, D. Lubicz and F. Vercauteren, “Point Counting on Elliptic and Hyperelliptic Curves,” In: H. Cohen and G. Frey, Eds., Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC, Boca Raton, 2006, pp. 407-453.
[19]	A. G. B. Lauder and D. Wan, “Counting Points on Varieties over Finite Fields of Small Characteristics,” In: J. P. Buhler and P. Stevenhagen, Eds., Algorithmic Number Theory, Cambridge University Press, Cambridge, 2008, pp. 579-612.
[20]	A. Weil, “Number of Solutions of Equations in Finite Fields,” Bulletin of American Mathematical Society, Vol. 55, 1949, pp. 497-508. doi:10.1090/S0002-9904-1949-09219-4
[21]	A. G. B. Lauder, “Counting Solutions to Equations in Many Variables over Finite Fields,” Foundation of Com- putational Mathematics, Vol. 4, No. 3, 2004, pp. 221-267. doi:10.1007/s10208-003-0093-y
[22]	Boris S. Verkhovsky, “Integer Factorization: Solution via Algorithm for Constrained Discrete Logarithm Problem,” Journal of Computer Science, Vol. 5, No. 9, 2009, pp. 674-679. doi:10.3844/jcssp.2009.674.679
[23]	“RSA Factoring Challenge,” http://en.wikipedia.org/wiki/RSA_Factoring_Challenge