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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

  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} mod r)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 з Енциклопедії цілочисельних послідовностей.

Наприклад, 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