Euler's Factorization Method

A factorization algorithm which works by expressing as a quadratic form in two different ways. Then

(1)

so

(2)

(3)

Let be the greatest common divisor of and so

			(4)
			(5)
			(6)

(where denotes the greatest common divisor of and ), and

(7)

But since , and

(8)

which gives

(9)

so we have

			(10)
			(11)
			(12)
			(13)
			(14)
			(15)