1. Что такое простые числа?
Простые числа ― это числа больше единицы, которые делятся только на 1 и сами на себя. Их можно сравнить с атомами вещества – они составляют неделимые единицы любого числа. Например, 12 можно разложить на произведение трех простых чисел 2*2*3, а число 17 нельзя, оно делится только на 17 и 1, поэтому оно простое..
Самое большое простое число известное на сегодняшний день равно 2⁸² ⁵⁸⁹ ⁹³³ – 1. В оригинале оно имеет длину 24 862 048 десятичных цифр (система счисления по основанию 10). Такая сокращенная запись простого числа называется числом Мерсенна. Оно рассчитывается по формуле 2ⁿ-1, где n – любое натуральное число, то есть положительное число от нуля до бесконечности.
2. Как найти простые числа?
Находить простые числа довольно сложно, потому что они очень неравномерно распределены в множестве натуральных чисел. Кроме того, нет четкого алгоритма их определения. Одним из первых способов поиска было так называемое решето Эратосфена, жившего в III веке до н. э.: из длинного списка чисел последовательно вычеркивались те, что делятся на 2 и на 3. Этот способ не стал универсальным, так как не позволил бы найти простые числа больших размеров. В 17 веке Пьер де Ферма (1601-1665 гг.) сделал предположение, что все числа вида Fn =2²ⁿ+1 — простые. Но затем Леонард Эйлер (1707-1783 гг.) нашел третий делитель (помимо единицы и самого числа) для числа 2³²+1 — и формула Ферма также не стала единым алгоритмом.
3. Как работает факторизация?
Как мы сказали ранее, абсолютно любое число можно представить как произведение небольших простых чисел. Например, 120 ― это 2*2*3*2*5. Этот процесс сведения числа к простым числам называется факторизацией. А что если перемножить два больших простых числа и потом попробовать полученное произведение факторизовать обратно? Для компьютера перемножение не такая уж и сложная задача. Но вот разложить число на множители обратно ― с этим с трудом справляются даже суперкомпьютеры. Таких вариантов огромное множество. Даже самым простым способом – методом перебора – компьютеру понадобится вечность (реальная вечность!), чтобы перебрать простые делители большого числа, получившегося в результате перемножения. Например, на факторизацию числа длиной 400 цифр у обычного компьютера частотой 1 Ггц уйдет примерно 10¹⁹⁴ секунд или 2,78*10¹⁹⁰ часов. Для сравнения возраст вселенной 10¹⁸ секунд или 2,78*10¹⁴ часов.
4. Как простые числа используют в шифровании?
Сложность факторизации произведения простых чисел стала причиной использования их в алгоритмах шифрования — то есть преобразования информации в такой вид, что ее содержание становится недоступным для посторонних людей. Один из самых известных алгоритмов шифрования — это RSA, названный по первым буквам фамилий их его создателей ― Rivest, Shamir и Aldeman. В нем задействуют два больших простых числа, произведение которых нужно для создания ключей шифрования. Один из них служит для шифрования данных, второй — для расшифровки. И это огромные числа! Они могут содержать 309 цифр (2¹⁰²⁴) или 617(2²⁰⁴⁸) цифр.
5. В каких сферах применяют шифрование?
Алгоритм RSA используют в операционных системах, для цифровой подписи документов, защиты коммуникации через интернет, шифрования банковских транзакций. Например, когда вы оплачиваете покупки в интернете — работают простые числа. При вводе номера карты цифры шифруются по алгоритму RSA для передачи на сервер и ваши персональные данные остаются под защитой.
