наибольшее произвольное простое число

[shust]

Кто что может сказать по поводу наибольшего произвольного (не специального вида)
известного к настоящему времени простого числа? Какого порядка его величина? Как его можно получить? Произвольное натуральное число получается последовательным выписыванием цифр его, например, десятичного представления. Пример: 85439648304765974321.

[Руст]

Самое большое из известных на сегодня простых чисел имеет вид: $2^{32582657}-1$. А вообще много интересного о них можете найти в портале The Prime pages.

[ИСН]

Произвольное можно построить какой угодно величины, это банально и неинтересно, поэтому за ними не гоняются так, как за числами специального вида.

[Someone]

ИСН писал(а):

Произвольное можно построить какой угодно величины, это банально и неинтересно, поэтому за ними не гоняются так, как за числами специального вида.

Нет, ситуация не такая. За простыми числами специальных видов гоняются именно потому, что их простоту гораздо легче доказать, поэтому наибольшие известные простые числа - именно специальных видов. Вот начало постоянно обновляющегося списка с http://primes.utm.edu/primes/download.php:

    1f 2^32582657-1                    9808358 G9   2006 Mersenne 44??
    2  2^30402457-1                    9152052 G9   2005 Mersenne 43??
    3  2^25964951-1                    7816230 G8   2005 Mersenne 42??
    4  2^24036583-1                    7235733 G7   2004 Mersenne 41??
    5  2^20996011-1                    6320430 G6   2003 Mersenne 40??
    6  2^13466917-1                    4053946 G5   2001 Mersenne 39
    7  27653*2^9167433+1               2759677 SB8  2005 
    8  28433*2^7830457+1               2357207 SB7  2004 
    9  2^6972593-1                     2098960 G4   1999 Mersenne 38
   10  5359*2^5054502+1                1521561 SB6  2003 
   11  4847*2^3321063+1                 999744 SB9  2005 
   12  2^3021377-1                      909526 G3   1998 Mersenne 37
   13  2^2976221-1                      895932 G2   1997 Mersenne 36
   14f 222361*2^2854840+1               859398 g403 2006 
   15  1372930^131072+1                 804474 g236 2003 Generalized Fermat
   16  1361244^131072+1                 803988 g236 2004 Generalized Fermat
   17  1176694^131072+1                 795695 g236 2003 Generalized Fermat
   18  572186^131072+1                  754652 g0   2004 Generalized Fermat
   19  3*2^2478785+1                    746190 g245 2003 
          Divides Fermat F(2478782), GF(2478782,3), GF(2478776,6),
          GF(2478782,12)
   20c 26773*2^2465343-1                742147 L197 2006 

А что касается "произвольных" простых чисел, то их простоту приходится доказывать тяжёлыми и медленно работающими методами типа метода эллиптическиъ кривых. Наибольшее такое число, которое я нашёл в этом списке:

 5152  ((((((2521008887^3+80)^3+12)^3+450)^3+894)^3+3636)^3+70756)^3+97220
                                         20562 FE1  2006 ECPP, Mills' prime

[shust]

ИСН писал(а):

Произвольное можно построить какой угодно величины..

Укажите как построить первое произвольное простое число, большее десяти в 20 степени.

Someone писал(а):

Нет, ситуация не такая. За простыми числами специальных видов гоняются именно потому, что их простоту гораздо легче доказать, поэтому наибольшие известные простые числа - именно специальных видов.

Согласен.

Someone писал(а):

А что касается "произвольных" простых чисел, то их простоту приходится доказывать тяжёлыми и медленно работающими методами типа метода эллиптическиъ кривых. Наибольшее такое число, которое я нашёл в этом списке:
5152 ((((((2521008887^3+80)^3+12)^3+450)^3+894)^3+3636)^3+70756)^3+97220
20562 FE1 2006 ECPP, Mills' prime

Но это не совсем произвольное простое число, скорее совсем не произвольное, т.к. представляется определенной формулой.

[Руст]

Десять в двадцатой степени это не большое число. В криптографии используют простые числа порядка 10 в 100-й степени. Алгоритмы тестирующие на простоту не такие сложные, чтобы последовательной проверкой отсеять не простые из некоторого интервала. Например для построения первого простого после 10 в сотой степени возьмём вначале первые 250 (100ln(10)) чисел и отсеим делящееся на первые 1000 простых. Далее оставшиеся проверяем тестами Рабина Миллера. Оставшиеся полиномиальными алгоритмами с доказательством простоты. Гораздо сложнее найти делители у больших чисел, чем проверить число на простоту.

[Someone]

shust писал(а):

Но это не совсем произвольное простое число, скорее совсем не произвольное, т.к. представляется определенной формулой.

