Быстрое испытание на соответствие с 100% уверенностью?

Question

Я использую GMP (с MPIR) для типов данных произвольного размера. Я также использую его функцию проверки верности, которая использует метод Миллера-Рабина, но это не точно. Это то, что я хочу исправить.

Я смог подтвердить, что число 18446744073709551253 является простым с использованием грубой силы с использованием подхода sqrt.

Есть ли способ проверить, что большие числа являются просто или нет, с точностью 100%?

• Нельзя использовать слишком много памяти/места для хранения, допустимо принимать несколько мегабайт.

• Он должен быть быстрее, чем метод sqrt, который я использовал.

• Он должен работать для чисел размером не менее 64 бит или больше.

• И, наконец, он должен быть на 100% точным, без майбелей!

Какие у меня варианты?

Я мог бы жить с методом грубой силы (для 64-битных чисел), хотя, но из интереса, я хочу быстрее & больше. Кроме того, проверка 64-битного номера была слишком медленной: всего 43 секунды!

Answer 1

Для очень больших чисел, AKS primality test является детерминированным тестом на простоту, который работает во время O (журнал ^7.5 н лог журнал п), где п есть число интереса. Это экспоненциально быстрее, чем алгоритм O (n). Тем не менее, алгоритм имеет большие постоянные факторы, поэтому это непрактично, пока ваши числа не станут довольно большими.

Надеюсь, это поможет!

Answer 2

В общем случае 100% уверенность невозможна на физическом компьютере, так как существует небольшая, но конечная возможность того, что какой-то компонент провалился невидимо и что ответ, указанный в конце, неверен. Учитывая этот факт, вы можете запустить достаточно вероятные тесты Миллера-Рабина, что вероятность того, что число будет составным, намного меньше вероятности отказа вашего оборудования. Это не трудно проверить до 1 в 2^256 уровня определенности:

boolean isPrime(num) 
    limit <- 256 
    certainty <- 0 
    while (certainty < limit) 
    if (millerRabin returns notPrime) 
     return false 
     exit 
    else 
     certainty <- certainty + 2 
    endif 
    endwhile 
    return true 
end isPrime 

Это будет проверить, что число является простым, до достоверности 1 в 2^256. Каждый тест M-R добавляет коэффициент достоверности в четыре раза. Я видел, как получившиеся штрихи называются «промышленными простыми числами», достаточно хорошими для всех практических целей, но не совсем для теоретической математической определенности.

Answer 3

Для небольших n, пробные работы; предел там, вероятно, где-то около 10^12. Для несколько больших n существуют различные исследования (см. Работы Герхарда Джешке и Чжоу Чжана), которые вычисляют наименьшее псевдопереключение для различных коллекций оснований Миллера-Рабина; это займет около 10^25. После этого все становится тяжело.

«Большие пушки» доказывания примитивности - это метод APRCL (его можно назвать суммами Якоби или гауссовскими суммами) и методом ECPP (на основе эллиптических кривых). Оба являются сложными, поэтому вы захотите найти реализацию, не пишите свои собственные. Эти методы могут обрабатывать несколько сотен цифр.

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

Если вы можете фактор п -1, или даже частично учитывать его метод Поклингтон может определить простоты п. Метод Покинглинга очень быстрый, но факторинга может и не быть.

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

У меня есть варианты AKS и Pocklington в моем блоге.

Answer 4

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

Приоритет, доказывающий большие числа, по-прежнему остается проблемой, которая еще недостаточно решена. Если бы это было так, награды EFF были бы присуждены, и криптография имела бы некоторые проблемы, а не список простых чисел, а методы, используемые для их поиска.

Я считаю, что в ближайшем будущем возникнет новый алгоритм доказательства примитивности, который не зависит от предварительно сгенерированного списка простых чисел до квадратного корня из n, и это не делает грубой -force, чтобы убедиться, что все простые числа (и множество не простых чисел) под квадратным корнем используются в качестве свидетелей первобытности n. Этот новый алгоритм, вероятно, будет зависеть от математических понятий, которые намного проще, чем те, которые используются аналитической теорией чисел. Есть шаблоны в простых, это точно. Идентификация этих шаблонов - это совсем другое дело.