Fermat-Faktorisierung Wir wollen NNN, eine ungerade natürliche Zahl faktorisieren. Bei der Fermatschen Faktorisierungsmethode versucht man nun die Zahl NNN als Differenz von Quadratzahlen zu schreiben: N=u2−w2,N=u^2-w^2,N=u2−w2, denn dann erhält man die Zerlegung N=(u−w)(u+w).N=(u-w)(u+w).N=(u−w)(u+w). Wir schreiben u2−N=w2u^2-N=w^2u2−N=w2 und erkennen, dass u2≥Nu^2\geq Nu2≥N und damit auch u≥⌈N⌉.u\geq \lceil\sqrt{N}\rceil.u≥⌈N⌉. Wir testen also für u=⌈N⌉,⌈N⌉+1,⌈N⌉+2,⌈N⌉+3,…u=\lceil\sqrt{N}\rceil,\lceil\sqrt{N}\rceil+1,\lceil\sqrt{N}\rceil+2,\lceil\sqrt{N}\rceil+3,\dotsu=⌈N⌉,⌈N⌉+1,⌈N⌉+2,⌈N⌉+3,… ob u2−Nu^2-Nu2−N eine Quadratzahl ist.