Поиск простого числа по новому

[ozheredov]

Someone в сообщении #1321038 писал(а):

танк навстречу

Спасибо, вам того же )) Раз уже зашла речь о рекордах, задам «наболевший» вопрос: наибольшее простое (известное, ясен перец) содержит неск. десятков миллионов знаков, и превзойти его — якобы большая проблема, а очень хочется, поскольку это всё имеет прямое отношение к криптографии и пр. Так вот в чём проблема, я не понимаю? Берём все известные на данный момент простые, перемножаем и сверху приклеиваем единичку — вуа ля, новое простое (с большим отрывом от предыдущего) готово! Может, эта — раздобудем базу данных (несколько сот терабайт, если как я думаю кодировать два знака с помощью unsigned short int), поможем пользователю SpiderHulk, а заодно пару лямов бакинских поднимем? )

[grizzly]

ozheredov в сообщении #1321117 писал(а):

перемножаем и сверху приклеиваем единичку — вуа ля, новое простое (с большим отрывом от предыдущего) готово!

В том "звоне", который Вы слышали, было предположение, что простых чисел конечное число. Не спешите, просто подумайте или вспомните.

[ozheredov]

grizzly

А, да, точно! Конечно же это я ступил. А какой тогда способ мгновенно найти следующее простое число, зная все предыдущие (то о чем говорит Someone?) Есть 3, 5, 7, 11. Как найти большее? Большее не значит 13, возможно намного большее.

-- 19.06.2018, 16:40 --

ozheredov в сообщении #1321135 писал(а):

Есть 3, 5, 7, 11.

2 ещё есть )

[grizzly]

ozheredov в сообщении #1321135 писал(а):

А какой тогда способ мгновенно найти следующее простое число, зная все предыдущие (то о чем говорит Someone?)

Речь идёт не о том, чтобы сгенерировать следующее, а только об очень быстрой проверке современными алгоритмами на современных процессорах.

[Someone]

ozheredov в сообщении #1321135 писал(а):

А какой тогда способ мгновенно найти следующее простое число, зная все предыдущие (то о чем говорит Someone?)

Видите ли, если уж у нас где-то хранится список всех простых чисел, меньших $n$, то, стало быть, земных ресурсов для этого достаточно. Оценка количества нуклонов в наблюдаемой части Вселенной даёт заведомо меньше $10^{100}$. Как Вы думаете, сколько времени современным компьютерам требуется, чтобы найти следующее за $10^{100}$ простое число? Я спрашиваю не о суперкомпьютерах, а о тех компьютерах, которые у многих стоят дома на столе.

[ozheredov]

Someone в сообщении #1320783 писал(а):

Понятия не имею. И в каком смысле "известны"? Имеется полный список в печатном виде или в виде набора файлов на каком-нибудь компьютерном носителе?
И для чего Вы хотите это знать? Чтобы взять самое большое число в этом списке и, запустив какой-нибудь пакет компьютерной математики, за ничтожную долю секунды побить этот рекорд?

Я проинтерпретировал так что это типа возможно. Сейчас понимаю в чем я ступил — каждое число очень большое, и чисел дофига. М-да, хранить пожалуй что негде

[Andrey A]

ozheredov в сообщении #1321117 писал(а):

Берём все известные на данный момент простые, перемножаем и сверху приклеиваем единичку — вуа ля, новое простое...

Евклид этого не утверждал. Идея в том, что любой простой делитель такого числа будет отличаться от имеющихся, и, поскольку задействованы все, будет $>$ старшего из имеющихся (grizzly намекал, но Вы не отреагировали). Пример: $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=59\cdot 509$. Причем $59$ явно простое так как $\sqrt{59}<13$, а $509$ еще нуждается в проверке. Получить заведомо простое из этого набора можно так: $3\cdot 5\cdot 13-2\cdot 7\cdot 11=41<(13+2)^2$ или типа того. Было уже, но это отдельный разговор.

ozheredov в сообщении #1321251 писал(а):

М-да, хранить пожалуй что негде

Не счесть алмазов
В каменных лабазах...

[ozheredov]

Andrey A в сообщении #1321259 писал(а):

grizzly намекал

Да отреагировал я ) :

ozheredov в сообщении #1321135 писал(а):

А, да, точно! Конечно же это я ступил.