Proth prime - Proth prime

Proth Prime

Nomeado após	François Proth
Ano de publicação	1878
Autor da publicação	Proth, François
Nº de termos conhecidos	Mais de 1,5 bilhão abaixo de 2 70
Não conjecturado . de termos	Infinito
Subseqüência de	Números proth, números primos
Fórmula	k  × 2 n + 1
Primeiros termos	3, 5, 13, 17, 41, 97, 113
Maior termo conhecido	10223 × 2 31172165 + 1 (em dezembro de 2019)
Índice OEIS

Um número de Proth é um número natural N da forma em que k e n são inteiros positivos , k é ímpar e . Um proth de Proth é um número de Proth que é primo . Eles foram nomeados em homenagem ao matemático francês François Proth . Os primeiros primos de Proth são ${\ displaystyle N = k \ cdot 2 ^ {n} +1}$${\ displaystyle 2 ^ {n}> k}$

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 ).

A primalidade dos números de Proth pode ser testada mais facilmente do que muitos outros números de magnitude semelhante.

Definição

Um número de Proth assume a forma em que k e n são inteiros positivos, é ímpar e . Um proth de Proth é um número de Proth que é primo. ${\ displaystyle N = k2 ^ {n} +1}$${\ displaystyle k}$${\ displaystyle 2 ^ {n}> k}$

Sem a condição de que , todos os inteiros ímpares maiores que 1 seriam números de Proth. ${\ displaystyle 2 ^ {n}> k}$

Teste de Primalidade

A primalidade de um número de Proth pode ser testada com o teorema de Proth , que afirma que um número de Proth é primo se e somente se existe um inteiro para o qual ${\ displaystyle p}$${\ displaystyle a}$

${\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv -1 {\ pmod {p}}.}$

Este teorema pode ser usado como um teste probabilístico de primalidade, verificando se há muitas escolhas aleatórias de se isso não vale para vários aleatórios , então é muito provável que o número seja composto . Este teste é um algoritmo de Las Vegas : ele nunca retorna um falso positivo, mas pode retornar um falso negativo ; em outras palavras, ele nunca relata um número composto como " provavelmente primo ", mas pode relatar um número primo como "possivelmente composto". ${\ displaystyle a}$${\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv -1 {\ pmod {p}}.}$${\ displaystyle a}$${\ displaystyle p}$

Em 2008, Sze criou um algoritmo determinístico que funciona na maioria das vezes, onde Õ é a notação soft-O . Para pesquisas típicas de primos Proth, geralmente é fixo (por exemplo, 321 Prime Search ou Sierpinski Problem) ou de ordem (por exemplo,  Cullen prime search). Nestes casos, o algoritmo é executado no máximo , ou tempo para todos . Também existe um algoritmo que funciona no tempo. ${\ displaystyle {\ tilde {O}} ((k \ log k + \ log N) (\ log N) ^ {2})}$${\ displaystyle k}$${\ displaystyle O (\ log N)}$${\ displaystyle {\ tilde {O}} ((\ log N) ^ {3})}$${\ displaystyle O ((\ log N) ^ {3+ \ epsilon})}$${\ displaystyle \ epsilon> 0}$${\ displaystyle {\ tilde {O}} ((\ log N) ^ {24/7})}$

Primos grandes

Em 2019, o maior Proth Prime conhecido é . Tem 9.383.761 dígitos. Foi descoberto por Szabolcs Peter no projeto de computação distribuída PrimeGrid que o anunciou em 6 de novembro de 2016. É também o maior primo conhecido não Mersenne . ${\ displaystyle 10223 \ cdot 2 ^ {31172165} +1}$

O projeto Seventeen or Bust , procurando por primos Proth com certeza para provar que 78557 é o menor número Sierpinski ( problema de Sierpinski ), encontrou 11 primos Proth grandes em 2007, dos quais 5 são megaprimes . Resoluções semelhantes para o problema principal de Sierpiński e o problema estendido de Sierpiński renderam vários outros números. ${\ displaystyle t}$

Desde dezembro de 2019, o PrimeGrid é o principal projeto de computação para a busca de primos Proth. Seus principais projetos incluem:

