A factoring algorithm?

123 Views Asked by At

I haven't proved it (yet) but it seems like $\gcd(a-b,m+n)|am+bn$. Could this be used to design a factoring agorithm?

A big number $N$ could be analyzed finding $a,b,m,n\in\mathbb Z_+$ such that $N=am+bn$, with recursion due to one of the terms, to find $a,b,m,n$ such that $\gcd(a-b,m+n)>1$.


The strategy of choose $a,b,m,n$ has two goals, to choose $am$ close to $N$ and to increase the probability to get $\gcd >1$. The goals may be difficult or even impossible to combine, but one should remember the words of Carl Pomerance: "It isn't proved that factoring has to be hard."