2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This was very interesting, but is this hard to show? If I'm going to use it, I'd like to understand the proof or at least have some intuition behind why this is true. $\endgroup$ – Parseval Feb 13 at 16:55
  • 4
    $\begingroup$ $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$. $\endgroup$ – Robert Israel Feb 13 at 17:06
  • $\begingroup$ @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? $\endgroup$ – Parseval Feb 13 at 17:40
  • $\begingroup$ I would hate to try doing something like that by hand. God gave us computers for a reason. $\endgroup$ – Robert Israel Feb 13 at 20:13
  • $\begingroup$ subtract 400 times the first from the second. $\endgroup$ – Roddy MacPhee Feb 21 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.