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

[Droog_Andrey]

Батороев в сообщении #240951 писал(а):

Сам я такими делами не занимаюсь, но где-то читал, что тест Миллера-Рабина работает очень оперативно.

А я занимаюсь. Оперативно этот тест рабоотает в сравнении с уиверсальными тестами вроде ECPP, как я уже говорил выше.

[Someone]

Батороев в сообщении #240951 писал(а):

где-то читал, что тест Миллера-Рабина работает очень оперативно

Да. Например, на моём компьютере один раунд для числа порядка $2^{1000000}$ (около $10^{301030}$) занимает 4500 секунд. Просеивание миллиона таких чисел с использованием делителей до $1830551537$ - 90 секунд. Количество оставшихся кандидатов сокращается почти в 19 раз.

[iig]

На этом форуме посмотрите мой алгоритм
topic23917.html
Может, что интересное скажете.

[Бодигрим]

Кстати, я вот не могу вспомнить следующий момент. Вот есть у нас некоторый вероятностный тест, который при произвольном значении некоторого параметра, скажем, с вероятностью 1/2 срабатывает для составного числа и вообще никогда не срабатывает для простого числа. Обычно этот факт несложно доказать при помощи элементарной (или не очень элементарной) теории чисел.

Следующий шаг - это провести 10, 100, 1000 проверок при различных значениях параметра и, как это обычно утверждается, проверить простоту с вероятностью ошибки $2^{-10}$, $2^{-100}$... Но для того, чтобы гарантировать такую вероятность, надо ведь доказать независимость (или какую-нибудь "почти-независимость") распределения исходов теста при всех значениях параметра. Собственно, вопрос: а этот факт для распространенных алгоритмов доказан или принимается на веру?

[Батороев]

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

Именно решето в первую очередь и используют. За исключением редких случаев, когда делители имеют специальный вид (например, для чисел Мерсенна) и брутфорс-префакторизация оказывается быстрее.

А уже потом - вероятностные тесты на простоту. И в самом конце - строгое доказательство простоты найденного числа.

Droog_Andrey
Прошу меня извинить!
Вчера изначально не уловил суть Вашего сообщения - именно то, что в нем идет речь о поиске простых в некотором диапазоне, а не проверки конкретного числа.
И наболтал "что попало".

[Droog_Andrey]

Но даже если проверяется конкретное число, самым первым идёт тест на наличие небольших делителей.

[Батороев]

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

Но даже если проверяется конкретное число, самым первым идёт тест на наличие небольших делителей.

В этом случае, какова цель таких проверок?

-- Пн сен 07, 2009 10:20:12 --

Хотя, чисто психологически, может, и есть смысл провести такую предварительную проверку. Не знаю, спорить не буду.

Мне в тесте Миллера-Рабина нравится то, что всего лишь с 1-го раунда он в состоянии распознать подавляющую часть составных чисел, оставляя нераспознанными только числа Кармайкла, да и то специального вида.

-- Пн сен 07, 2009 10:54:29 --

Батороев в сообщении #240951 писал(а):

Сам я такими делами не занимаюсь, но где-то читал, что тест Миллера-Рабина работает очень оперативно.

Похоже читал здесь, хотя говорится всколзь: http://ru.wikipedia.org/wiki/GIMPS

[Droog_Andrey]

Батороев в сообщении #241103 писал(а):

какова цель таких проверок?

Сэкономить время проверки в случае наличия таких делителей (а они в большинстве случаев есть).

[SerjeyMinsk]

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

Как я и думал, ASSA считает большие простые числа только на словах.
Меня не будет 3 дня, так что вернёмся к этому вопросу позже.

Не понял.
ASSA считает любые большие числа. И причем точно. И причем ресурсов аппаратных занимает намного меньше, когда речь идет о очень больших числах. Ваша оптимизация - это деоптимизация (если есть такое слово), потому как недостаточно учитывать только саму программу (которую вы итак не смогли нормально сделать потому что вовсе не анализировали алгоритм), но и аппарат на котором производятся вычисления.
Возьмите измените значение D в программе на с-с + 100, например. Проверьте за сколько времени вы найдете 1 простое число методом ASSA, а за сколько это-же число вы найдете методом Эратосфена. (И не надо метод ASSA называть решетом. Это Эратосфен назвал так свой труд) Причем здесь вообще решето? Мы что о гречке речь ведем?
И тогда давайте говорить о скоростях дальше.

[Droog_Andrey]

SerjeyMinsk, привет минчанам. А что за метод такой, и что конкретно он делает?

Например, может ли эта программа найти все простые в диапазоне от $N$ до $N+10000$, где $N$ равно

803837457453639491257079614341942108138837688287558145837488917522297427376533365218
650233616396004545791504202360320876656996676098728404396540823292873879185086916685
732826776177102938969773947016708230428687109997439976544144845341155872450633409279
0222752962294149842306881685404326457534018329786111298960644845216191652872597530000

?

[SerjeyMinsk]

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

SerjeyMinsk, привет минчанам. А что за метод такой, и что конкретно он делает?

Например, может ли эта программа найти все простые в диапазоне от $N$ до $N+10000$, где $N$ равно

803837457453639491257079614341942108138837688287558145837488917522297427376533365218
650233616396004545791504202360320876656996676098728404396540823292873879185086916685
732826776177102938969773947016708230428687109997439976544144845341155872450633409279
0222752962294149842306881685404326457534018329786111298960644845216191652872597530000

?

Рад землякам.
Пока методом ASSA можно находить простые числа в интервале длины $4 N$ (если по-научному, я так понял). По-русски (для меня конечно-же) от любого нечетного в квадрате до предыдущего нечетного в квадрате. Можно подумать и о том как увеличить диапазон, но в принципе не вижу смысла.
У меня такой программы нет по числам которые вы дали. У меня есть алгоритм и просто програма, сделанная программистом в паскале мне для проверки результатов его работы. С помощью усилий людей, присутствующих на данном форуме я смог довести её только до 10 значных чисел. Знакомые в Череповце довели её до тысячезначных чисел и скоро будет у меня на руках. Целью это не ставил. Была цель проверить работу алгоритма.
Алгоритм был выложен здесь на форуме для того чтобы убедить участвующих в беседе в том, что алгоритм у меня действительно есть. Потом я его удалил так как нашел в нем и другую коммерческую составляющую, а не только научный интерес. Вышлю для исследования в личном сообщении, если Вам интересно.

[Droog_Andrey]

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

Знакомые в Череповце довели её до тысячезначных чисел и скоро будет у меня на руках.

Интересно было бы потестить на моём примере (там 337 знаков всего).

[SerjeyMinsk]

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

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

Знакомые в Череповце довели её до тысячезначных чисел и скоро будет у меня на руках.

Интересно было бы потестить на моём примере (там 337 знаков всего).

Алгоритм выслал.

[Droog_Andrey]

Посмотрел. 100-значные не потянет, и даже 30-значные. Предел - где-то 20 знаков.

[SerjeyMinsk]

Его прямое применение в криптографии, а не в проектах типа GIMPS и поискам самых больших чисел.