Euler ekspansionsmetode

Euler - faktoriseringsmetoden er en teknik til at faktorisere et tal ved at skrive det som summen af to kvadrater på to forskellige måder. For eksempel kan et tal skrives som eller som og Eulers metode giver udvidelsen af . $1000009$ $1000^{2}+3^{2}$ $972^{2}+235^{2}$ $1000009=293\cdot 3413$

Historie

Ideen om, at to forskellige repræsentationer af et ulige positivt tal kan føre til en dekomponering, blev først foreslået af Marin Mersenne . Det blev dog ikke brugt i stor udstrækning, før Eulers metode blev vedtaget hundrede år senere. Triumfen for den metode, der nu bærer Eulers navn, var faktoriseringen af et tal , der tidligere blev betragtet som primtal, selvom det ikke var pseudo -prime ved alle de vigtigste primalitetstest. $1000009$

Eulers faktoriseringsmetode er mere effektiv end Fermats metode for tal, hvis divisorer ikke er tætte, og potentielt signifikant mere effektiv end forsøgsdeling, hvis man kan finde tallenes to-kvadrat-repræsentation hurtigt nok. Eulers udvikling gjorde det muligt at finde udvidelsen af tal meget hurtigere og at udvikle store tabeller over udvidelse af tal. De metoder, der bruges til at finde tal som en sum af to kvadrater, er i det væsentlige de samme som til at finde forskellen på kvadrater i Fermats faktoriseringsmetode .

Ulemper

Den store ulempe ved Euler-faktoriseringsmetoden er, at den ikke kan bruges til at faktorisere heltal med en primfaktor på formen 4k + 3, som er inkluderet i primfaktoriseringen med en ulige grad, da sådanne tal ikke kan repræsenteres som en summen af to kvadrater. Selv ulige sammensatte tal på formen 4k + 1 er ofte produktet af to primtal på formen 4k + 3 (for eksempel 3053 = 43 × 71) og kan ikke udvides ved hjælp af Euler-metoden.

Denne begrænsning har gjort Euler-nedbrydningsmetoden uønsket for computerbaserede dekomponeringsalgoritmer , da enhver bruger, der forsøger at anvende metoden på et tilfældigt tal, næppe vil vide, om Euler-metoden vil være anvendelig på dette tal. Først for relativt nylig har der været forsøg på at udvikle Euler-metoden i computeralgoritmer for specielle tal, hvor Euler-metoden bestemt er anvendelig.

Teoretisk grundlag

Brahmagupta-Fibonacci identiteten siger, at produktet af to summer af to kvadrater er summen af to kvadrater. Eulers metode er afhængig af denne sætning, men kan ses som den omvendte tilgang til sætningen, hvis givet , leder vi efter en nedbrydning til produktet af to kvadrater. ${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2))$ $n$

Det udleder vi først

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

og faktoriser begge dele

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

(en)

Lad nu k = gcd ( a - c , d - b ) og h = gcd( a + c , d + b ), så der er nogle tal for hvilke $l,m,l',m'$

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

Efter indskiftning i (1) får vi

klhm'=kmhl'

Efter at have reduceret de fælles faktorer, får vi

lm'=l'm

Nu bruger vi det faktum, at og er coprime, så vi får $(l,m)$ $\left(l',m'\right)$

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

På denne måde

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

Nu ser vi, at m = gcd( a + c , d - b ) og l = gcd( a - c , d + b )

Efter at have anvendt Brahmagupta-Fibonacci-identiteten får vi

\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.

Da hver faktor er summen af to kvadrater, skal en af dem indeholde begge lige tal - enten , eller . Uden tab af generalitet vil vi antage, at tallene i parret er lige. Sammenbruddet bliver til $(k,h)$ $(l,m)$ $(k,h)$

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

Eksempel

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

Fra formlerne ovenfor har vi:

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

På denne måde

1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\ højre]\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\,

Noter

Litteratur

Oystein Or. Eulers faktoriseringsmetode // Talteori og dens historie . - 1988. - S. 59-64 . - ISBN 0-486-65620-9 .
James McKee. At omdanne Euler's Factoring Method til en Factoring Algorithm // Bulletin of the London Mathematical Society. - 1996. - T. 4 , no. 28 . — S. 351–355 . - doi : 10.1112/blms/28.4.351 .

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme