Простые числа специального вида
Здесь мы приведем ряд тестов для доказательства простоты чисел специального вида. 
Следующая теорема дает эффективно проверяемый критерий простоты чисел вида . 
Теорема 2. Пусть  -- нечетное натуральное число, а . Определим последовательность по формуле 

Тогда число простое тогда и только тогда, когда . 
Отметим, что числа вида могут быть простыми только при простом , так как если , то . Поэтому теорема 2 полезна только для проверки простоты чисел вида , где  -- простое число, т. е. для нахождения чисел Мерсенна (простых чисел вида ). Их в настоящее время известно немногим более 30. 
Предложены специальные тесты для проверки простоты чисел вида . Специальные тесты предлагаются для чисел вида и , а так же-- для чисел вида и . Изучаются простые числа вида и . изучаются тесты простоты для чисел специального вида. 
Имеются тесты, позволяющие строить пары простых чисел специального вида. 
Теорема 3 Если и  -- простые числа, причем , то 
    1) при является первообразным корнем по модулю ; 
    2) при является первообразным корнем по модулю . 
Таким образом, если  -- простое число, то для проверки простоты достаточно проверить выполнение сравнений 

для или (при или соответственно). 
Заметим, что в данном разделе мы проверяли на простоту числа , для которых известно разложение или на простые множители. Общие методы построения больших простых чисел, к описанию которых мы перейдем далее, также существенно используют известное разложение на множители. 
Интересный метод построения больших простых чисел специального вида предложен Пинцем, Стейгером и Семереди. Справедлива следующая теорема. 
Теорема 4.  Пусть  -- натуральное число вида , где , . Тогда для простоты необходимо и достаточно выполнения следующих двух условий: 
    1) не является квадратом целого неотрицательного числа; 
    2) существует натуральное число такое, что 
   и 
Из этой теоремы следует такой способ построения больших простых чисел. 
    1. Выбрать , где , , и положить . 
    2. Проверить условие 1) теоремы 4; если оно не выполнено, то составное. 
    3. Для всех натуральных таких, что , проверять условие 2) теоремы 4 ( -- некоторая постоянная). Из невыполнения этого условия может следовать, что составное. Если же при некотором условие 2) выполнено, то  -- простое число. 
Оценка сложности алгоритма -- арифметических операций. 
Важной отличительной чертой предложенного метода является то, что при некотором значении существует бесконечно много простых чисел , простота которых действительно устанавливается данным алгоритмом. При этом количество таких , , оценивается снизу величиной , где -- также абсолютная постоянная. 
В работе Гордона [Gor] обсуждается вопрос о построении "сильных" простых чисел , для которых , , , где , ,  -- достаточно большие простые числа. Такие важны, например, для криптосистемы RSA. Доказано следующее утверждение: если ,  -- различные нечетные простые числа,  -- нечетное простое число, то и тогда и только тогда, когда , где и нечетно. Поэтому если , , уже построены, то следует искать в прогрессии , где пробегает множество натуральных чисел. Однако автор предлагает проверять простоту вероятностным способом. Здесь можно предложить использовать методы, описываемые ниже, поскольку известно частичное разложение на множители.