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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Криптография[править | править вики-текст]

В криптографии сильным называется простое число 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.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]