Алгоритмы доказательства первичности для чрезвычайно больших целых чисел, не имеющих конкретной формы

Question

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

Вот мои требования:

1- он должен быть совершенно правильно

2- он должен быть установлен на базовом домашнем компьютере

3- Он должен пройти курс в течение нескольких недель или месяцев.

Ограничение моей памяти - 8 ГБ оперативной памяти (я могу установить свои параметры в зависимости от количества кеша) на выделенной машине с жестким диском 1 тб. Я буду рассматривать номера по одному в течение нескольких месяцев.

Редактировать 1: Я хорошо осведомлен о том, что это сложная арена, в которой можно конкурировать, если не почти невозможно, используя существующие методы. Я не использую текущие методы, и мне нужен способ доказать правильность моих методов для очень больших чисел.

Edit2: Часть причины, по которой мне нужен не вероятностный метод, заключается в том, что это будет попытка награды EFF и, после этого, на второй награде EFF. Если мои методы правильны (и это один из них), я должен быть в состоянии сделать все это с помощью своего ноутбука.

Answer 1

Из того, что я понимаю, вы ищете алгоритм, который:

• детерминированным
• довольно быстро
• с довольно разумным объемом памяти

Я не уверен, о последней части, так как я никогда не пытался ее реализовать (пока), но я знаю, что проблема примитивности была решена для общих чисел. Другими словами, вы можете определить, является ли число простым или нет, со 100% уверенностью, независимо от формы. Вы должны взглянуть на AKS primality test, который является первым известным алгоритмом, который решает эту проблему.

Как вы уже сказали, это может занять некоторое время, но в конечном итоге он закончит с определенным ответом. Сложность оптимизированной версии O ((log n)^7.5 (log n пропорциональна числу цифр n).

Однако, поскольку эта среда исполнения довольно большая, и вы хотите протестировать много чисел, вы должны рассмотреть возможность фильтрации таких чисел с помощью более быстрого, недетерминированного алгоритма. Другими словами, я попытался бы запустить Miller-Rabin test для нескольких чисел (a = 2,3,5,7, ... - первый десяти простых чисел должно быть достаточно, но даже если вы действительно хотите получить лучшую точность, вы, вероятно, не должны выходить за пределы 50 простых чисел). Вероятность того, что тестируемый номер является ложным, после тестов К Миллера-Рабина меньше 1/4^k, если я правильно помню. Другими словами, вы можете запустить небольшое количество тестов (не говоря уже о том, что эти тесты очень быстрые) и быть очень уверенными, если число является простым (если какой-либо из этих тестов терпит неудачу, число определенно НЕ просто). Тесты MR проходят, запускайте алгоритм AKS на тестируемом номере, чтобы убедиться (как вы можете видеть на странице MR wikipedia, наименьший ложный положительный результат, даже после нескольких тестов, увеличивается с очень высокой скоростью).