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$
$ =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.