Cunningham-projektet

Cunningham -projektet är ett samarbete som startade 1925 för att faktorisera tal av formen b ⁿ ± 1 för b = 2, 3, 5, 6, 7, 10, 11, 12 och stora n . Projektet är uppkallat efter Allan Joseph Champneys Cunningham , som publicerade den första versionen av tabellen tillsammans med Herbert J. Woodall . Det finns tre tryckta versioner av tabellen, den senaste publicerad 2002, samt en onlineversion.

Exponenternas nuvarande gränser är:

Bas	2	3	5	6	7	10	11	12
Begränsa	1500	900	600	550	500	450	400	400
Aurifeuillian (LM) gräns	3000	1800	1200	1100	1000	900	800	800
Antal decimalsiffror för basgräns	452	430	420	428	423	451	417	432

Faktorer av Cunningham nummer

Två typer av faktorer kan härledas från ett Cunningham-tal utan att behöva använda en faktoriseringsalgoritm: algebraiska faktorer, som beror på exponenten, och Aurifeuillian-faktorer , som beror på både basen och exponenten.

Algebraiska faktorer

Från elementär algebra,

$(b^{kn}-1)=(b^{n}-1)\summa _{r =0}^{k-1}b^{rn}$

för alla k , och

$(b^{kn}+1)=(b^{n}+1 )\summa _{r=0}^{k-1}(-1)^{r}\cdot b^{rn}$

för udda k . Dessutom är b ^{2 n} − 1 = ( b ⁿ − 1)( b ⁿ + 1). Således, när m delar n , är b ^m − 1 och b ^m + 1 faktorer av b ⁿ − 1 om kvoten av n över m är jämn ; endast den första siffran är en faktor om kvoten är udda. b ^m + 1 är en faktor av b ⁿ − 1, om m delar n och kvoten är udda.

Faktiskt,

$b^{n}-1=\prod _{d\mid n}\Phi _{d}(b)$

och

$b^{n}+1=\prod _{d\mid 2n,\,d!\mid n}\Phi _{d}(b)$

Aurifeuillianska faktorer

Huvudartikel: Aurifeuillian faktorisering

När talet är av en viss form (det exakta uttrycket varierar med basen) kan Aurifeuilliansk faktorisering användas, vilket ger en produkt av två eller tre tal. Följande ekvationer ger Aurifeuillian-faktorer för Cunningham-projektets baser som en produkt av F , L och M :

Låt b = s ² × k med kvadratfritt k , om ett av villkoren gäller, så har $\Phi _{n}(b)$ aurifeuilliansk faktorisering.

(i) $k\equiv 1\mod 4$ och $n\equiv k{\pmod {2k}};$

(ii) $k\equiv 2,3{\pmod {4}}$ och $n\equiv 2k{\pmod {4k}}.$

b	siffra	F	L	M	Andra definitioner
2	2 4 k +2 + 1	1	2 2 k +1 − 2 k +1 + 1	2 2 k +1 + 2 k +1 + 1
3	3 6 k +3 + 1	3 2 k +1 + 1	3 2 k +1 − 3 k +1 + 1	3 2 k +1 + 3 k +1 + 1
5	5 10 k +5 − 1	5 2 k +1 − 1	T2 - 5 k +1 T + 5 2 k +1	T2 + 5k + 1T + 52k + 1 _	T = 5 2 k + 1 + 1
6	6 12 k +6 + 1	6 4 k +2 + 1	T 2 - 6 k +1 T + 6 2 k +1	T2 + 6k + 1T + 62k + 1 _	T = 6 2 k + 1 + 1
7	7 14 k +7 + 1	7 2 k +1 + 1	A - B	A + B	A = 7 6 k +3 + 3(7 4 k +2 ) + 3(7 2 k +1 ) + 1 B = 7 5 k +3 + 7 3 k +2 + 7 k +1
10	10 20 k +10 + 1	10 4 k +2 + 1	A - B	A + B	A = 10 8 k +4 + 5(10 6 k +3 ) + 7(10 4 k +2 ) + 5(10 2 k +1 ) + 1 B = 10 7 k +4 + 2(10 5 k + 3 ) + 2(103k + 2 ) + 10k + 1
11	11 22 k +11 + 1	11 2 k +1 + 1	A - B	A + B	A = 11 10 k +5 + 5(11 8 k +4 ) − 11 6 k +3 − 11 4 k +2 + 5(11 2 k +1 ) + 1 B = 11 9 k +5 + 11 7 k +4 − 11 5 k +3 + 11 3 k +2 + 11 k +1
12	12 6 k +3 + 1	12 2 k +1 + 1	12 2 k +1 − 6(12 k ) + 1	12 2 k +1 + 6(12 k ) + 1

Andra faktorer

När väl de algebraiska och aurifeuillianska faktorerna har tagits bort, är de andra faktorerna för b ⁿ ± 1 alltid av formen 2 kn + 1, eftersom de alla är faktorer av $\Phi _{n}(b)$ . När n är primtal är både algebraiska och aurifeuillianska faktorer inte möjliga, förutom de triviala faktorerna ( b − 1 för b ⁿ − 1 och b + 1 för b ⁿ + 1). För Mersenne-tal är trivialfaktorerna inte möjliga för primtal n , så alla faktorer är av formen 2 kn + 1. I allmänhet är alla faktorer av ( b ⁿ − 1) /( b − 1) av formen 2 kn + 1, där b ≥ 2 och n är primtal, förutom när n delar b − 1, i vilket fall ( b ⁿ − 1)/( b − 1) är delbart med n själv.

Cunningham-tal av formen b ⁿ − 1 kan bara vara primtal om b = 2 och n är primtal, förutsatt att n ≥ 2; det här är Mersenne-siffrorna. Tal av formen b ⁿ + 1 kan bara vara primtal om b är jämn och n är en potens av 2 , återigen under antagande av n ≥ 2; dessa är de generaliserade Fermat-talen, som är Fermat-tal när b = 2. Vilken faktor som helst av ett Fermat-tal 2 ^{2 n} + 1 är av formen k 2 ^{n +2} + 1.

Notation

b ⁿ − 1 betecknas som b , n −. På liknande sätt betecknas bn + 1 som b ^, n +. När det handlar om siffror av den form som krävs för Aurifeuilliansk faktorisering, används b , n L och b , n M för att beteckna L och M i produkterna ovan . Referenser till b , n − och b , n + är till talet med alla algebraiska och aurifeuillianska faktorer borttagna. Till exempel är Mersenne-tal av formen 2, n − och Fermat-tal har formen 2,2 ⁿ +; antalet Aurifeuille räknat 1871 var produkten av 2,58L och 2,58M.

Se även

• Cunningham nummer
• ECMNET och NFS@Home , två samarbeten som arbetar för Cunningham-projektet

externa länkar

• Cunningham-projektets hemsida
• Brent-Montgomery-te Riele-bord (Cunningham-bord för högre baser)
• Cunningham-bord på Prime Wiki