Настоящий международный стандарт определяет методы генерации и тестирования простых чисел, требуемые в криптографических протоколах и алгоритмах. Во-первых, настоящий международный стандарт определяет методы проверки того, является ли данное число простым. Методы тестирования, включенные в настоящий международный стандарт, можно разделить на две группы: · Вероятностные тесты на простоту, которые имеют небольшую вероятность ошибки. Все описанные здесь вероятностные тесты могут объявить составное число простым. Один описанный здесь тест может объявить простое число составным. · Детерминированные методы, которые гарантированно дают правильный вердикт. Эти методы используют так называемые сертификаты простоты. Во-вторых, этот международный стандарт определяет методы генерации простых чисел. Опять же, представлены как вероятностные, так и детерминированные методы. ПРИМЕЧАНИЕ. Читатели, имеющие опыт работы в теории алгоритмов, возможно, уже сталкивались с вероятностными и детерминистическими алгоритмами. Мы подчеркиваем, что детерминированные методы в этом международном стандарте по-прежнему используют случайные биты, а термин «детерминированный» относится только к тому факту, что выходные данные верны с вероятностью, равной единице. Приложение B описывает варианты методов генерации простых чисел для удовлетворения конкретных криптографических требований. Методы генерации, доказательства и проверки простоты, определенные настоящим стандартом, применимы к криптографическим системам, основанным на свойствах простых чисел. П р и м е ч а н и е — Спецификации испытаний, приведенные в настоящем стандарте, определяют испытуемые свойства в наиболее простой форме. Непосредственное следование этим спецификациям не обязательно приведет к наиболее эффективной реализации. Особенно это касается теста Фробениуса-Грэнтэма.