2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Исчисление простых чисел
Сообщение15.08.2017, 23:42 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва

(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}$ цифр. Я думаю, что дальнейшее обсуждение сложности рассматриваемого алгоритма проверки простоты (одного!) числа не имеет смысла.

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение16.08.2017, 04:49 
Заслуженный участник


20/08/14
11062
Россия, Москва

(Someone)

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

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение19.08.2017, 19:12 
Аватара пользователя


26/02/14
496
so dna
atlakatl в сообщении #1238332 писал(а):
Только ни одного простого числа из этой формулы не известно. Так что формула чисто декоративная.

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

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение19.08.2017, 19:22 
Аватара пользователя


21/09/12

1871
Rak so dna в сообщении #1241791 писал(а):
Эта формула даёт любое простое
Я это не опровергал. Покажите, где я возражал.
Rak so dna в сообщении #1241791 писал(а):
И примеры есть
Ссылку приведите, пожалуйста.

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение19.08.2017, 20:45 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
atlakatl в сообщении #1241795 писал(а):
Ссылку приведите, пожалуйста.
https://pdfs.semanticscholar.org/6cc0/7d0dd05572539d48c97ef8fa0e1c09dbba6a.pdf

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение19.08.2017, 21:11 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Someone в сообщении #1241810 писал(а):
atlakatl в сообщении #1241795 писал(а):
Ссылку приведите, пожалуйста.
https://pdfs.semanticscholar.org/6cc0/7d0dd05572539d48c97ef8fa0e1c09dbba6a.pdf
Это только метод поиска. А чтобы привести хоть один конкретный пример не хватит полей нашего Интернета :D

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение19.08.2017, 21:13 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
grizzly в сообщении #1241814 писал(а):
Это только метод поиска. А чтобы привести хоть один конкретный пример не хватит полей нашего Интернета
Да, так и есть. Но при наличии неограниченных ресурсов решение может быть доведено до конца.

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение20.08.2017, 09:14 
Аватара пользователя


26/02/14
496
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$ еще больше, но принципиальных проблем в их определении нет.

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение20.08.2017, 09:44 


21/05/16
4292
Аделаида
А что это за переменные?

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение20.08.2017, 09:45 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение20.08.2017, 09:59 


14/01/11
2916
Rak so dna в сообщении #1241865 писал(а):
принципиальных проблем в их определении нет.

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

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение20.08.2017, 10:16 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Rak so dna в сообщении #1241865 писал(а):
$r\simeq{10^{10^{52}}}$
Это, если я помню, ограничение снизу, а само $r$ может быть много, много больше.
Rak so dna в сообщении #1241865 писал(а):
числа $u, c, d$ еще больше, но принципиальных проблем в их определении нет
Завидую Вашим принципам :D

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение20.08.2017, 12:10 


21/05/16
4292
Аделаида
kotenok gav в сообщении #1241870 писал(а):
А что это за переменные?

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение20.08.2017, 16:20 


19/05/10

3940
Россия
kotenok gav в сообщении #1241899 писал(а):
kotenok gav в сообщении #1241870 писал(а):
А что это за переменные?
А что обсуждается то, хотя бы знаете?

 Профиль  
                  
 
 Re: Исчисление простых чисел
Сообщение20.08.2017, 16:21 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
kotenok gav в сообщении #1241870 писал(а):
А что это за переменные?
Я же дал ссылку.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group