Возможно ли определить за умеренное время (часы\дни) является ли заданное число, с числом знаков более 1000, простым?

Question

[Виталий Пухов]

Суть вопроса в заголовке, я знаю, что алгоритмов много, но интересно насколько долго будет проводиться процедура, скажем если будет 1млн. знаков. Число заранее определено.

Answer 1

[Владимир Мартьянов]

Есть вероятностные тесты, например Рабин-Миллер.

Comments

[Виталий Пухов]

насколько я понял это не гарантированная, но быстрая проверка?

[Владимир Мартьянов]

Виталий Пухов: Да, быстрая и не гарантированная. Касательно вероятности неверного результата в ней надо смотреть что пишут. На практике ее вполне используют в криптографии.

[B@rmaley.e><e]

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

[Виталий Пухов]

B@rmaley.e><e: хорошо, допустим "относительно быстро" я определил число, которое вероятно является простым, реально ли определить гарантированно что именно это число является простым?

Answer 2

[Mrrl]

Скорость работы вероятностного алгоритма - примерно C*L^2*log(L), где L - длина проверяемого числа, C - количество тестов (вероятность false positive будет не больше 4^(-C)). Это если использовать сверхбыстрые алгоритмы умножения. Для миллиона знаков время получится несколько триллионов - и там всё зависит от константы. Будут это часы, или дни - сказать трудно.
Если тестируемое число равно произведению нескольких известных простых чисел + 1, то проверка может дать гарантированный результат, но в этом случае C равно количеству чисел, входящих в произведение.

Comments

[Виталий Пухов]

То есть это только для вероятностного трилионы операций, а для гарантированной проверки?

[Mrrl]

Виталий Пухов: Ещё больше. Посмотрите здесь: en.wikipedia.org/wiki/Primality_test#Fast_determin...
Может быть, что-нибудь понравится.
А что известно про число, которое надо проверять? Как оно получилось?

[Виталий Пухов]

Mrrl: число построено как A*B+C где A,B,C произвольные числа

[Mrrl]

Виталий Пухов: Это всё равно, что сказать "число произвольное". Так что придётся применять общие алгоритмы.
Учтите ещё, что вероятность того, что число с миллионом знаков простое - примерно 1/2300000. Так что чисел для поиска такого числа придётся перебрать много.
Если хотите искать большие простые числа - ищите их в виде 2*p*q+1, где p и q - тоже простые. Можно добавить ещё несколько простых множителей, но не очень много. Простоту таких чисел проверить (гарантированно) гораздо проще:
https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D...

[Виталий Пухов]

Mrrl: обычно так и есть, но в данном случае, при определенных B и C я смог добиться вероятности того что полученное число будет простым более чем 90 % на первых 200 тысячах, дальше конечно она будет уменьшаться, но слишком сильно, чтобы проверить насколько сильно будет уменьшаться нужно будет много проверять, все алгоритмы что попадались жутко медленные.

[Mrrl]

Остаётся только пожелать удачи.

Answer 3

[Boris Nagaev]

Существует детерминированный полиномиальный алгоритм Агравала... для проверки числа на простоту.