Вероятное простое число
- Вероятное простое число (PRP) — целое число, удовлетворяющее условию, которое удовлетворяют все простые числа.
- Различные типы вероятных простых чисел имеют разные специфические условия.
- Хотя могут существовать вероятные простые числа, которые являются составными (псевдопростые), условие обычно выбирается для того, чтобы сделать такие исключения редкими.
- Тест Ферма на составность работает следующим образом: задано целое число n, выберите некоторое целое число a, которое не кратно n.
- Вероятная примитивность является основой для эффективных алгоритмов тестирования на примитивность, которые находят применение в криптографии.
- Идея заключается в том, что, хотя для любого фиксированного a существуют составные вероятностные простые числа с основанием a, мы можем надеяться, что существует некоторое фиксированное значение P < 1, такое, что для любого данного составного n, если мы выберем a случайным образом, вероятность того, что n является псевдопростым для основания a, не превышает P.
Полный текст статьи: