С доисторических времён люди обратили внимание на то, что у одних чисел полно разных делителей, а других – совсем мало. В пределе так и вовсе два: единица и само это число.
Например: 100 делится и на 2, и на 4, и на 5, и на 25 и т.д. А вот 101 как ни крути делится только на себя и на 1. Числа, имеющие только два делителя, называют простыми.
Ну, казалось бы, простые и простые. Но в 17-м веке известный французский математик Пьер Ферма взял да и обратил особое внимание на эти простые числа. Стал выдумывать всякие теоремы, гипотезы и попытки поиска общего вида простых чисел. За ним позднее подтянулись Лейбниц и Эйлер.
В середине 18-го века русский математик прусского происхождения Христиан Гольдбах предположил, что любое чётное число больше 4-х можно представить как сумму двух простых чисел.
К настоящему дню это предположение не получило подтверждения, а задача носит название проблемы Гольдбаха. Если кто может, рекомендую на досуге решить проблему – сильно продвинете математику, получите много шекелей и признание.
Простые числа так и оставались бы просто занятным разделом математики, но примерно 50 лет назад они внезапно нашли своё применение в алгоритмах шифрования (криптографии с открытым ключом).
Американские криптографы Уитфилд Диффи и Мартин Хеллман были одними из первых (или первыми), кто заложил основы подхода.Базируясь на этих идеях, был разработан алгоритм RSA. В его основе лежит пара огромных простых чисел длиной в сотни знаков.
Их перемножают, получая число n = p·q, которое вместе с показателем e образует открытый ключ. Этот ключ может быть доступен всем желающим, его можно хоть на заборе написать: он используется для шифрования сообщений и проверки электронной подписи.
Однако расшифровать сообщение способен только владелец закрытого ключа, поскольку для его вычисления необходимо знать исходные простые множители числа n. Именно сложность разложения больших чисел на простые множители и обеспечивает надёжность системы.