Исчисление простых чисел

[Someone]

(Dmitriy40)

Dmitriy40 в сообщении #1240750 писал(а):

А мне вот дополнительно интересна и сложность алгоритма.

Да ужасающая там сложность.Например, если мы хотим проверить на простоту число порядка $10^{100}$ (это совсем небольшое число по современным понятиям; например, программа Primo, использующая метод эллиптических кривых, на моём компьютере за $0{,}16$ секунды проверила, что число
\parindent=0 $15\,197\,067\,331\,985\,087\,436\,765\,859\,032\,346\,168\,140\,235\,515\,143\,921\,296\,021\,506\,015\,387\,717\,999\,171\,041\,541\\ 312\,961\,569\,035\,509\,805\,473$
является простым, и выдала сертификат простоты, который можно проверить; это число сгенерировала Wolfram Mathematica командой $\mathbf{Timing[RandomPrime[{10^{100}, 2*10^{100}}]]}$ за $0{,}1248$ секунды), то мы должны найти все простые числа, не превосходящие квадратный корень из проверяемого числа. Их нужно разбить на две группы (разбиение может быть произвольным) и перемножить числа в каждой группе (можно каждое взять в любой степени), что даст те самые $Q$ и $R$; произведение этих чисел никак не меньше, чем примориал $10^{50}$. Используя оценку примориала $N\#=e^{(1+o(1))N}$, получаем, что произведение $QR$ есть, как минимум, число порядка $e^{10^{50}}$. Таким образом, нам придётся иметь дело с числами, в десятичной записи которых примерно $0{,}43\cdot 10^{50}$ цифр. Я думаю, что дальнейшее обсуждение сложности рассматриваемого алгоритма проверки простоты (одного!) числа не имеет смысла.

[Dmitriy40]

(Someone)

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

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

Угу, это убивает всю практическую ценность, спасибо.

[Rak so dna]

atlakatl в сообщении #1238332 писал(а):

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

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

[atlakatl]

Rak so dna в сообщении #1241791 писал(а):

Эта формула даёт любое простое

Я это не опровергал. Покажите, где я возражал.

Rak so dna в сообщении #1241791 писал(а):

И примеры есть

Ссылку приведите, пожалуйста.

[Someone]

atlakatl в сообщении #1241795 писал(а):

Ссылку приведите, пожалуйста.

https://pdfs.semanticscholar.org/6cc0/7d0dd05572539d48c97ef8fa0e1c09dbba6a.pdf

[grizzly]

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

atlakatl в сообщении #1241795 писал(а):

Ссылку приведите, пожалуйста.

https://pdfs.semanticscholar.org/6cc0/7d0dd05572539d48c97ef8fa0e1c09dbba6a.pdf

Это только метод поиска. А чтобы привести хоть один конкретный пример не хватит полей нашего Интернета

[Someone]

grizzly в сообщении #1241814 писал(а):

Это только метод поиска. А чтобы привести хоть один конкретный пример не хватит полей нашего Интернета

Да, так и есть. Но при наличии неограниченных ресурсов решение может быть доведено до конца.

[Rak so dna]

Если коротко, то простое число $2$ дают следующие значения:
$k=0, g=0, f=17, n=2, p=3, q=16, z=9, w=1, h=2, j=5, e=32$ $a=7901690358098896161685556879749949186326380713409290912$,
$o=8340353015645794683299462704812268882126086134656108363777$
$y=2a, x=2a^2-1, m=a, l=1, i=0, v=2a-3, b=0, s=1, t=0$,
$r\simeq{10^{10^{52}}}$, числа $u, c, d$ еще больше, но принципиальных проблем в их определении нет.

[kotenok gav]

А что это за переменные?

[atlakatl]

Rak so dna
Хочется верить,
Но нет оснований.
Коль нет оснований,
То нечего верить.

[Sender]

Rak so dna в сообщении #1241865 писал(а):

принципиальных проблем в их определении нет.

Принципиальным-то неоткуда взяться, конечно. Ведь множество всех их значений перечислимо.

[grizzly]

Rak so dna в сообщении #1241865 писал(а):

$r\simeq{10^{10^{52}}}$

Это, если я помню, ограничение снизу, а само $r$ может быть много, много больше.

Rak so dna в сообщении #1241865 писал(а):

числа $u, c, d$ еще больше, но принципиальных проблем в их определении нет

Завидую Вашим принципам

[kotenok gav]

kotenok gav в сообщении #1241870 писал(а):

А что это за переменные?

[mihailm]

kotenok gav в сообщении #1241899 писал(а):

kotenok gav в сообщении #1241870 писал(а):

А что это за переменные?

А что обсуждается то, хотя бы знаете?

[Someone]

kotenok gav в сообщении #1241870 писал(а):

А что это за переменные?

Я же дал ссылку.