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