Euler's Factorization Method

Works by expressing $N$ as a Quadratic Form in two different ways. Then

$$N=a^2+b^2=c^2+d^2,$$ (1)

so

$$a^2-c^2=d^2-b^2$$ (2)

$$(a-c)(a+c)=(d-b)(d+b).$$ (3)

Let $k$ be the Greatest Common Divisor of $a-c$ and $d-b$ so

$$a-c = kl$$ (4)

$$d-b = km$$ (5)

$$(l,m) = 1,$$ (6)

(where $(l,m)$ denotes the Greatest Common Divisor of $l$ and $m$), and

$$l(a+c)=m(d+b).$$ (7)

But since $(l,m)=1$, $m\vert a+c$ and

$$a+c=mn,$$ (8)

which gives

$$b+d=ln,$$ (9)

so we have

$[({\textstyle{1\over 2}}k)^2+({\textstyle{1\over 2}}n)^2](l^2+m^2) = {\textstyle{1\over 4}}(k^2+n^2)(l^2+m^2)$
$\quad = {\textstyle{1\over 4}}[(kn)^2+(kl)^2+(nm)^2+(nl)^2]$
$\quad = {\textstyle{1\over 4}}[(d-b)^2+(a-c)^2+(a+c)^2+(d+b)^2]$
$\quad = {\textstyle{1\over 4}}(2a^2+2b^2+2c^2+2d^2)$
$\quad = {\textstyle{1\over 4}}(2N+2N)=N.$	(10)

See also Prime Factorization Algorithms