Cunningham-Projekt

Das Cunningham-Projekt ist ein Gemeinschaftsprojekt, das 1925 begann, um Zahlen der Form b ⁿ ± 1 für b = 2, 3, 5, 6, 7, 10, 11, 12 und große n zu faktorisieren . Das Projekt ist nach Allan Joseph Champneys Cunningham benannt , der die erste Version der Tabelle zusammen mit Herbert J. Woodall veröffentlichte . ^[¹^] Es existieren drei gedruckte Versionen der Tabelle, die jüngste erschien 2002, ^[²^] sowie eine Online-Version von Samuel Wagstaff . ^[³^]

Die aktuellen Grenzwerte der Exponenten sind:

Base	2	3	5	6	7	10	11	12
Limit	1500	900	600	550	500	450	400	400
Aurifeuillean (LM) Grenze	3000	1800	1200	1100	1000	900	800	800

Faktoren der Cunningham-Zahl

Aus einer Cunningham-Zahl lassen sich zwei Arten von Faktoren ableiten, ohne dass ein Faktorisierungsalgorithmus benötigt wird : algebraische Faktoren von Binomialzahlen (z. B. Differenz zweier Quadrate und Summe zweier Kuben ), die vom Exponenten abhängen, und Aurifeuille-Faktoren , die sowohl von der Basis als auch vom Exponenten abhängen.

Algebraische Faktoren

Aus der elementaren Algebra,

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

für alle k , und

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

Für ungerades k $gilt$ : $b²n - 1 = (bn - 1)(bn + 1)$ . Wenn m also n teilt , sind $bm$ $-$ $1$ und $bm$ $+ 1$ Faktoren von $bn$ $- 1$ , falls der Quotient von $n$ durch m gerade ist ; ist der Quotient ungerade $,$ ist nur die erste Zahl ein Faktor. $bm$ $+ 1$ $ist$ ein Faktor von $bn$ $-$ $1$ , wenn m n teilt und der Quotient ungerade ist.

Tatsächlich,

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

Und

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

Weitere Informationen finden Sie auf dieser Seite .

Aurifeuillean-Faktoren

Wenn die Zahl eine bestimmte Form hat (der genaue Ausdruck variiert mit der Basis), kann die Aurifeuille-Faktorisierung verwendet werden, die ein Produkt aus zwei oder drei Zahlen liefert. Die folgenden Gleichungen geben die Aurifeuille-Faktoren für die Basen des Cunningham-Projekts als Produkt von F , L und M an : ^{[ 4 ]}

Sei b = s ² × k mit quadratfreiem k , wenn eine der Bedingungen erfüllt ist, dann habe ich eine Aurifeuille-Faktorisierung. $\Phi _{n}(b)$

(i) und

k\equiv 1{\pmod {4}}

n\equiv k{\pmod {2k}};

(ii) und

k\equiv 2,3{\pmod {4}}

n\equiv 2k{\pmod {4k}}.

