Fermats faktoriseringsmetod

Fermats faktoriseringsmetod , uppkallad efter Pierre de Fermat , är baserad på representationen av ett udda heltal som skillnaden mellan två kvadrater :

N=a^{2}-b^{2}.

Den skillnaden är algebraiskt faktorbar som $(a+b)(ab)$ ; om ingen av faktorn är lika med en, är det en korrekt faktorisering av N .

Varje udda tal har en sådan representation. Faktum är att om $N=cd$ är en faktorisering av N , då

N=\left({\frac {c+d}{2}}\right)^{2}-\left({\ frac {cd}{2}}\right)^{2}

Eftersom N är udda, är c och d också udda, så dessa halvor är heltal. (En multipel av fyra är också en skillnad på kvadrater: låt c och d vara jämna.)

I sin enklaste form kan Fermats metod vara till och med långsammare än provdelning (värsta fall). Icke desto mindre är kombinationen av provdelning och Fermats mer effektiv än båda.

Grundläggande metod

Man provar olika värden på a , i hopp om att ${\displaystyle a^{2}-N=b^{2}} ,$ en kvadrat.

  FermatFactor(N):  // N bör vara udda  a ← tak(sqrt(N)) b2 ← a*a - N  upprepa tills  b2  är  en kvadrat: a ← a + 1 b2 ← a*a - N // ekvivalent: // b2 ← b2 + 2*a + 1  // a ← a + 1  returnera  a - sqrt(b2)  // eller a + sqrt(b2)

Till exempel, för att faktorn $N=5959$ , är första försöket för a kvadratroten ur $5959$ avrundat uppåt till nästa heltal, vilket är $78$ . Sedan, $b^{2}=78^{2}-5959=125$ . Eftersom 125 inte är en kvadrat, görs ett andra försök genom att öka värdet på a med 1. Det andra försöket misslyckas också, eftersom 282 återigen inte är en kvadrat.

Prova:	1	2	3
a	78	79	80
b ²	125	282	441
b	11.18	16,79	21

Det tredje försöket ger den perfekta kvadraten på 441. Så, $a=80$ , $b=21$ , och faktorerna för $5959$ är $ab= 59$ och $a+b=101$ .

Antag att N har fler än två primtalsfaktorer. Den proceduren hittar först faktoriseringen med de minsta värdena av a och b . Det vill säga, $a+b$ är den minsta faktorn ≥ kvadratroten av N , och så $ab=N/(a+b)$ är den största faktorn ≤ rot- N . Om proceduren finner ${\displaystyle N=1\cdot N} ,$ visar det att N är primtal.

