Proth prime - Proth prime

A Proth číslo je číslo N formuláře ${ displaystyle N = k2 ^ {n} +1}$ kde k a n jsou pozitivní celá čísla, k je liché a ${ displaystyle 2 ^ {n}> k}$. A Proth prime je číslo Prototh primární. Jsou pojmenovány podle francouzského matematika François Proth.^[1] Prvních pár Prothových prvočísel je

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 (OEIS: A080076).

Primalitu Prothových čísel lze testovat snadněji než mnoho jiných čísel podobné velikosti.

Definice

Formulář má číslo Proth ${ displaystyle N = k2 ^ {n} +1}$ kde k a n jsou kladná celá čísla, ${ displaystyle k}$ je liché a ${ displaystyle 2 ^ {n}> k}$. Proth prime je číslo Prototh, které je prime.^[1][2]

Bez podmínky, že ${ displaystyle 2 ^ {n}> k}$, všechna lichá celá čísla větší než 1 by byla Prothova čísla.^[3]

Testování originality

Primalitu čísla Prototh lze testovat pomocí Prothova věta, který uvádí, že číslo Prototh ${ displaystyle p}$ je prvočíslo právě tehdy, pokud existuje celé číslo ${ displaystyle a}$ pro který

${ displaystyle a ^ { frac {p-1} {2}} equiv -1 { pmod {p}}.}$^[2][4]

Tuto větu lze použít jako pravděpodobnostní test prvočíselnosti kontrolou mnoha náhodných voleb ${ displaystyle a}$ zda ${ displaystyle a ^ { frac {p-1} {2}} equiv -1 { pmod {p}}.}$ Pokud se to nepodaří udržet několik náhodně ${ displaystyle a}$, pak je velmi pravděpodobné, že číslo ${ displaystyle p}$ je složený.^{[Citace je zapotřebí ]}Tento test je a Algoritmus Las Vegas: nikdy nevrací a falešně pozitivní ale může vrátit a falešně negativní; jinými slovy, nikdy nehlásí a složené číslo tak jako "pravděpodobně prime „ale může nahlásit prvočíslo jako„ možná složené “.

V roce 2008 Sze vytvořil deterministický algoritmus který běží maximálně ${ displaystyle { tilde {O}} ((k log k + log N) ( log N) ^ {2})}$ čas, kde Õ je soft-O notace. Pro typické hledání Prothových prvočísel obvykle ${ displaystyle k}$ je buď opravený (např. 321 Prime Search nebo Sierpinski Problem) nebo objednávkový ${ displaystyle O ( log N)}$ (např. Cullen prime Vyhledávání). V těchto případech je spuštěn maximálně algoritmus ${ displaystyle { tilde {O}} (( log N) ^ {3})}$nebo ${ displaystyle O (( log N) ^ {3+ epsilon})}$ čas pro všechny ${ displaystyle epsilon> 0}$. Existuje také algoritmus, který běží ${ displaystyle { tilde {O}} (( log N) ^ {24/7})}$ čas.^[1][5]

Velké prvočísla

Od roku 2019^{[Aktualizace]}, největší známý Proth prime je ${ displaystyle 10223 cdot 2 ^ {31172165} +1}$. Má 9 383 761 číslic.^[6] Nalezl jej Szabolcs Peter v PrimeGrid projekt distribuovaných výpočtů která to oznámila dne 6. listopadu 2016.^[7] Je to také největší známáMersenne prime.^[8]

Projekt Sedmnáct nebo Busta, s určitým hledáním Prothova prvočísla ${ displaystyle t}$ dokázat, že 78557 je nejmenší Sierpinského číslo (Sierpinského problém ), našel do roku 2007 11 velkých Prothových prvočísel, z toho 5 megaprimes. Podobná usnesení jako hlavní Sierpińského problém a rozšířený Sierpińského problém přinesly několik dalších čísel.

Od prosince 2019 PrimeGrid je přední počítačový projekt pro vyhledávání Prothových prvočísel. Mezi jeho hlavní projekty patří:

• obecné Proth prime vyhledávání
• 321 Prime Search (hledání prvočísel formuláře ${ displaystyle 3 krát 2 ^ {n} +1}$, také zvaný Zvyklá prvočísla druhého druhu )
• 27121 Prime Search (hledání prvočísel formuláře ${ displaystyle 27 krát 2 ^ {n} +1}$ a ${ displaystyle 121 krát 2 ^ {n} +1}$)
• Cullen prime search (hledání prvočísel formuláře ${ displaystyle n krát 2 ^ {n} +1}$)
• Sierpinského problém (a jejich hlavní a rozšířené zobecnění) - hledání prvočísel formy ${ displaystyle k krát 2 ^ {n} +1}$ kde k je v tomto seznamu:

k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 202705, 209611, 222113, 225931, 227723, 229673, 237019, 238411}}

Od prosince 2019 jsou největší objevená prvočísla prvočísla:^[9]

Použití

Malý Proth připraví (méně než 10²⁰⁰) byly použity při konstrukci prvočísel, sekvencí prvočísel tak, že každý člen je „blízký“ (do přibližně 10¹¹) na předchozí. Takové žebříky byly použity k empirickému ověření domněnek týkajících se prvočísel. Například, Goldbachova slabá domněnka bylo v roce 2008 ověřeno až 8 875 · 10³⁰ pomocí žebříků připravených z Prothových prvočísel.^[28] (Domněnku později prokázal Harald Helfgott.^{[29][30][je zapotřebí lepší zdroj ]})

Prothovy prvočísla se také mohou optimalizovat den Boerova redukce mezi Problém Diffie-Hellman a Diskrétní logaritmický problém. Prvočíslo 55×2²⁸⁶ + 1 byl použit tímto způsobem.^[31]

Protože Prothova prvočísla mají jednoduché binární reprezentace, byly také použity při rychlé modulární redukci bez nutnosti předběžného výpočtu, například Microsoft.^[32]

Reference