Подписывайтесь на канал в Яндекс. Дзен или на канал в телеграм "Математика не для всех", чтобы не пропустить интересующие Вас материалы.
Приветствую Вас, уважаемые Читатели! Сегодня поговорим об основной теореме арифметики - на первый взгляд достаточно простом и легко доказуемом утверждении (в отличие, например, от теоремы Жордана). Тем не менее основная теорема арифметики, впервые описанная Эвклидом, - это краеугольный камень теории чисел вообще и всей современной криптографии. Поехали!
Формулировка теоремы
"Каждое натуральное число можно представить в виде единственного произведения простых множителей" - и это всё, разве что в символьной форме выглядит вот так:
Задача представления натуральных чисел в таком виде (каноническом) называется задачей факторизации. И это очень крепкий алгоритмический орешек: с числом 686 мы справились вручную, а вот с числом из 1024 знаков не справится ни один современный классический компьютер за вменяемое время. Поэтому задача факторизации целых чисел была положена в основу систем шифрования с открытым ключом - RSA. Вот один яркий пример:
В основе алгоритма тот факт, что даже зная открытый ключ (как правило, очень длинное число), злоумышленник не сможет его "факторизовать", не зная специального закрытого ключа, известного лишь адресату и адресанту. Первым шагом этого алгоритма является лишь выбор 2 простых чисел!
Т.е. сохранность информации зависит просто от того, сможет ли преступник разложить число на множители за адекватное время! Чистая математика бесполезна (ирон.).
Вот так Евклид и простые числа стоят на страже конфиденциальности каждого из нас! Далее рассмотрим алгоритм RSA на пальцах: он хоть исторически один из первых, но находит очень активное применение и сейчас, например, в ЭЦП.
Почитайте про теорему Жордана - абсолютно тривиальное, но сложнодоказуемое утверждение.
Ставьте лайк и подписывайтесь! ! ССЫЛКА НА ДЗЕН-КАНАЛ и TELEGRAM.
Второй проект - канал "Русский язык не для всех".