B	Nummer	F	L	M	Andere Definitionen
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	T² − 5^{k +1}T + 5^{2 k +1}	T² + 5^{k +1}T + 5^{2 k +1}	T = 5 ^{2 k +1} + 1
6	6 ^{12 k +6} + 1	6 ^{4 k +2} + 1	T² − 6^{k +1}T + 6^{2 k +1}	T² + 6^{k +1}T + 6^{2 k +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(10 ^{3 k +2} ) + 10 ^{k +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

Andere Faktoren

Nachdem die algebraischen und aurifeuilleschen Faktoren entfernt wurden, haben die übrigen Faktoren von $b n \pm 1$ stets die Form $2 kn + 1$ , da die Faktoren von $b n - 1$ alle Faktoren von bn sind und die Faktoren von $b$ $n$ $+ 1$ alle Faktoren von bn sind . Für Primzahlen n sind weder algebraische noch aurifeuillesche Faktoren möglich, außer den trivialen Faktoren ( $b$ $- 1$ für $b$ $n$ $- 1$ und $b$ $+ 1$ für $b $ $n$ $+ 1$ ). Bei Mersenne-Zahlen sind die trivialen Faktoren für Primzahlen n nicht möglich , daher haben alle Faktoren die Form $2$ $kn$ $+ 1$ . Im Allgemeinen sind alle Faktoren von $($ $b$ $n$ $- 1) /($ $b$ $- 1)$ von der Form $2$ $kn$ $+ 1,$ wobei $b$ $\geq 2$ und n eine Primzahl ist, außer wenn n $b$ $- 1$ teilt , in welchem Fall $($ $b$ $n$ $- 1) /($ $b$ $- 1) durch$ n selbst teilbar ist . $\Phi _{n}(b)$ $\Phi _{2n}(b)$

Cunningham-Zahlen der Form $b n -1$ sind nur dann Primzahlen, wenn b = 2 und n eine Primzahl ist, wobei n ≥ 2 gilt; dies sind die Mersenne-Zahlen. Zahlen der Form $b n +1$ sind nur dann Primzahlen, wenn b gerade und n eine Zweierpotenz ist , wobei $n \geq 2 gilt; dies sind die verallgemeinerten Fermat-Zahlen, die$ Fermat-Zahlen sind, wenn b = 2 gilt. Jeder Faktor einer Fermat-Zahl $2 n +1$ hat die Form $k \cdot 2 n +2 + 1$ .

Notation

b ^n -1 wird als b n- bezeichnet. Analog dazu wird b ^n +1 als b n + bezeichnet. Bei Zahlen der für die Aurifeuille-Faktorisierung erforderlichen Form werden L und M in den obigen Produkten mit b n L und b n M bezeichnet . ^[⁵^] Die Bezeichnungen b n- und b n + beziehen sich auf die Zahl, von der alle algebraischen und Aurifeuille-Faktoren entfernt wurden. Beispielsweise haben Mersenne-Zahlen die Form 2 n- und Fermat-Zahlen die Form 22 ⁿ +; die von Aurifeuille 1871 faktorisierte Zahl war das Produkt von 2,58L und 2,58M.

Siehe auch

Cunningham-Zahl
ECMNET und NFS@Home , zwei Kooperationen, die für das Cunningham-Projekt arbeiten
Die Great Internet Mersenne Prime Search , die auch ein Projekt zur Faktorisierung von Mersenne-Zahlen mittels elliptischer Kurvenfaktorisierung besitzt.

Referenzen

^ Cunningham, Allan JC; Woodall, HJ (1925). Faktorisierung von y ⁿ ± 1, y = 2, 3, 5, 6, 7, 10, 11, 12, bis zu hohen Potenzen n . Hodgson .
Brillhart , John ; Lehmer, Derrick H .; Selfridge, John L .; Tuckerman, Bryant; Wagstaff, Samuel S. (2002). Faktorisierungen von b  ⁿ ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 bis zu hohen Potenzen . Contemporary Mathematics. Band 22. AMS. doi : 10.1090/conm/022 . ISBN 9780821850787Die
^ „Das Cunningham-Projekt“ . Abgerufen am 23. November 2023 .
^ „Haupttabellen von Cunningham“ . Abgerufen am 15. Januar 2025 .Am Ende der Tabellen 2LM, 3+, 5-, 6+, 7+, 10+, 11+ und 12+ finden sich Formeln, die die Aurifeuille-Faktorisierungen detailliert beschreiben.
^ „Erläuterung der Notation auf den Seiten“ . Abgerufen am 23. November 2023 .

Externe Links

Homepage des Cunningham-Projekts
Faktorisierungen von b ⁿ ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 bis zu hohen Potenzen, zweite Auflage
Faktorisierungen von b ⁿ ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 bis zu hohen Potenzen, dritte Auflage
Haupttabelle des Cunningham-Projekts
Älterer Haupttisch des Cunningham-Projekts
Haupttabelle der dritten Auflage des Cunningham-Buches
Maschinenlesbare Cunningham-Tabellen
Das Cunningham-Projekt
Brent-Montgomery-te Riele-Tabelle (Cunningham-Tabellen für höhere Basen (Basen 13 ≤ b ≤ 99, perfekte Potenzen ausgeschlossen, da eine Potenz von b ⁿ auch eine Potenz von b ist ))
Online-Faktorsammlung
Cunningham-Projekt auf Prime Wiki
Cunningham-Projekt auf PrimePages

[1] Cunningham, Allan JC; Woodall, HJ (1925). Faktorisierung von y ⁿ ± 1, y = 2, 3, 5, 6, 7, 10, 11, 12, bis zu hohen Potenzen n . Hodgson .

[2] Brillhart , John ; Lehmer, Derrick H .; Selfridge, John L .; Tuckerman, Bryant; Wagstaff, Samuel S. (2002). Faktorisierungen von b <sup> ⁿ ± 1</sup>, b = 2, 3, 5, 6, 7, 10, 11, 12 bis zu hohen Potenzen . Contemporary Mathematics. Band 22. AMS. doi : 10.1090/conm/022 . ISBN 9780821850787Die

[3] „Das Cunningham-Projekt“ . Abgerufen am 23. November 2023 .

[4] „Haupttabellen von Cunningham“ . Abgerufen am 15. Januar 2025 .Am Ende der Tabellen 2LM, 3+, 5-, 6+, 7+, 10+, 11+ und 12+ finden sich Formeln, die die Aurifeuille-Faktorisierungen detailliert beschreiben.

[5] „Erläuterung der Notation auf den Seiten“ . Abgerufen am 23. November 2023 .

[

[

[

[ 4 ]

[