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

Сильне просте число (англ. strong prime) — це просте число з певними особливими властивостями. Визначення сильного простого числа різниться в криптографії і теорії чисел.

Визначення в криптографії

В криптографії, просте число $p$ є сильним, якщо виконуються такі умови.

1. $p-1$ має великий простий дільник $r$;
2. $p+1$ має великий простий дільник $s$;
3. $r-1$ має великий простий дільник $t$.

Іноді просте число, яке задовольняє підмножині наведених умов, також називається сильним.

Алгоритм Гордона для генерації сильних простих чисел

Алгоритм генерує сильне просте число.

1. Утворити два великих простих $s$ і $t$ приблизно однакової бітової довжини.
2. Обрати ціле $i_{0}.$ Знайти перше просте в послідовності $2it+1,$ для $i=i_{0},i_{0}+1,i_{0}+2,\dots .$ Позначити це просте як $r=2it+1.$
3. Обчислити $p_{0}=2(s^{r-2}modr)s-1.$
4. Обрати ціле $j_{0}.$ Знайти перше ціле в послідовності $p_{0}+2jrs,$ для $j=j_{0},j_{0}+1,j_{0}+2,\dots .$ Позначити це просте як $p=p_{0}+2jrs.$
5. Повернути(p).

Обґрунтування: щоб побачити, що просте $p$ повернуте алгоритмом Гордона насправді сильне, зауважимо по-перше (припускаємо, що $r\not =s$), що $s^{r-1}\equiv 1{\pmod {r}};$ це випливає з теореми Ферма. Звідси, $p_{0}\equiv 1{\pmod {r}}$ і $p_{0}\equiv {\pmod {s}}.$ Зрештою,

1. $p-1=p_{0}+2jrs-1\equiv 0{\pmod {r}},$ і отже $p-1$ має простий дільник $r$;
2. $p+1=p_{0}+2jrs+1\equiv 0{\pmod {s}},$ і отже $p+1$ має простий дільник $s$; і
3. $r-1=2it\equiv 0{\pmod {t}},$ і отже $r-1$ має простий дільник $t$.

Визначення в теорії чисел

В теорії чисел, просте число є сильним, якщо воно більше ніж середнє арифметичне найближчих простих згори і знизу (інакше кажучи, воно ближче до наступного ніж до попереднього). Або алгебраїчно, дано просте число $p_{n}$, де n його індекс у впорядкованій множині простих чисел, $p_{n}>{{p_{n-1}+p_{n+1}} \over 2}$. Перші кілька простих чисел такі

11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, 107, 127, 137, 149, 163, 179, 191, 197, 223, 227, 239, 251, 269, 277, 281, 307, 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499 послідовність A051634 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.

Наприклад, 17 — це сьоме просте число. Шосте і восьме, 13 і 19, їхня сума становить 32, половина 16. Тобто 17 — сильне просте.

В двійках простих чисел близнюків (p, p + 2) з p > 5, p завжди сильне просте, бо 3 повинно ділити p − 2, тобто p − 2 не просте.