Псевдопримышленный
- Псевдопростое число — вероятное простое число, которое на самом деле не является простым.
- Псевдопростые числа классифицируются в зависимости от свойств простых чисел, которые они удовлетворяют.
- Псевдопростые числа играют важную роль в криптографии с открытым ключом, где сложность разложения больших чисел на простые множители высока.
- Существуют вероятностные тесты на простоту, которые иногда выдают составные числа вместо простых.
- Детерминированные тесты на первичность, такие как тест AKS, не дают ложных срабатываний.
- Малая теорема Ферма утверждает, что если p простое, а a взаимно просто с p, то ap−1 − 1 делится на p.
- Целое число x, являющееся псевдопростым числом Ферма для всех значений a, которые взаимно просты с x, называется числом Кармайкла.
Полный текст статьи: