**Author(s):**Boris S. Verkhovsky

**Journal:**International Journal of Communications, Network and System Sciences

ISSN 1913-3715

**Volume:**04;

**Issue:**10;

**Start page:**609;

**Date:**2011;

Original page

**Keywords:**Integer Factorization | Factorization of Semi-Primes | Non-Deterministic Algorithm | Elliptic Curves | Counting Points on Elliptic Curves | Crypto-Immunity | Dual Elliptic Curves

**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

*y2=x(x2+b2)(*mod

*n)*, 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.