Сильное простое число

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 14 мая 2011.

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

Криптография

В криптографии сильным называется простое число $p$, такое что:

1. $p$ достаточно велико
2. $p-1$ имеет достаточно большие простые делители, то есть $q_1$ в $p = a_1q_1 + 1$
3. $q_1-1$ имеет достаточно большие простые делители, то есть $q_2$ в $q_1 = a_2q_2 + 1$
4. $p+1$ имеет достаточно большие простые делители

Иногда также добавляют дополнительные условия, например $a_1 = 2$, $a_2 = 2$ и т.п.

Теория чисел

В теории чисел простое число называется сильным, если оно больше, чем среднее арифметическое из предыдущего и следующего простого числа. То есть: $p_n > {{p_{n - 1} + p_{n + 1}} \over 2}$

Последовательность сильных простых чисел начинается так:

11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, ... (последовательность A051634 в OEIS)

Для простых близнецов $(p, p+2)$ действительно: если $p>5$, p всегда сильное простое число.

Общие свойства

Существуют числа, имеющие свойства сильного простого числа в обоих определениях, например число 439351292910452432574786963588089477522344331.

См. также

• Безопасное простое число