Eulerova faktorizační metoda

Eulerova faktorizační metoda, pojmenovaná po Leonhardu Eulerovi, je metoda hledání prvočíselného rozkladu založená na možnosti zapsat zkoumané přirozené číslo N jako součet dvou čtverců dvěma různými způsoby:

\ N = a^2+ b^2 = c^2+ d^2

Odečtením c^2 a b^2 od obou stran získáváme rozdíl dvou čtverců:

\ a^2 - c^2 = d^2 - b^2

a odtud plyne, že

(a - c)\cdot(a + c) = (d - b)\cdot(d + b)

Bez újmy na obecnosti lze předpokládat, že d a b jsou buď obě sudá, nebo lichá, tedy že jejich rozdíl bude sudý. Nechť k je největší společný dělitel (a - c) a(d - b), tedy

(a - c) = kl, (d - b) = km a NSD (l, m) = 1

Dosadíme-li získaný vztah do rovnosti součinů výše, máme l\cdot(a + c) = m\cdot(d + b)

Protože jsou l a m nesoudělná, musí být (a + c) dělitelné m. Tato myšlenka dává:

\ (a + c) = mn a \ (d + b) = ln

Ze získaných rovností plyne 2c=(a+c)-(a-c)=mn-kl a 2d=(d-b)+(d+b)=km+ln, odkud po dosazení do původního zapsání N máme:

N=\frac{1}{4}\left[\left(mn-kl\right)^2+\left(km+ln\right)^2\right] = \frac{1}{4}\left(m^2n^2+k^2l^2+k^2m^2+l^2n^2\right)=\frac{1}{4}\left(m^2+l^2\right)\left(k^2+n^2\right)

Kategorie:Faktorizační algoritmy