The South Caicos Factoring Algorithm

Abstract

Let $N=UV$, where $U,V$ are integers, with $1<U,V<N$, and $\gcd (U,V)=1$. We describe a probabilistic algorithm for factoring $N$ using $O(\max (U,V{)}^{1/2+\epsilon })$ bit operations.