Projekt Cunningham - The Cunningham project

The Cunninghamův projekt je projekt, zahájený v roce 1925, do faktor čísla formuláře bⁿ ± 1 pro b = 2, 3, 5, 6, 7, 10, 11, 12 a větší n. Název projektu je Allan Joseph Champneys Cunningham, který publikoval první verzi tabulky společně s Herbert J. Woodall.^[1] K dispozici jsou tři tištěné verze tabulky, poslední publikovaná v roce 2002,^[2] stejně jako online verze.^[3]

Aktuální limity exponentů jsou:

Faktory Cunninghamových čísel

Z Cunninghamova čísla lze odvodit dva typy faktorů, aniž by bylo nutné použít faktorizační algoritmus: algebraické faktory, které závisejí na exponentu, a Aurifeuillianovy faktory, které závisejí jak na základně, tak na exponentu.

Algebraické faktory

Ze základní algebry,

${ displaystyle (b ^ {kn} -1) = (b ^ {n} -1) součet _ {r = 0} ^ {k-1} b ^ {rn}}$

pro všechny k, a

${ displaystyle (b ^ {kn} +1) = (b ^ {n} +1) součet _ {r = 0} ^ {k-1} (- 1) ^ {r} cdot b ^ {rn }}$

pro liché k. Navíc, b²ⁿ − 1 = (bⁿ − 1)(bⁿ + 1). Takže kdy m rozděluje n, b^m - 1 a b^m + 1 jsou faktory bⁿ - 1 pokud kvocient z n přes m je sudý; pouze první číslo je faktor, pokud je kvocient lichý. b^m + 1 je faktor bⁿ - 1, pokud m rozděluje n a kvocient je lichý.

Ve skutečnosti,

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

a

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

Aurifeuillian faktory

Když má číslo určitou formu (přesný výraz se liší podle báze), může být použita Aurifeuillianova faktorizace, která dává součin dvou nebo tří čísel. Následující rovnice uvádějí Aurifeuillianovy faktory pro základny projektu Cunningham jako produkt F, L a M:^[4]

Nechat b = s² · k s bez čtverce k, pokud platí jedna z podmínek, pak ${ displaystyle Phi _ {n} (b)}$ mít Aurifeuillianovu faktorizaci.

(i) ${ displaystyle k equiv 1 mod 4}$ a ${ displaystyle n equiv k { pmod {2k}};}$

ii) ${ displaystyle k equiv 2,3 { pmod {4}}}$ a ${ displaystyle n equiv 2k { pmod {4k}}.}$

Další faktory

Jakmile jsou odstraněny algebraické a Aurifeuillianovy faktory, ostatní faktory z bⁿ ± 1 jsou vždy ve formě 2kn + 1, protože jsou to všechny faktory ${ displaystyle Phi _ {n} (b)}$^{[Citace je zapotřebí ]}. Když n je prvočíslo, algebraické i aurifeuillské faktory nejsou možné, kromě triviálních faktorů (b - 1 pro bⁿ - 1 a b + 1 pro bⁿ + 1). Pro Mersennova čísla, triviální faktory nejsou pro prime možnén, takže všechny faktory mají formu 2kn + 1. Obecně platí, že všechny faktory (bⁿ − 1)/(b - 1) jsou ve formě 2kn + 1, kde b ≥ 2 a n je hlavní, kromě případů, kdy n rozděluje b - 1, v takovém případě (bⁿ − 1)/(b - 1) je dělitelné n sám.

Cunninghamova čísla formuláře bⁿ - 1 může být hlavní, pouze pokud b = 2 a n je hlavní, za předpokladu, že n ≥ 2; to jsou čísla Mersenne. Čísla formuláře bⁿ + 1 může být hlavní, pouze pokud b je sudé a n je síla 2, opět za předpokladu n ≥ 2; toto jsou zobecněná čísla Fermat, která jsou Fermat čísla když b = 2. Libovolný faktor Fermatova čísla 2²ⁿ +1 má formu k2^n + 2 + 1.

Zápis

bⁿ - 1 je označen jako b,n-. Podobně, bⁿ +1 je označeno jako b,n+. Když pracujeme s čísly formuláře požadovaného pro aurifeuillianskou faktorizaci, b,nL a b,nM se používají k označení L a M v výše uvedené produkty.^[5] Odkazy na b,n- a b,n+ jsou na číslo s odstraněnými všemi algebraickými a aurifeuillskými faktory. Například Mersennova čísla mají tvar 2,n- a čísla Fermat jsou ve tvaru 2,2ⁿ+; číslo Aurifeuille započteno v roce 1871 byl produkt 2,58L a 2,58M.

Viz také

• Cunninghamovo číslo
• ECMNET a NFS @ Home, dvě spolupráce pracující pro projekt Cunningham

Reference

externí odkazy

• Domovská stránka projektu Cunningham
• Stůl Brent-Montgomery-te Riele (Cunninghamovy tabulky pro vyšší základny)
• Cunninghamovy tabulky na Mersennewiki