• pesquisa Proth principal geral
• 321 Prime Search (pesquisa por primos da forma , também chamados de primos Thabit do segundo tipo )${\ displaystyle 3 \ times 2 ^ {n} +1}$
• 27121 Pesquisa principal (pesquisa de números primos do formulário e )${\ displaystyle 27 \ times 2 ^ {n} +1}$${\ displaystyle 121 \ times 2 ^ {n} +1}$
• Pesquisa principal Cullen (pesquisa por números primos da forma )${\ displaystyle n \ times 2 ^ {n} +1}$
• Problema de Sierpinski (e suas generalizações primos e estendidas) - procurando por primos da forma em que k está nesta lista:${\ displaystyle k \ times 2 ^ {n} +1}$

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

Em dezembro de 2019, os maiores primos Proth descobertos são:

classificação	melhor	dígitos	quando	Cullen prime ?	Discoverer (Projeto)	Referências
1	10223 · 2 31172165 + 1	9383761	31 de outubro de 2016		Szabolcs Péter (problema de Sierpinski)
2	168451 · 2 19375200 + 1	5832522	17 de setembro de 2017		Ben Maloney (problema de Prime Sierpinski)
3	19249 · 2 13018586 + 1	3918990	26 de março de 2007		Konstantin Agafonov (dezessete ou busto)
4	193997 · 2 11452891 + 1	3447670	3 de abril de 2018		Tom Greer (problema estendido de Sierpinski)
5	3 · 2 10829346 + 1	3259959	14 de janeiro de 2014		Sai Yik Tang (321 Prime Search)
6	27653 · 2 9167433 + 1	2759677	8 de junho de 2005		Derek Gordon (dezessete ou busto)
7	90527 · 2 9162167 + 1	2758093	30 de junho de 2010		Desconhecido (problema de Sierpinski principal)
8	28433 · 2 7830457 + 1	2357207	30 de dezembro de 2004		Team Prime Rib (dezessete ou busto)
9	161041 · 2 7107964 + 1	2139716	6 de janeiro de 2015		Martin Vanc (problema estendido de Sierpinski)
10	27 · 2 7046834 + 1	2121310	11 de outubro de 2018		Andrew M. Farrow (27121 Pesquisa Principal)
11	3 · 2 7033641 + 1	2117338	21 de fevereiro de 2011		Michael Herder (321 Prime Search)
12	33661 · 2 7031232 + 1	2116617	17 de outubro de 2007		Sturle Sunde (dezessete ou busto)
13	6679881 · 2 6679881 + 1	2010852	25 de julho de 2009	sim	Magnus Bergman (Cullen Prime Search)
14	1582137 · 2 6328550 + 1	1905090	20 de abril de 2009		Dennis R. Gesker (Cullen Prime Search)
15	7 · 2 5775996 + 1	1738749	2 de novembro de 2012		Martyn Elvy (Proth Prime Search)
16	9 · 2 5642513 + 1	1698567	29 de novembro de 2013		Serge Batalov
17	258317 · 2 5450519 + 1	1640776	28 de julho de 2008		Scott Gilvey (primeiro problema de Sierpinski)
18	27 · 2 5213635 + 1	1569462	9 de março de 2015		Hiroyuki Okazaki (27121 Prime Search)
19	39 · 2 5119458 + 1	1541113	23 de novembro de 2019		Scott Brown (Fermat Divisor Prime Search)
20	3 · 2 5082306 + 1	1529928	3 de abril de 2009		Andy Brady (321 Prime Search)

Usos

Primos Proth pequenos (menos de 10 ²⁰⁰ ) têm sido usados ​​na construção de escadas de números primos, sequências de números primos de modo que cada termo esteja "próximo" (em cerca de 10 ¹¹ ) do anterior. Essas escadas têm sido usadas para verificar empiricamente conjecturas relacionadas aos primeiros . Por exemplo, a conjectura fraca de Goldbach foi verificada em 2008 até 8.875 × 10 ³⁰ usando escadas primárias construídas a partir de primos de Proth. (A conjectura foi posteriormente provada por Harald Helfgott .)

Além disso, Proth primes pode otimizar a redução de den Boer entre o problema Diffie-Hellman e o problema do logaritmo discreto . O número primo 55 × 2 ²⁸⁶  + 1 foi usado desta forma.

Como os primos Proth têm representações binárias simples , eles também têm sido usados ​​na redução modular rápida sem a necessidade de pré-computação, por exemplo, pela Microsoft .

Referências