Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

Простое число – это целое число больше 1, единственный фактор которого – 1 и сам по себе. Фактор – это целое число, которое можно равномерно разделить на другое число. К первым нескольким простым числам относятся 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Числа, имеющие более двух факторов, называются составными числами. Номер 1 не является ни простым, ни составным.

Для каждого числа p существует простое число p’ с конечной целью, что p’ более заметно, чем p. Это научное подтверждение, которое было показано в старых доказательствах греческим математиком Евклидом, говорит о том, что “самого большого” простейшего числа не существует. По мере того, как продолжается расстановка нормальных чисел N = {1, 2, 3, …}, простые числа становятся все менее частыми и их становится все труднее обнаружить за разумное время. На момент написания статьи наибольшее известное простое число имеет более 23 миллионов цифр. Оно обозначено как M77232917 и имеет на миллион цифр больше, чем предыдущий рекордсмен.
Пошаговые инструкции для принятия решения о том, является ли число простым.

Компьютер может быть использован для тестирования невероятно огромного количества, чтобы проверить, являются ли они первичными. В любом случае, на том основании, что нет никаких ограничений на то, насколько огромным может быть число, всегда есть момент, когда тестирование оказывается слишком невероятным поручением даже для самых доминирующих суперкомпьютеров.

Различные вычисления были определены как попытка получить все возрастающие простые числа. Например, предположим, что n – это целое число, и пока неизвестно, является ли n простым или составным. Для начала возьмите квадратный корень (или 1/2 интенсивности) n; в этот момент округлите это число до ближайшего целого числа и назовите результат m. В этот момент найдите остальные сопровождающие остатки:
qm = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2

Число n является простым, если и только если ни одно из q, как определено выше, не является целым числом.
Мерсенн и Фермат праймы
Мерсеннская премьера должна быть сведена к форме 2 n – 1, где n – это простое число. Первые известные значения n, производящие праймы Мерсена, – это где n = 2, n = 3, n = 5, n = 7, n = 13, n = 17, n = 19, n = 31, n = 61, и n = 89.

Фермат-премьер – это число фермата, которое также является простым числом. Ферматное число F n имеет форму 2 m + 1, где m – n-я сила 2 (то есть m = 2 n, где n – целое число).
Простые числа и криптография

Шифрование требует критических указаний: алгоритм (используемая процедура) не нужно держать в секрете, но ключ должен. Даже самый изощренный хакер в мире не сможет расшифровать данные до тех пор, пока ключ остается секретным: а простые числа очень полезны для создания ключей. Например, качество шифрования открытых/закрытых ключей заключается в том, насколько сложно вычислить результат двух произвольно выбранных простых чисел. Однако, как правило, очень сложно и утомительно вычислить, какие два простых числа были использованы для создания огромного элемента, когда известен только этот элемент.
В криптографии RSA (Rivest-Shamir-Adleman) с открытым ключом простые числа всегда должны быть уникальными. Однако приметы, используемые в схемах криптографии с использованием ключей Диффи-Хеллмана и стандарта цифровой подписи (DSA), часто стандартизируются и используются в большом количестве приложений.