What algorithms are used to determine the difference of two squares?

Question

I'm taking a discrete math class this semester. The professor said that by the end of the semester he wants us to have an understanding of RSA encryption. One thing that we have gone over in class is the Euclidean algorithm used to find the greatest common divisor of two numbers.

There is one part that he hasn't really gone over though. That part is, how are you supposed to get to the step where you have a difference of two squares?

This is an example of what I'm talking about:

$1,194995^2 - 555,218^2$

$ = 1,428,013,050,025 - 308,267,027,524$

$= 1,119,746,022,501$

$ =20,504,789 * 54609$

Factor $20,504,789$ in a non-trivial way.

How are you supposed to get to the steps where you know you have to factor 20,504,789? All he had said is that he will give us the first part. I want to know how the first part is produced.

Answer 1

Key in many algorithms to factor an integer $\rm\:n\:$ (e.g. Fermat's difference fo squares continued fraction, quadratic sieve, number field sieve) is the search for a nontrivial square root mod $\rm\:n,\:$ i.e.

$$\rm\: mod\ n\!:\ \ a^2\equiv\,b^2,\ \ a\not\equiv \pm b$$

Then $\rm\ n\mid a^2\!-\!b^2\! = (a\!-\!b)(a\!+\!b),\ \ n\nmid a\pm b\:\Rightarrow\: gcd(n,a\!+\!b)\:$ is a proper factor of $\rm\:n.\:$

Each of the mentioned integer factorization algorithms employs different strategies to discover such nontrivial square roots. In some special cases one can prove that such ideas lead to fast algorithms. For example, one can tweak Fermat's factorization method (by difference of squares) to quickly factor any $\rm\ n = p\:q\ $ that is a product of two "close" primes, namely if $\rm\:|p-q| < n^{1/3},\:$ then $\rm\:n\:$ can be factored in polynomial time, see Robert Erra; Christophe Grenier. The Fermat factorization method revisited. 2009, and their slides How to compute RSA keys? The Art of RSA: Past, Present, Future.

Answer 2

You have $1,194,995^2 - 555,218^2=(1,194,995+555,218)(1,194,995-555218)=1,750,213\cdot 639,777$ Now we can look for common factors between both of these and $20,504,789$, finding $16057$ and $1277$ but it is not obvious to me how you found the factorization you have.

Answer 3

If your question is how to solve the exercise you mentioned (factoring $n=20504789$), then Ross Millikan's answer is the way to go.

If you are wondering how someone ever came up with 1194995 and 555218 given the number 20504789, my guess is they just started from the squares and then found the number 20504789. For example, take numbers $a=23456789$ and $b=12345678$. Then $a^2-b^2 = 14425252381 \cdot 27577$ (which I factored using a computer, just for the purpose of creating a problem statement). One can then ask

Observe that $a^2-b^2 = 14425252381 \cdot 27577$ where $a=2345678$ and $b=12345678$. Factor 14425252381 in a non-trivial way.

Answer 4

I don't know what exactly you're looking for. But here's the generalized form your effort.

$a=a_1.a_2...(a_i)$ and $b=b_1.b_2...(b_m)$ (A large enough numbers).

$a^2-b^2=N$

Now $N$ is $n_1.n_2...n_k$

You're looking for unique(not a prime one) factorization of $N$.

For example: $N=101.59.61.109$, One of the unique factorizations can be $N=5959.6649$