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

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

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

В криптографії, просте число ${\displaystyle p}$ є сильним, якщо виконуються такі умови^[1].

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

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

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

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

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

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

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

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

В теорії чисел, просте число є сильним, якщо воно більше ніж середнє арифметичне найближчих простих згори і знизу (інакше кажучи, воно ближче до наступного ніж до попереднього). Або алгебраїчно, дано просте число ${\displaystyle p_{n}}$, де n його індекс у впорядкованій множині простих чисел, ${\displaystyle 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 не просте.

Примітки

1. Ron Rivest and Robert Silverman, Are 'Strong' Primes Needed for RSA?, Cryptology ePrint Archive: Report 2001/007. http://eprint.iacr.org/2001/007