Abstract
An efficient integer factorization algorithm would reduce the security of all variants of the RSA cryptographic scheme to zero. Despite the passage of years, no method for efficiently factoring large semiprime numbers in a classical computational model has been discovered. In this paper, we demonstrate how a natural extension of the generalized approach to smoothness, combined with the separation of 2-adic point orders, leads us to propose a factoring algorithm that finds (conjecturally) the prime decomposition N = pq in subexponential time L(√2+o(1), min(p,q)). This approach motivated by the papers \cite{Len}, \cite{MMV} and \cite{PoZo} is based on a more careful investigation of pairs (E,Q), where Q is a point on an elliptic curve E over _N. Specifically, in contrast to the familiar condition that the largest prime divisor P⁺( Q_p) of the reduced order Q_p does not divide #E(_q) we focus on the relation between P⁺( Q_r) and the smallest prime number l_min(E,Q) separating the orders Q_p and Q_q. We focus on the ₂ family of even order elliptic curves over _N since then the condition l_min(E,Q)≤ 2 holds true for large fraction of points (x,y)∈ E(_N). Moreover if we know the pair (E,Q) such that P⁺( Q_r)≤ t<l_min(E,Q) and d=max_r∈ {p,q}( Q_r) is large in comparison to min_r∈ {p,q}|a_r(E)|≠ 0 then we can decompose N in deterministic time t^1+o(1) by representing N in base d.