Eulerova expanzní metoda

Eulerova metoda rozkladu na rozklad je technika rozkladu čísla tak, že je zapsáno jako součet dvou čtverců dvěma různými způsoby. Číslo lze například zapsat jako nebo jako a Eulerova metoda dává rozšíření . $1000009$ $1000^{2}+3^{2}$ $972^{2}+235^{2}$ $1000009=293\cdot 3413$

Historie

Myšlenku, že dvě různé reprezentace lichého kladného čísla mohou vést k rozkladu, poprvé navrhl Marin Mersenne . Široce se však používala až poté, co byla o sto let později přijata Eulerova metoda. Triumfem metody, která nyní nese Eulerovo jméno, bylo rozklad čísla , které bylo dříve považováno za prvočíslo, i když podle všech hlavních testů prvočísel nebylo pseudoprvočíslo . $1000009$

Eulerova metoda faktorizace je účinnější než Fermatova metoda pro čísla, jejichž dělitelé si nejsou blízcí, a potenciálně výrazně efektivnější než zkušební dělení, pokud lze dostatečně rychle najít dvoučtvercovou reprezentaci čísel. Eulerův vývoj umožnil mnohem rychleji najít rozšíření čísel a vyvinout velké tabulky rozšíření čísel. Metody používané k nalezení čísel jako součtu dvou čtverců jsou v podstatě stejné jako pro nalezení rozdílu čtverců ve Fermatově faktorizační metodě .

Nevýhody

Velkou nevýhodou Eulerovy rozkladové metody je skutečnost, že ji nelze použít k rozkladu celých čísel s prvočinitelem ve tvaru 4k + 3, který je zahrnut do prvočíselného rozkladu s lichým stupněm, protože taková čísla nelze reprezentovat jako součet dvou čtverců. Lichá složená čísla tvaru 4k + 1 jsou často součinem dvou prvočísel tvaru 4k + 3 (například 3053 = 43 × 71) a nelze je rozšířit pomocí Eulerovy metody.

Toto omezení způsobilo, že Eulerova dekompoziční metoda je nežádoucí pro počítačové dekompoziční algoritmy , protože žádný uživatel, který se pokouší aplikovat metodu na náhodné číslo, pravděpodobně nebude vědět, zda bude Eulerova metoda na toto číslo použitelná. Teprve relativně nedávno se objevily pokusy vyvinout Eulerovu metodu v počítačových algoritmech pro speciální čísla, pro které je Eulerova metoda jistě použitelná.

Teoretický základ

Brahmagupta-Fibonacci identita říká, že součin dvou součtů dvou čtverců je součtem dvou čtverců. Eulerova metoda se opírá o tuto větu, ale lze ji považovat za inverzní přístup k větě, pokud je dán , hledáme rozklad na součin dvou čtverců. ${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2))$ $n$

Nejprve to dedukujeme

{\displaystyle a^{2}-c^{2}=d^{2}-b^{2))

a faktorizovat obě části

(ac)(a+c)=(db)(d+b)

(jeden)

Nyní nechť k = gcd ( a - c , d - b ) a h = gcd ( a + c , d + b ), takže existují čísla, pro která $l,m,l',m'$

$(ac)=kl$ ,
$(db)=km$ , gcd( l , m ) = 1
$(a+c)=hm'$ ,
$(d+b)=hl'$ , gcd( l , m ) = 1

Po dosazení do (1) dostaneme

klhm'=kmhl'

Po snížení společných faktorů dostaneme

lm'=l'm

Nyní používáme skutečnost, že a jsou coprime, abychom dostali $(l,m)$ $\left(l',m'\right)$

$l=l'$
$m=m'$

Takto,

$(ac)=kl$
$(db)=km$
$(a+c)=hm$
$(d+b)=hl$

Nyní vidíme, že m = gcd( a + c , d - b ) a l = gcd( a - c , d + b )

Po aplikaci identity Brahmagupta-Fibonacciho dostaneme

\left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=\left(kl-hm\right)^{2 }+(km+hl)^{2}={\bigl (}(ac)-(a+c){\bigr )}^{2}+{\bigl (}(db)+(d+b) {\bigr )}^{2}=(2c)^{2}+(2d)^{2}=4n,

\left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km -hl)^{2}={\bigl (}(ac)+(a+c){\bigr )}^{2}+{\bigl (}(db)-(d+b){\bigr ) }^{2}=(2a)^{2}+(2b)^{2}=4n.

Protože každý faktor je součtem dvou čtverců, jeden z nich musí obsahovat obě sudá čísla - buď , nebo . Bez ztráty obecnosti budeme předpokládat, že čísla v páru jsou sudá. Zhroucení se změní v $(k,h)$ $(l,m)$ $(k,h)$

n=\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\ vpravo)\left(l^{2}+m^{2}\vpravo).\,

Příklad

Vzhledem k tomu: ${\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2))$

Z výše uvedených vzorců máme:

a = 1000	(A) a − c = 28	gcd[A,C] k = 4
b = 3	(B) a + c = 1972	gcd[B,D] h = 34
c = 972	(C) d − b = 232	l = 7
d = 235	(D) d + b = 238	m = 58

Takto,

1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\ vpravo]\cdot \left(7^{2}+58^{2}\right)\,

=\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,

=(4+289)\cdot (49+3364)\,

=293\cdot 3413\,

Poznámky

Literatura

Oystein Or. Eulerova metoda faktorizace // Teorie čísel a její historie . - 1988. - S. 59-64 . - ISBN 0-486-65620-9 .
James McKee. Přeměna Eulerovy faktoringové metody na faktorovací algoritmus // Bulletin London Mathematical Society. - 1996. - T. 4 , no. 28 . — S. 351–355 . - doi : 10.1112/blms/28.4.351 .

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin