Как определяется простота числа в криптографии?

Для определения простоты числа в криптографии используют тесты простоты — алгоритмы, которые позволяют точно или с некоторой долей вероятности определить, является ли число простым. infourok.ru

Тесты простоты делятся на две категории: истинные (детерминированные) и вероятностные. infourok.ru ru.ruwiki.ru

Истинные тесты всегда выдают факт простоты либо составности числа. ru.ruwiki.ru Например, к ним относится перебор делителей — алгоритм тестирования простоты числа путём полного перебора всех возможных потенциальных делителей. infourok.ru

Вероятностные тесты дают ответ о составности числа либо его несоставности с некоторой вероятностью. ru.ruwiki.ru Некоторые из них:

• Тест Ферма. cyberleninka.ru applied-research.ru Основан на одноимённой теореме, но допускает псевдопростые числа. applied-research.ru
• Тест Миллера — Рабина. applied-research.ru Улучшает метод Ферма за счёт разложения числа и вероятностных проверок, но не гарантирует стопроцентную точность. applied-research.ru
• Тест Соловея — Штрассена. infourok.ru applied-research.ru Использует символ Якоби и даёт более надёжные результаты, но остаётся вероятностным. applied-research.ru

Одной из проблем тестирования простоты является существование псевдопростых чисел, которые могут вводить в заблуждение вероятностные алгоритмы. applied-research.ru