Eulers faktoriseringsmetod

Eulers faktoriseringsmetod är en teknik för att faktorisera ett tal genom att skriva det som summan av två kvadrater på två olika sätt. Till exempel kan talet $1000009$ skrivas som $1000^{2}+3^{2}$ eller som $972^{2}+ 235^{2}$ och Eulers metod ger faktoriseringen $1000009=293\cdot 3413$ .

Tanken att två distinkta representationer av ett udda positivt heltal kan leda till en faktorisering föreslogs tydligen först av Marin Mersenne . Det användes dock inte i stor utsträckning förrän hundra år senare av Euler. Hans mest berömda användning av metoden som nu bär hans namn var att faktorisera siffran ${\displaystyle 1000009} ,$ som tydligen tidigare troddes vara primtal även om det inte är ett pseudoprimtal enligt något större primalitetstest.

Eulers faktoriseringsmetod är mer effektiv än Fermats för heltal vars faktorer inte ligger nära varandra och potentiellt mycket effektivare än försöksdivision om man kan hitta representationer av tal som summor av två kvadrater någorlunda enkelt. Eulers utveckling möjliggjorde i slutändan mycket effektivare faktorisering av siffror och, på 1910-talet, utvecklingen av stora faktortabeller som gick upp till cirka tio miljoner [ . Metoderna som används för att hitta representationer av tal som summor av två kvadrater är i huvudsak desamma som med att hitta skillnader mellan kvadrater i Fermats faktoriseringsmetod .

Nackdel och begränsning

Den stora nackdelen med Eulers faktoriseringsmetod är att den inte kan användas för att faktorisera ett heltal med någon primfaktor av formen 4 k + 3 som förekommer med en udda potens i dess primtalsfaktorisering, eftersom ett sådant tal aldrig kan vara summan av två kvadrater . Även udda sammansatta tal av formen 4 k + 1 är ofta produkten av två primtal av formen 4 k + 3 (t.ex. 3053 = 43 × 71) och kan återigen inte faktoriseras med Eulers metod.

Denna begränsade tillämplighet har gjort Eulers faktoriseringsmetod ogynnsam för datorfaktoriseringsalgoritmer , eftersom alla användare som försöker faktorisera ett slumpmässigt heltal sannolikt inte vet om Eulers metod faktiskt kan tillämpas på heltalet i fråga. Det är först relativt nyligen som det har gjorts försök att utveckla Eulers metod till datoralgoritmer för användning på specialiserade tal där det är känt att Eulers metod kan tillämpas.

Teoretisk grund

Brahmagupta -Fibonacci-identiteten säger att produkten av två summor av två kvadrater är summan av två kvadrater. Eulers metod bygger på detta teorem men det kan ses som det omvända, givet $n=a^{2}+b^{2}=c^{2 }+d^{2}$ finner vi $n$ som en produkt av summan av två kvadrater.

Första slutsatsen

$a^{2}-c^{2}=d^{2}-b^{2}$

och faktor båda sidor för att få

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

Låt nu $k=\operatörsnamn {gcd} (ac,db)$ och $h= \operatorname {gcd} (a+c,d+b)$ så att det finns några konstanter $l,m,l',m'$ som uppfyller

• $(ac)=kl$ ,
• $(db)=km$ ,

$\operatörsnamn {gcd} (l,m)=1$

• $(a+c)=hm'$ ,
• $(d+b)=hl'$ ,

$\operatörsnamn {gcd} (l',m')=1$

Att ersätta dessa i ekvation (1) ger

$klhm'=kmhl'$

Att avbryta gemensamma faktorer ger

$lm'=l'm$

​​nu använder det faktum att $(l,m)$ och $\left(l',m'\right)$ är par av relativt primtal. hitta det

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

Så

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

Vi ser nu att $m=\operatörsnamn {gcd} (a+c,db)$ och ${ \displaystyle l=\operatörsnamn {gcd} (ac,d+b)}$

Genom att tillämpa Brahmagupta-Fibonacci-identiteten får vi

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

Eftersom varje faktor är en summa av två kvadrater måste en av dessa innehålla båda jämna tal: antingen $(k,h)$ eller $(l,m)$ . Utan förlust av generalitet, antag att paret $(k,h)$ är jämnt. Faktoriseringen blir då

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

Arbetat exempel

Sedan: $\ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}$

vi har från formeln ovan:

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

Således,

$1000009=\left[\left({\frac {4}{2}} \right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\cdot \left[\left({\frac {14}{2}}\ höger)^{2}+\left({\frac {116}{2}}\right)^{2}\right]\,$

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

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

$=293\cdot 3413\,$

Pseudokod

funktion Euler_factorize(int n) -> lista[int] om is_prime(n) sedan print("Number kan inte faktoriseras") avsluta funktion for-loop från a=1 till a=tak(sqrt(n)) b2 = n - a*a b = floor(sqrt(b2)) if b*b==b2 break loop bevara a,b if a*a+b*b!=n then print("Det gick inte att hitta något uttryck för n som summa av kvadrater ") avsluta funktionen for-loop från c=a+1 till c=tak(sqrt(n)) d2 = n - c*c d = floor(sqrt(d2)) om d*d==d2 bryt slingan bevarande c ,d om c*c+d*d!=n sedan print("Det gick inte att hitta ett andra uttryck för n som summan av kvadrater") avsluta funktion A = ca, B = c+a C = bd, D = b+ dk = GCD(A,C)//2, h = GCD(B,D)//2 l = GCD(A,D)//2, m = GCD(B,C)//2 faktor1 = k* k + h*h faktor2 = l*l + m*m returlista[ faktor1, faktor2 ]

•   Ore, Oystein (1988). "Eulers faktoriseringsmetod" . Talteori och dess historia . s. 59–64 . ISBN 978-0-486-65620-5 .
• McKee, James (1996). "Att förvandla Eulers faktoriseringsmetod till en faktoriseringsalgoritm". Bulletin från London Mathematical Society . 4 (28): 351–355. doi : 10.1112/blms/28.4.351 .