Wagstaff prime - Wagstaff prime

v teorie čísel, a Wagstaff prime je prvočíslo p formuláře

${ displaystyle p = {{2 ^ {q} +1} nad 3}}$

kde q je lichý prime. Wagstaffova prvočísla jsou pojmenována po matematik Samuel S. Wagstaff ml.; the hlavní stránky připočítám Françoisovi Morainovi za to, že je jmenoval na přednášce na konferenci Eurocrypt 1990. Wagstaffovy prvočísla se objevují v Nová Mersennova domněnka a mít aplikace v kryptografie.

Příklady

První tři Wagstaffovy prvočísla jsou 3, 11 a 43, protože

${ displaystyle { begin {aligned} 3 & = {2 ^ {3} +1 nad 3}, [5pt] 11 & = {2 ^ {5} +1 nad 3}, [5pt] 43 & = {2 ^ {7} +1 nad 3}. End {zarovnáno}}}$

Známé Wagstaffovy prvočísla

Prvních několik Wagstaffových prvočísel je:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651,… (sekvence A000979 v OEIS )

Od října 2014^{[Aktualizace]}, známé exponenty, které produkují Wagstaffovy prvočísla nebo pravděpodobné prvočísla jsou:

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339,^[2] (všechny známé Wagstaffovy prvočísla)

95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399,…, 13347311, 13372531 (pravděpodobné prvočísla Wagstaff) (sekvence A000978 v OEIS )

V únoru 2010 Tony Reix objevil pravděpodobnou vrcholnou dobu Wagstaff:

${ displaystyle { frac {2 ^ {4031399} +1} {3}}}$

který má 1 213 572 číslic a byl 3. největším pravděpodobným prvočíslem, jaké kdy bylo k tomuto datu nalezeno.^[3]

V září 2013 oznámil Ryan Propper objev dvou dalších pravděpodobných prvočísel Wagstaff:^[4]

${ displaystyle { frac {2 ^ {13347311} +1} {3}}}$

a

${ displaystyle { frac {2 ^ {13372531} +1} {3}}}$

Každý z nich je pravděpodobné prvočíslo s o něco více než 4 miliony desetinných míst. V současné době není známo, zda existují exponenti mezi 4031399 a 13347311, kteří produkují Wagstaffovy pravděpodobné prvočísla.

Všimněte si, že když p je prime Wagstaff, ${ displaystyle { frac {2 ^ {p} +1} {3}}}$ nemusí být prvočíslo, první protipříklad je p = 683 a předpokládá se, že pokud p je Wagstaffovo prvočíslo a p> 43, pak ${ displaystyle { frac {2 ^ {p} +1} {3}}}$ je složený.

Testování originality

Primalita byla prokázána nebo vyvrácena pro hodnoty q až 83339. Ti s q > 83339 je pravděpodobné prvočíslo k dubnu 2015^[ref]. Důkaz primality pro q = 42737 provedl François Morain v roce 2007 s distribucí ECPP implementace běžící na několika sítích pracovních stanic pro 743 GHz-dny na Opteron procesor.^[5] Jednalo se o třetí největší důkaz primality ECPP od jeho objevu do března 2009.^[6]

V současné době je nejrychlejším známým algoritmem pro prokázání primality Wagstaffových čísel ECPP.

Nástroj LLR (Lucas-Lehmer-Riesel) od Jeana Penného se používá k vyhledání pravděpodobných prvočísel Wagstaff pomocí testu Vrba-Reix. Jedná se o test PRP založený na vlastnostech cyklu digraf pod x ^ 2-2 modulo číslo Wagstaff.

Zobecnění

Je přirozené to zvažovat^[7] obecněji čísla formuláře

${ displaystyle Q (b, n) = { frac {b ^ {n} +1} {b + 1}}}$

kde základna ${ displaystyle b geq 2}$. Od ${ displaystyle n}$ zvláštní máme

${ displaystyle { frac {b ^ {n} +1} {b + 1}} = { frac {(-b) ^ {n} -1} {(- b) -1}} = R_ {n } (- b)}$

tato čísla se nazývají „Wagstaffova číselná základna ${ displaystyle b}$“, a někdy zvažován^[8] případ odměna čísla se zápornou základnou ${ displaystyle -b}$.

Pro některé konkrétní hodnoty ${ displaystyle b}$, Všechno ${ displaystyle Q (b, n)}$ (s možnou výjimkou pro velmi malé ${ displaystyle n}$) jsou složené kvůli „algebraické“ faktorizaci. Konkrétně pokud ${ displaystyle b}$ má formu dokonalé síly s lichým exponentem (jako 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000 atd. (sekvence A070265 v OEIS )), pak skutečnost, že ${ displaystyle x ^ {m} +1}$, s ${ displaystyle m}$ liché, je dělitelné ${ displaystyle x + 1}$ ukázat to ${ displaystyle Q (a ^ {m}, n)}$ je dělitelné ${ displaystyle a ^ {n} +1}$ v těchto zvláštních případech. Jiný případ je ${ displaystyle b = 4k ^ {4}}$, s k kladné celé číslo (jako 4, 64, 324, 1024, 2500, 5184 atd. (sekvence A141046 v OEIS )), kde máme aurifeuillská faktorizace.

Kdy však ${ displaystyle b}$ nepřipouští algebraickou faktorizaci, předpokládá se, že nekonečný počet ${ displaystyle n}$ hodnoty ${ displaystyle Q (b, n)}$ Prime, všimněte si všeho ${ displaystyle n}$ jsou lichá prvočísla.

Pro ${ displaystyle b = 10}$, samotná prvočísla mají následující vzhled: 9091, 909091, 909090909090909091, 909090909090909090909090909091,… (sekvence A097209 v OEIS ), a tyto njsou: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... (sekvence A001562 v OEIS ).

Vidět odměna pro seznam zobecněné základny Wagstaffových prvočísel ${ displaystyle b}$. (Zobecněná základna Wagstaffů ${ displaystyle b}$ jsou zobecněné základny odměn ${ displaystyle -b}$ s lichým ${ displaystyle n}$)

Nejméně prime p takhle ${ displaystyle Q (n, p)}$ je prime are (začíná na n = 2, 0, pokud neexistuje p existuje)

3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ... (sekvence A084742 v OEIS )

Nejméně základna b takhle ${ displaystyle Q (b, prime (n))}$ je prime are (začíná na n = 2)

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (sekvence A103795 v OEIS )

Reference

externí odkazy

• John Renze a Eric W. Weisstein. „Wagstaff prime“. MathWorld.
• Chris Caldwell, Prvních dvacet: Wagstaff na Prime Stránky.
• Renaud Lifchitz, "Účinný pravděpodobný primární test pro čísla formuláře (2^p + 1)/3".
• Tony Reix, „Tři dohady o testování primality pro čísla Mersenne, Wagstaff a Fermat na základě cyklů Digraph pod X² - 2 modulo a prime ".
• Seznam odměn v základně -50 až 50
• Seznam základen Wagstaffových prvočísel 2 až 160