Quadratic Sieve improvement idea

89 Views Asked by At

I got an idea for Quadratic Sieve improvement, but I don't know if someone already tried it or how efficient it is. Please tell me if it can work.

Let $N$ be the number we wish to factor.

We can look at the congruence of squares $x^2 \equiv y^2\pmod{N^2}$, if we can find such $x,y$ we can compute the gcd of $x+y$ and $N$ to find a nontrivial factor of $N$(if it's trivial we just need to find more $x,y$ pairs)

$y$ can be stated as $x^2-N^2 = y^2$ -> $(x-N)(x+N) = y^2$

We can then find a pair of $a,c$ such that $x+N=ac$ and $a,c \approx \sqrt{N}$, let's call the $x$ that satisfy this $x`$, then for each $x$ in $f(i)=ia+x`$ we can write $y$ as $(ia + x`-N)(x`+ia +N) = y^2$ -> $a(ia + x`-N)(c+i) = y^2$

Finally, we can start searching for $x,y$ pairs that satisfy $x^2 \equiv y^2\pmod{N^2}$ in

$$f(i)=a(ia + x`-N)(c+i)$$

When $f(i)$ is a square then $gcd(\sqrt{f(i)} + ia+x`,N)$ has a high chance if being a non trivial divisor of $N$

If we start running on $f(i)$ from $i\approx \frac{N-x}{a}$ then $ia+x`-N\approx{\sqrt{N}}$ and also $c+i\approx{\sqrt{N}}$. We can use the same technics as we use in QS . Leveregix Dixon's factorization method together with sieving and loggaritmic approximation for faster sieve.

The only difference is that we are building two squares instead of one, we are looking for $(ia + x`-N)$ to be a square and also $(c+i)$ to be a square, as they cannot have any commonly dividing values, except $2$ and the factors of $N$.

Proof:

If a prime $p$ divides $(x-N)$, $(x+N)$ then it must divides $(x-N + 2N)$ since it equals to $(x+N)$. And so it must divide $2N$, that can only happen if $p=2$ or $p$ is a factor of $N$

My theory is that the sieving should be much easier since we are not dealing with squares like in the classing QS where we are searching for $f(x)=x^2-N$ to be a square or SIQS where we are searching for $f(x)=a(ax^2-bx+c)$ to be a square. However from the other side, we need to make two numbers to be a square, so I am not so sure it's indeed easier and hence asking the question here.