Каким алгоритмом можно проверить Большое число на простоту?

Question

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

Есть ли методы гарантированной проверки числа на простоту без необходимости полного "перебора"?
Везде встречаются либо метод "поделить на все числа меньше данного" либо вероятностные (не дают гарантии коррекности), другого способа определить нет?
Если для чисел до 100 знаков можно еще "перебрать" все хотябы до половины, то с числами в сотни тысяч знаков это бессмысленная затея, мне казалось должны быть способы определить подобное без необходимости совершать 10^100500 операций.

Answer 1

[SeptiM]

Расклад примерно такой. Пусть n -- длина числа, т.е. обычный перебор работает за 2^{c * n}.

1) Вероятностный тест Рабина-Миллера можно реализовать за O(k n^2 log n), где k -- число попыток. Вероятность ложноположительной ошибки 4^-k. При k=100 это значение настолько безумно мало, что скорее в вашей программе найдется критический баг, процессор сделает ошибку в вычислениях и взломщик выиграет в лотерею и все это одновременно, чем число окажется составным.

2) Детерминированный AKS (en.wikipedia.org/wiki/AKS_primality_test). Работает за O(n^{6 + eps}). Интересен скорее теоретически.

3) Эллиптический тест на простоту (en.wikipedia.org/wiki/Elliptic_curve_primality). Эмпирически работает за O(n^5). Интересен тем, что в случае успеха возвращает сертификат простоты.

Comments

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

1 реализовал, но не ясно как он будет работать с очень большими числами

[SeptiM]

А что значит "большое число"? Сколько это в количестве цифр в десятичной записи?

Answer 2

[Кирилл Пензин]

Как вариант: поделить на все простые числа, не превышающие квадратного корня из данного числа.

Comments

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

это ускорит процесс, но тут работа вида "делить очень большое число на очень большое число", мне кажется должны быть более адекватные алгоритмы

[rehab]

Можно подробней, про Ваше решение, не очень понятно. Какое число делить и почему именно квадратный корень от числа

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

кстати, где можно посмотреть доказательство этого утверждения?

[MiiNiPaa]

Для доказательства хватает школьной математики:
1) Если число n делится нацело на k, оно также делится на m=n/k (Базовые свойства деления)
2) Из этого следует, что каждый делитель из множества чисел меньше некого числа x, такого, что x·x = n, имеет парный ему уникальный делитель из множества чисел больше x. И наоборот
2.1) Соответственно проверяя число 100 на простоту, 25 как делитель проверять не нужно: мы уже проверили 4 до этого и убедились что число не простое.
3) Число x — квадратный корень из n.

Answer 3

[h8nor]

методы гарантированной проверки

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


Вместо перебора делителей можно использовать http://ru.wikipedia.org/wiki/Признаки_делимости

Comments

[Mrrl]

Хороший алгоритм. Но для 1000-значного числа (скажем, 4096 бит), даже если мы найдём простые q,r, такие, что r=2*q+1, q>2^24 (судя по алгоритму из английской версии, этого достаточно), то нам понадобится примерно 64 или 80 ГБ памяти - только для возведения многочлена в степень.

[Mrrl]

Например, q=33554771, r=67109543. Похоже, что таких пар довольно много - в окрестности 2^24 примерно 3 числа на 1000.

[h8nor]

Mrrl: Благодарю за критическое замечание.

[Mrrl]

Дѣаволъ: На самом деле, это не важно. Для таких чисел потребуется примерно 2^80 операций, т.е. несколько миллионов лет при расчёте на одном ядре (сколько именно - зависит от быстродействия компьютера и качества реализации алгоритма). За разумное время - от дня до года - можно попробовать доказать простоту 100-значного числа. А для него и памяти нужно гораздо меньше.

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

Mrrl: 100-значное не проблема, его можно за минуту просчитать, но что делать если знаков скажем 100000

[Mrrl]

Виталий Пухов: Как это вы просчитаете его за минуту, интересно знать?

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

Mrrl: MillerRabin 1000 100-значных за 10 секунд, после при желании можно будет проверить "в лоб"

[Mrrl]

Виталий Пухов: А "в лоб" это как?

[Mrrl]

Виталий Пухов: И сколько времени занимает одна попытка для Miller-Rabin?

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

Mrrl: "в лоб" поделить на все простые числа, не превышающие квадратного корня из данного числа., около 10 мс

[Mrrl]

Таких чисел примерно 10^48. Если одно деление занимает, скажем, 10 нс, то потребуется 10^32 лет.

[Mrrl]

Виталий Пухов: Но если воспользоваться детерминированным тестом Миллера, то достаточно будет прогнать тест Миллера-Рабина для всех стартовых значений от 2 до 107000 (=2*ln(10^100)^2), т.е. можно уложиться в 20 минут. Для 1000-значного числа потребуется уже 200000 минут, или 5 месяцев. Но более быстрый алгоритм вы вряд ли найдёте.

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

Mrrl: ясно, выходит проверить не получится, жаль конечно

[Mrrl]

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

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

Mrrl: да цель была немного другая, хотел оценить свой метод, он дает возможность подобрать 5 чисел, 1 из которых 100% является простым, остальные 4 нет. Проверить смог на первых 10млн чисел

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

Mrrl: разложение на множители не выглядит тривиальной задачей для числа с большим числом знаков

[Mrrl]

Виталий Пухов: Разложение является тривиальной задачей для чисел, которые строятся, как произведение известных простых чисел. Там разложение известно сразу.
Для вашей задачи теста Миллера-Рабина более, чем достаточно. Если 10 случайных проверок дадут положительный результат, то вероятность того, что число составное - меньше одной миллионной. Так что доля простых чисел, которая получится по результатам проверки, будет очень близка к истине (ошибка будет соответствовать статистической погрешности).

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

Mrrl: если так то выходит алгоритм получился достаточно эффективным, потому как легко получается найти простое число порядка 999999^100, хотя не уверен что таки числа кому ни будь нужны)

Answer 4

[Сергей Протько]

Быстро это сделать не выйдет. Не спроста же большие простые числа используют в криптографии. Даже если принять во внимание тот факт, что вы не пытаетесь разложить это добро на множители.

Comments

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

Пусть не очень быстро, допустим день или неделя на 1 число, проблема в том что подобных алгоритмов я не нашел.

Answer 5

[Александр Дубина]

на сколько я помню, это очень тяжелая задача, и за нахождение простого числа в миллиард знаков дают около полумиллиона долларов. Дерзайте)