Доказуемое простое число

Простое целое число, вычисленное с помощью алгоритма проверки простоты

В теории чисел доказуемое простое число — это целое число , которое было вычислено как простое с использованием алгоритма доказательства простоты . Методы бутстрэппинга с использованием теста Поклингтона на простоту являются наиболее распространенными способами генерации доказуемых простых чисел для криптографии. ^{[1] [2]} Сравните с вероятным простым числом , которое, вероятно (но не обязательно), является простым числом, основываясь на результатах вероятностного теста на простоту .

В принципе, каждое простое число может быть доказано как простое за полиномиальное время с помощью теста простоты AKS . Другие методы, которые гарантируют, что их результат является простым, но которые не работают для всех простых чисел, полезны для случайной генерации доказуемых простых чисел. ^[3]

Доказуемые простые числа также были получены на встроенных устройствах. ^[4]

Смотрите также

• Вероятное простое число
• Тест на простоту

Ссылки

1. C. Couvreur и JJ Quisquater (1982), Введение в быструю генерацию больших простых чисел , Philips Journal of Research, т. 37, стр. 231–264
2. Крэндалл, Ричард; Померанс, Карл (2005). Простые числа: вычислительная перспектива . Springer. стр. 174–178. ISBN 978-0387-25282-7.
3. Моллин, Ричард А. (2002), RSA и криптография с открытым ключом, Дискретная математика и ее приложения, CRC Press, стр. 124–125, ISBN 9781420035247.
4. Кристоф, Клавье. "Эффективное создание доказуемых простых чисел на встроенных устройствах" (PDF) . Международная ассоциация криптологических исследований .