Поиск простых чисел

[SerjeyMinsk]

Droog_Andrey в сообщении #241882 писал(а):

SerjeyMinsk в сообщении #241820 писал(а):

На том основании, что ASSA раскладывает на два сомножителя составное число пропорционально количеству времени потраченного на поиск всех простых чисел в заданном диапазоне + 3 операции.

Для 100-значного числа это количество времени в $10^{25}$ раз превышает возраст вселенной, в то время как GNFS справляется за несколько часов.

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

[Droog_Andrey]

Вы издеваетесь.

post241500.html#p241500

[SerjeyMinsk]

Droog_Andrey в сообщении #241968 писал(а):

Вы издеваетесь.

post241500.html#p241500

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

[Xaositect]

SerjeyMinsk в сообщении #241980 писал(а):

Почему увеличивается время для 100 значного аж в больше возраста вселенной я никак понять не могу. Один ноль добавляется.

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

[SerjeyMinsk]

Xaositect в сообщении #241983 писал(а):

SerjeyMinsk в сообщении #241980 писал(а):

Почему увеличивается время для 100 значного аж в больше возраста вселенной я никак понять не могу. Один ноль добавляется.

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

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

[venco]

SerjeyMinsk в сообщении #241986 писал(а):

Xaositect в сообщении #241983 писал(а):

SerjeyMinsk в сообщении #241980 писал(а):

Почему увеличивается время для 100 значного аж в больше возраста вселенной я никак понять не могу. Один ноль добавляется.

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

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

Нет.

[SerjeyMinsk]

venco в сообщении #241990 писал(а):

SerjeyMinsk в сообщении #241986 писал(а):

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

Нет.

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

[Xaositect]

SerjeyMinsk в сообщении #241995 писал(а):

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

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

[SerjeyMinsk]

Xaositect в сообщении #242008 писал(а):

SerjeyMinsk в сообщении #241995 писал(а):

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

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

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

[Xaositect]

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

[Gordmit]

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



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

[Xaositect]

Gordmit в сообщении #242141 писал(а):

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

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

[SerjeyMinsk]

Xaositect в сообщении #242048 писал(а):

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

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

[SerjeyMinsk]

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

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

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

[venco]

SerjeyMinsk в сообщении #242514 писал(а):

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

Порядка $6\cdot 10^{696}$.

SerjeyMinsk писал(а):

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

Порядка $1.73\cdot 10^9$.