Integer Factorization problem - New Idea

312 Views Asked by At

I been thinking about slightly different approach of solving the problem, and I want you to tell me if my idea is reasonable and if it's original(If someone already thought about this, I would be interested to know).

I want to factor some integer $N$. So I represent it as fallow, where $x,k,a$ are integers.

$$x^2 - N = ka$$

Next I constract a function

$$f(i) = (x + ik)^2 - N$$

And I want to find when $f(i)$ is a square so I can use Fermat factoring method.

So first lets simplify it.

$f(i) = (x + ik)^2 - N= x^2 + 2ik + (ik)^2 - N = 2ixk + (ik)^2 + ka=$ $$k(2ix + ki^2 + a)$$

Next I want to use similar ideas as used in quadratic sieve to find some vector representation of $2ix + ki^2 + a$ in the bounds of $B$ aka B-Smooth numbers. $k$ will always be part of the vector as it divides all the values in $f(i)$.

The benefit of this method is that the growth of $2ix + ki^2 + a$ will be slower than $h(i) = (x+i)^2 - N$ and there for it will be easier to look for B-Smooth numbers.

After finding enough B-Smooth numbers I can find a square.

Is it reasonable? Is it original? What do you think?