I am trying to find solutions for integer factorization problem. And particularly I am curries in RSA cracking.
I came to the next equation:
$$az + by = \frac{c}{x}$$
- $c$ is the number that I am trying to factor.
- $x$ one of the two possible solutions(because it's RSA, $c$ been chosen that way)
- $a,b$ relatively small positive integer constants that I know their value
- $z,y$ positive integer variables
Can this be any useful for me?
Take $N=XY$ and imagine that each number is written using the division algorithm in terms of some base $B$. Then you get $Bz+r=(Bx+a)(By+b)$. Where $r$ is congruent to $ab$ mod $B$, and $N$, $X$, $Y$ are relatively prime to $B$. A little algebra reduces this to $z=Bxy+ay+bx+m$. Now you have reduced your search area for trial division by a factor of $B$, except that you have to multiply it by the totient function of $B$. Thus the fastest you can get (on the surface) with this method is using the reduced residue systems of primorials. The rough best choice for $B$ is around the third or fourth root of $N$. You want to pick $B$ small enough that the factors you seek are not in the reduced residue system or else the equation collapses to trial division over the reduced residue system, that is roughly speaking trial division. The best value for $B$ is not knowable simply as a function of $N$ unless you decide to shift gears whenever $ax+by$ is greater than $B$ by choosing $B$ from some easy to use sequence like the primorials. At worst you have to check $\phi(n)$ places at each level.