Псевдопростое число — это вероятное простое число ( целое число , обладающее общим свойством для всех простых чисел ), которое на самом деле не является простым. Псевдопростые числа классифицируются в зависимости от того, какому свойству простых чисел они удовлетворяют.
В некоторых источниках термин псевдопростые числа используется для описания всех возможных простых чисел, как составных , так и реальных простых чисел.
Псевдопростые числа имеют первостепенное значение в криптографии с открытым ключом , которая использует сложность разложения больших чисел на их простые множители. В 1988 году Карл Померанс подсчитал, что разложение числа из 144 цифр обойдется в 10 миллионов долларов, а разложение числа из 200 цифр — в 100 миллиардов долларов (сегодня стоимость значительно ниже, но все еще непомерно высока). [1] [2] Но поиск двух больших простых чисел, необходимых для такого использования, также обходится дорого, поэтому используются различные вероятностные тесты на простоту , некоторые из которых в редких случаях ненадлежащим образом выдают составные числа вместо простых чисел. С другой стороны, детерминированные тесты на простоту, такие как тест на простоту AKS , не дают ложных срабатываний ; относительно них нет псевдопростых чисел.
Маленькая теорема Ферма утверждает, что если p — простое число и a взаимно просто с p , то a p −1 — 1 делится на p . Для целого числа a > 1, если составное целое число x делит a x −1 − 1, то x называется псевдопростым числом Ферма по основанию a . Отсюда следует, что если x является псевдопростым числом Ферма по основанию a , то x взаимнопрост с a . В некоторых источниках используются варианты этого определения, например, позволяющие считать псевдопростыми числа только нечетные числа. [3]
Целое число x , которое является псевдопростым числом Ферма для всех значений a , взаимно простых с x , называется числом Кармайкла .