Такое свойство превращает эту операцию в очень полезный инструмент для систем шифрования, основанных на асимметричных ключах, как, например, RSA-алгоритм, который, в свою очередь, является основой криптографии с открытым ключом. Далее мы более подробно расскажем о связи простых чисел с криптографией и о формальной математической основе алгоритма RSA.
Простые числа и «другая» теорема Ферма
Простые числа — это подмножество натуральных чисел, больших единицы, которые делятся только на единицу и на само себя. Основная теорема арифметики утверждает, что любое натуральное число, большее единицы, всегда можно представить в виде произведения степеней простых чисел, и это представление (факторизация) является единственным. Например:
20 = 2>2∙5
63 = З>2 ∙7
1050 = 2∙3∙5>2∙7.
Все простые числа, кроме числа 2, нечетные. Единственные два последовательных простых числа — это 2 и 3. Нечетные последовательные простые числа — т. е. пары простых чисел, отличающихся на 2 (например, 17 и 19), — называются простыми числами-близнецами. Простые числа Мерсенна и числа Ферма также представляют особый интерес.
Простое число называется числом Мерсенна, если при добавлении единицы получается степень двойки. Например, 7 — число Мерсенна, так как 7 + 1 = 8 = 2>3.
Первые восемь простых чисел Мерсенна выглядят так:
3, 7, 31,127, 8191,131071, 524287, 2147483647.
В настоящее время известно чуть более 40 простых чисел Мерсенна. Самым большим из них является гигантское число: 2>43112609—1, найденное в 2008 г. Для сравнения, примерное число элементарных частиц во Вселенной меньше, чем 2>300.
Простые числа Ферма — это простые числа вида F>n = 2>2n+ 1, где n — натуральное число.
В настоящее время известно пять простых чисел Ферма: 3 (n = 0), 5 (n = 1), 17 (n = 2), 257 (n = 3) и 65537 (n = 4).
Простые числа Ферма носят имя прославленного французского юриста и математика Пьера де Ферма (1601–1665), который их открыл. Он сделал также другие важные открытия в теории простых чисел. Классической является малая теорема Ферма, которая утверждает: «Если р — простое число, и целое а не делится на р, тоа>р a (mod р).»
Этот результат имеет большое значение для современной криптографии, как мы сейчас увидим.
От Эйлера к RSA
Еще один важный результат в модульной арифметике известен как соотношение Везу. Это утверждение гласит, что если а и b — целые положительные числа, тогда уравнение НОД (a, b) = к эквивалентно существованию двух целых чисел
