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)
|