А доказывать простоту совершенно случайного числа такой величины никто не будет. На это требуются годы, и нужен определённый (и весьма существенный) стимул, хотя бы в виде любопытства и интереса к числам данного вида. В частности, для проверки простоты этого числа потребовалось 2219 суток (если я правильно понял, имеется в виду время, которое потратил бы один процессор AMD Opteron(tm) Processor 250 at 2.39 GHz).

Оно является "произвольным" не в том смысле, что взято случайно, а в том смысле, что для проверки его простоты требуются те же методы, что и для случайных чисел.

http://www.ellipsa.net/primo/record.html
http://www.lix.polytechnique.fr/Labo/Francois.Morain/Primes/mills2.txt

[shust]

Someone писал(а):

А доказывать простоту совершенно случайного числа такой величины никто не будет.

Может быть не такой большой величины, можно и поменьше. Почему бы не попробывать, был бы подходящий метод.

Цитата:

На это требуются годы, и нужен определённый (и весьма существенный) стимул, хотя бы в виде любопытства и интереса к числам данного вида.

Годы - это очень много. Не более суток, а лучше час работы обычных компьютеров.

Цитата:

Оно является "произвольным" не в том смысле, что взято случайно, а в том смысле, что для проверки его простоты требуются те же методы, что и для случайных чисел.

http://www.ellipsa.net/primo/record.html
http://www.lix.polytechnique.fr/Labo/Francois.Morain/Primes/mills2.txt

Рекордные простые числа этих сайтов не произвольного вида, а определеные некоторыми формулами. Возможно такое их представление и помогло установить эти рекорды.

[Руст]

Доказательство простоты числа порядка 10 в 100-й степени занимает минуты.

[shust]

Руст писал(а):

Доказательство простоты числа порядка 10 в 100-й степени занимает минуты.

Можете указать первое простое число, большее 10 в 100-й степени, или на худой конец дать ссылку на источник, где достоверно показано, что процесс отыскания такого числа

Цитата:

занимает минуты

?

[Руст]

Это я читал в одной книге по криптографии. Только для факторизации произведения двух таких чисел может потребоваться тысячи лет расчёта.

[Someone]

shust писал(а):

Руст писал(а):

Доказательство простоты числа порядка 10 в 100-й степени занимает минуты.

Можете указать первое простое число, большее 10 в 100-й степени, или на худой конец дать ссылку на источник, где достоверно показано, что процесс отыскания такого числа

Цитата:

занимает минуты

?

Mathematica 5.1

Timing[For[k = 0, k < 251, k++, If[PrimeQ[10^100 + 2 k + 1], Print[10^100 + 2 k + 1]]]]
100000000000000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000267
{0.141 Second, Null}
Timing[For[k = 0, k < 251, k++, If[PrimeQ[10^200 + 2 k + 1], Print[10^200 + 2 k + 1]]]]
100000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000357
{0.411 Second, Null}
Timing[For[k = 0, k < 251, k++, If[PrimeQ[10^300 + 2 k + 1], Print[10^300 + 2 k + 1]]]]
100000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000331
100000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000387
{0.851 Second, Null}
Timing[For[k = 0, k < 251, k++, If[PrimeQ[10^400 + 2 k + 1], Print[10^400 + 2 k + 1]]]]
100000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
00000000069
{0.941 Second, Null}

Правда, функция PrimeQ не делает полного доказательства простоты. Полное доказательство требует больше времени:

<< NumberTheory`PrimeQ`
Timing[ProvablePrimeQ[10^100+267]]
{4.617 Second, True}
Timing[ProvablePrimeQ[10^200+357]]
{100.034 Second, True}

Специализированные программы типа Primo делают это гораздо быстрее.

shust писал(а):

Рекордные простые числа этих сайтов не произвольного вида, а определеные некоторыми формулами. Возможно такое их представление и помогло установить эти рекорды.

Нет, там же написано: используется метод эллиптических кривых. Этот метод - универсальный. А специальные и несравненно более быстрые методы используются для проверки таких чисел, для которых у чисел $p\pm 1$ удаётся найти достаточно большое количество простых множителей.

[Руст]

Когда известно разложение на множители n-1, проверка на простоту n требует всего порядка $\tau(n-1)log_2(n)$ операций, здесь $\tau(n)$ - количество простых делителей, т.е. не более квадратичного от количества разрядов n. Примерно так же обстоит дело при известности факторизации n+1. Для специальных чисел типа Мерсена получается сложность проверки пропорционально количеству разрядов (правда с учётом того, что операции надо проделывать с большими числами это сводится к $log_2(n)^2\log(\log (n))$ обычных операций).

[maxal]

Есть методы построения случайных больших простых чисел, которые используются в криптографии.
См., например: раздел 4.5 Как строить большие простые числа из книги "Введение в криптографию"

[Droog_Andrey]

Руст писал(а):

Это я читал в одной книге по криптографии. Только для факторизации произведения двух таких чисел может потребоваться тысячи лет расчёта.

http://mersenneforum.org/showthread.php?t=4085