2014 dxdy logo

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

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




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу Пред.  1 ... 11, 12, 13, 14, 15, 16, 17 ... 46  След.
 
 Re: Поиск простых чисел
Сообщение10.09.2009, 14:02 
Аватара пользователя


07/07/09
346
Минск
Droog_Andrey в сообщении #241882 писал(а):
SerjeyMinsk в сообщении #241820 писал(а):
На том основании, что ASSA раскладывает на два сомножителя составное число пропорционально количеству времени потраченного на поиск всех простых чисел в заданном диапазоне + 3 операции.
Для 100-значного числа это количество времени в $10^{25}$ раз превышает возраст вселенной, в то время как GNFS справляется за несколько часов.

Раскажите, как Вы это посчитали.

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


09/02/09
2092
Минск, Беларусь
Вы издеваетесь.

post241500.html#p241500

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение10.09.2009, 15:30 
Аватара пользователя


07/07/09
346
Минск
Droog_Andrey в сообщении #241968 писал(а):
Вы издеваетесь.

post241500.html#p241500

Нисколько. Я про это и спрашиваю уже второй раз.
Просто 10 значные он считает за секунду.
Почему увеличивается время для 100 значного аж в $10^{25}$ больше возраста вселенной я никак понять не могу. Один ноль добавляется.

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


06/10/08
6422
SerjeyMinsk в сообщении #241980 писал(а):
Почему увеличивается время для 100 значного аж в больше возраста вселенной я никак понять не могу. Один ноль добавляется.

При увеличении от 10-значного до 100-значного число увеличивается в $10^{90}$ раз

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение10.09.2009, 15:39 
Аватара пользователя


07/07/09
346
Минск
Xaositect в сообщении #241983 писал(а):
SerjeyMinsk в сообщении #241980 писал(а):
Почему увеличивается время для 100 значного аж в больше возраста вселенной я никак понять не могу. Один ноль добавляется.

При увеличении от 10-значного до 100-значного число увеличивается в $10^{90}$ раз

Количество операций (a-b-b) ведь остается одинаковой.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение10.09.2009, 15:53 
Заслуженный участник


04/05/09
4589
SerjeyMinsk в сообщении #241986 писал(а):
Xaositect в сообщении #241983 писал(а):
SerjeyMinsk в сообщении #241980 писал(а):
Почему увеличивается время для 100 значного аж в больше возраста вселенной я никак понять не могу. Один ноль добавляется.

При увеличении от 10-значного до 100-значного число увеличивается в $10^{90}$ раз

Количество операций (a-b-b) ведь остается одинаковой.
Нет.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение10.09.2009, 16:05 
Аватара пользователя


07/07/09
346
Минск
venco в сообщении #241990 писал(а):
SerjeyMinsk в сообщении #241986 писал(а):
Количество операций (a-b-b) ведь остается одинаковой.
Нет.

То есть Вы считаете, что размер числа влияет на его сравнение по модулю?

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


06/10/08
6422
SerjeyMinsk в сообщении #241995 писал(а):
То есть Вы считаете, что размер числа влияет на его сравнение по модулю?

У вас идет уменьшение числа, пока $a-b-b-\dots-b$ не станет равным $b$
поскольку $a\sim n^2$, $b=2n$, для этого надо вычесть $b$ из $a$ порядка $n$ раз

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


07/07/09
346
Минск
Xaositect в сообщении #242008 писал(а):
SerjeyMinsk в сообщении #241995 писал(а):
То есть Вы считаете, что размер числа влияет на его сравнение по модулю?

У вас идет уменьшение числа, пока $a-b-b-\dots-b$ не станет равным $b$
поскольку $a\sim n^2$, $b=2n$, для этого надо вычесть $b$ из $a$ порядка $n$ раз

Но ведь A нам необязательно начинать с ряда, 2,4,6,8, а сразу с минимального четного числа того диапазона в котором мы будем производить вычисления.

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


06/10/08
6422
У Вас ясно написано: вычеркиваем те, которые сравнимы с a mod 10, с (a-b-b) mod 14 и т.д.
Как Вы будете с ними сравнивать, если Вы их не вычислите?

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение10.09.2009, 21:20 
Заслуженный участник


19/06/05
486
МГУ
Прошу прощения за оффтоп, но раз уж здесь собрались специалисты по алгоритмам поиска больших простых чисел, хотел бы поинтересоваться: проверка заданного большого числа на простоту - это другая задача?
У меня тут сохранилась вырезка из журнала "Ломоносов" за 2002, кажется, год, с вот такой статьей:

Изображение

Короче говоря, трое индусов придумали быстрый алгоритм проверки числа на простоту. А, собственно, вопрос в следующем: действительно ли это было большим событием во всей этой тематике?

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


06/10/08
6422
Gordmit в сообщении #242141 писал(а):
Короче говоря, трое индусов придумали быстрый алгоритм проверки числа на простоту. А, собственно, вопрос в следующем: действительно ли это было большим событием во всей этой тематике?

Это было достаточно большим событием в теории сложности, потому что вопрос о том, является ли проверка простоты полиномиальной задачей, стоял давно. А вот на практике алгоритм AKS вроде не дотягивает до рандомизированных.

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


07/07/09
346
Минск
Xaositect в сообщении #242048 писал(а):
У Вас ясно написано: вычеркиваем те, которые сравнимы с a mod 10, с (a-b-b) mod 14 и т.д.
Как Вы будете с ними сравнивать, если Вы их не вычислите?

Так ведь и значение mod можно пропорционально числу увеличить сразу-же. И ряд четных чисел взять не с 2, а со стозначных.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение11.09.2009, 23:21 
Аватара пользователя


07/07/09
346
Минск
А какое количество простых чисел между 600 значными и 700 значными числами кто-нибудь знает?

-- Пт сен 11, 2009 23:38:01 --

И подскажите, сколько процессор Celeron (530) 1.73 Ghz, 533 Mhz совершает операций в секунду. 1гб оперативной.

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


04/05/09
4589
SerjeyMinsk в сообщении #242514 писал(а):
А какое количество простых чисел между 600 значными и 700 значными числами кто-нибудь знает?
Порядка $6\cdot 10^{696}$.

SerjeyMinsk писал(а):
И подскажите, сколько процессор Celeron (530) 1.73 Ghz, 533 Mhz совершает операций в секунду. 1гб оперативной.
Порядка $1.73\cdot 10^9$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 682 ]  На страницу Пред.  1 ... 11, 12, 13, 14, 15, 16, 17 ... 46  След.

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



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

Сейчас этот форум просматривают: Mikhail_K


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

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