info prev up next book cdrom email home

Excludent Factorization Method

Also known as the difference of squares. It was first used by Fermat and improved by Gauß. Gauss looked for Integers $x$ and $y$ satisfying

\begin{displaymath}
y^2\equiv x^2-N\ \left({{\rm mod\ } {E}}\right)
\end{displaymath}

for various moduli $E$. This allowed the exclusion of many potential factors. This method works best when factors are of approximately the same size, so it is sometimes better to attempt $mN$ for some suitably chosen value of $m$.

See also Prime Factorization Algorithms




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