För $N=cd$ , låt c vara den största subrotfaktorn. $a=(c+d)/2$ , så antalet steg är ungefär $(c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2 =({\sqrt {N}}-c)^{2}/2c$ .

Om N är primtal (så att $c=1$ ), behöver man $O(N)$ steg. Detta är ett dåligt sätt att bevisa primat. Men om N har en faktor nära sin kvadratrot fungerar metoden snabbt. Mer exakt, om c skiljer sig mindre än ${\left(4N\right)}^{1/4}$ från ${\sqrt {N}}$ , metoden kräver bara ett steg; detta är oberoende av storleken på N . ^{[ citat behövs ]}

Fermats och försöksavdelning

Överväg att försöka faktorisera primtalet N = 2345678917 , men beräkna även b och a − b genomgående. När vi går upp från ${\sqrt {N}}$ kan vi tabulera:

a	48,433	48,434	48,435	48,436
b ²	76,572	173,439	270,308	367,179
b	276,7	416,5	519,9	605,9
a − b	48 156,3	48 017,5	47 915,1	47 830,1

I praktiken skulle man inte bry sig om den sista raden förrän b är ett heltal. Men observera att om N hade en subrotfaktor över ${\displaystyle ab=47830.1} ,$ skulle Fermats metod redan ha hittat den.

Provdelning skulle normalt försöka upp till 48 432; men efter bara fyra Fermat-steg behöver vi bara dela upp till 47830, för att hitta en faktor eller bevisa primaalitet.

Allt detta tyder på en kombinerad factoringmetod. Välj några bundna $c>{\sqrt {N}}$ ; använd Fermats metod för faktorer mellan ${\sqrt {N}}$ och $c$ . Detta ger en gräns för provdelning som är $c-{\sqrt {c^{2}-N}}$ . I exemplet ovan, med $c=48436$ är gränsen för provdelning 47830. Ett rimligt val kan vara $c=55000$ vilket ger en gräns på 28937.

I detta avseende ger Fermats metod minskande avkastning. Man skulle säkert sluta före denna punkt:

a	60 001	60 002
b ²	1,254,441,084	1,254,561,087
b	35 418,1	35 419,8
a − b	24 582,9	24 582,2

Siktförbättring

När man betraktar tabellen för $N=2345678917$ kan man snabbt se att inget av värdena för $b^{2}$ är kvadrater:

a	48,433	48,434	48,435	48,436
b ²	76,572	173,439	270,308	367,179
b	276,7	416,5	519,9	605,9

Det är inte nödvändigt att beräkna alla kvadratrötterna i ${\displaystyle a^{2}-N} ,$ och inte ens undersöka alla värden för $en$ . Kvadrater är alltid kongruenta med 0, 1, 4, 5, 9, 16 modulo 20. Värdena upprepas med varje ökning av $a$ med 10. I det här exemplet är N 17 mod 20, så subtrahera 17 mod 20 (eller addera 3) , $a^{2}-N$ ger 3, 4, 7, 8, 12 och 19 modulo 20 för dessa värden. Det är uppenbart att endast de fyra från denna lista kan vara en kvadrat. Således $a^{2}$ vara 1 mod 20, vilket betyder att $a$ är 1, 9, 11 eller 19 mod 20; det kommer att producera en $b^{2}$ som slutar på 4 mod 20 och, om kvadratisk, kommer $b$ att sluta på 2 eller 8 mod 10.

Detta kan utföras med vilken modul som helst. Använder samma $N=2345678917$ ,

modulo 16:	Rutor är	0, 1, 4 eller 9
	N mod 16 är	5
	så $a^{2}$ kan bara vara	9
	och $ett$ måste vara	3 eller 5 eller 11 eller 13 modulo 16
modulo 9:	Rutor är	0, 1, 4 eller 7
	N mod 9 är	7
	så $a^{2}$ kan bara vara	7
	och $ett$ måste vara	4 eller 5 modulo 9

Man väljer vanligtvis en potens av olika primtal för varje modul.

Givet en sekvens av a -värden (start, slut och steg) och en modul kan man fortsätta så här:

 FermatSieve(N, astart, aend, astep, modul) a ← astart  do  modulus  times  : b2 ← a*a - N  om  b2 är en kvadrat, modulo modulus: FermatSieve(N, a, aend, astep * modulus, NextModulus)  endif  a ← a + astp  enddo

Men rekursionen stoppas när få a -värden återstår; det vill säga när (aend-astart)/astep är liten. Dessutom, eftersom en stegstorlek är konstant, kan man beräkna successiva b2 med tillägg.

Multiplikatorförbättring

Fermats metod fungerar bäst när det finns en faktor nära kvadratroten av N .

Om det ungefärliga förhållandet mellan två faktorer ( $d/c$ ) är känt, kan ett rationellt tal $v/u$ väljas nära det värdet. $Nuv=cv\cdot du$ , och Fermats metod, applicerad på Nuv , kommer snabbt att hitta faktorerna $cv$ och ${\displaystyle du} .$ Då $\gcd(N,cv)=c$ och $\gcd(N,du)=d$ . (Om inte c delar u eller d delar v .)

I allmänhet, om förhållandet inte är känt, kan olika $u/v$ -värden prövas, och försök att faktorisera varje resulterande Nuv . R. Lehman utarbetade ett systematiskt sätt att göra detta, så att Fermats plusförsöksdivision kan faktorisera N i $O(N^{1/3})$ tid.

Andra förbättringar

De grundläggande idéerna för Fermats faktoriseringsmetod är grunden för den kvadratiska sikten och den allmänna talfältssikten , de mest kända algoritmerna för att faktorisera stora semiprimtal , som är de "värsta fallet". Den primära förbättringen som kvadratsikten gör jämfört med Fermats faktoriseringsmetod är att istället för att helt enkelt hitta en kvadrat i sekvensen av ${\displaystyle a^{2}-n} ,$ hittar den en delmängd av element i denna sekvens vars produkt är en kvadrat, och den gör detta på ett mycket effektivt sätt. Slutresultatet är detsamma: en skillnad på kvadratmod n som, om den inte är trivial, kan användas för att faktorisera n .

Se även

Anteckningar

Fermat (1894), Oeuvres de Fermat , vol. 2, sid. 256
McKee, J (1999). "Speeding Fermats factoring-metod" . Beräkningsmatematik . 68 (228): 1729–1737. doi : 10.1090/S0025-5718-99-01133-3 .

externa länkar

Fermats faktoriseringstid , på blogspot.in
Fermats Factorization Online Calculator , på windowspros.ru

Talteoretiska algoritmer
Primalitetstester	AKS APR Baillie–PSW Elliptisk kurva Pocklington Fermat Lucas Lucas-Lehmer Lucas–Lehmer–Riesel Proths teorem Pépins Kvadratisk Frobenius Solovay–Strassen Miller–Rabin
Prime-genererande	Sil av Atkin Sil av Eratosthenes Sikt av Pritchard Sikt av Sundaram Hjulfaktorisering
Heltalsfaktorisering	Fortsatt fraktion (CFRAC) Dixons Lenstra elliptisk kurva (ECM) Eulers Pollards rho p − 1 p + 1 Kvadratisk sikt (QS) General number field sieve (GNFS) Specialnummerfältsåll (SNFS) Rationell såll Fermats Shanks fyrkantiga former Försöksuppdelning Shors
Multiplikation	Forntida egyptisk Lång Karatsuba Toom-Cook Schönhage–Strassen Fürers
euklidisk division	Binär Chunking Fourier Goldschmidt Newton-Raphson Lång Kort SRT
Diskret logaritm	Baby-step jätte-step Pollard rho Pollard känguru Pohlig–Hellman Indexkalkyl Funktion fältsikt
Största gemensamma delare	Binär euklidisk Förlängd euklidisk Lehmers
Modulär kvadratrot	Cipolla Pocklingtons Tonelli–Shanks Berlekamp Kunerth
Andra algoritmer	Chakravala Cornacchia Exponentiering genom kvadrering Heltals kvadratrot Heltalsrelation ( LLL ; KZ ) Modulär exponentiering Montgomery reduktion Schoof Trachtenbergs system
Kursiv stil indikerar att algoritmen är för antal speciella former