Factoring a large semi-prime number.

Question

Say I want to factor $N=12193263122374638001$ into prime factors. Surely this can easily be done with a computer and the answer would be $N=123456789\cdot9876543211.$

But If I want to do this by hand, and say I somehow found out that

$$293813570403791659^2\equiv 25 \quad (\text{mod} \ N),\tag1$$

how can I do it?

I can't see the connection between $(1)$ and my problem. I found this document wich seemed to point men the right direction at first, but they don't deal with cases like mine, that is with conditions like $(1)$.

Any tips?

Answer 1

If $$x^2\equiv y^2\mod N$$ is a non-trivial congruence (that means $x\ne \pm y\mod N$) , then $$\gcd(x-y,N)$$ and $$\gcd(x+y,N)$$ give non-trivial factors of $N$. This is the basic idea of the number field sieve to factor large numbers.