info prev up next book cdrom email home

Euler's Factorization Method

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

\begin{displaymath}
N=a^2+b^2=c^2+d^2,
\end{displaymath} (1)

so
\begin{displaymath}
a^2-c^2=d^2-b^2
\end{displaymath} (2)


\begin{displaymath}
(a-c)(a+c)=(d-b)(d+b).
\end{displaymath} (3)

Let $k$ be the Greatest Common Divisor of $a-c$ and $d-b$ so
$\displaystyle a-c$ $\textstyle =$ $\displaystyle kl$ (4)
$\displaystyle d-b$ $\textstyle =$ $\displaystyle km$ (5)
$\displaystyle (l,m)$ $\textstyle =$ $\displaystyle 1,$ (6)

(where $(l,m)$ denotes the Greatest Common Divisor of $l$ and $m$), and
\begin{displaymath}
l(a+c)=m(d+b).
\end{displaymath} (7)

But since $(l,m)=1$, $m\vert a+c$ and
\begin{displaymath}
a+c=mn,
\end{displaymath} (8)

which gives
\begin{displaymath}
b+d=ln,
\end{displaymath} (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




© 1996-9 Eric W. Weisstein
1999-05-25