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