# Factoring a large semi-prime number.

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?

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.
• $N \mid x^2 - y^2 = (x-y)(x+y)$. Thus any prime factor of $N$ must divide either $x-y$ or $x+y$. If $x \ne \pm y \mod N$, some must divide $x-y$ and some must divide $x+y$. – Robert Israel Feb 13 at 17:06
• @RobertIsrael - May I ask, is this method really more effective? I now stand here with trying to use the Euclidean algorithm on $\text{gcd}(293813570403791654, 12193263122374638001).$ Is there a shortcut here or do I just need to do it? – Parseval Feb 13 at 17:40