Основная теорема арифметики: без неё интернет бы остановился

Подписывайтесь на канал в Яндекс. Дзен или на канал в телеграм "Математика не для всех", чтобы не пропустить интересующие Вас материалы.

Приветствую Вас, уважаемые Читатели! Сегодня поговорим об основной теореме арифметики — на первый взгляд достаточно простом и легко доказуемом утверждении (в отличие, например, от теоремы Жордана). Тем не менее основная теорема арифметики, впервые описанная Эвклидом, — это краеугольный камень теории чисел вообще и всей современной криптографии. Поехали!

Источник: https://al-fa-s.ru/image/cache/catalog/a-new/na_sayt_matetika/resized_1920x1080/7.19.8%20%200%2C46х0%2C625-1500×1500.jpg

Формулировка теоремы

"Каждое натуральное число можно представить в виде единственного произведения простых множителей" — и это всё, разве что в символьной форме выглядит вот так:

На факультативных занятиях ОТА проходят уже в 7 классе

Задача представления натуральных чисел в таком виде (каноническом) называется задачей факторизации. И это очень крепкий алгоритмический орешек: с числом 686 мы справились вручную, а вот с числом из 1024 знаков не справится ни один современный классический компьютер за вменяемое время. Поэтому задача факторизации целых чисел была положена в основу систем шифрования с открытым ключом — RSA. Вот один яркий пример:

Перед Вами зашифрованное RSA-сообщение, которое было опубликовано 1977 году в колонке «Математические игры» Мартина Гарднера в журнале Scientific American. За его дешифровку предлагался денежный приз. Открытый ключ имел длину 425 бит. Как итог, это сообщение "взламывали" 17 лет группой из 600 компьютеров. В результате получили сообщение: «Волшебные слова — это брезгливый ягнятник».

В основе алгоритма тот факт, что даже зная открытый ключ (как правило, очень длинное число), злоумышленник не сможет его "факторизовать", не зная специального закрытого ключа, известного лишь адресату и адресанту. Первым шагом этого алгоритма является лишь выбор 2 простых чисел!

Т.е. сохранность информации зависит просто от того, сможет ли преступник разложить число на множители за адекватное время! Чистая математика бесполезна (ирон.).

Вот так Евклид и простые числа стоят на страже конфиденциальности каждого из нас! Далее рассмотрим алгоритм RSA на пальцах: он хоть исторически один из первых, но находит очень активное применение и сейчас, например, в ЭЦП.

Почитайте про теорему Жордана — абсолютно тривиальное, но сложнодоказуемое утверждение.

Ставьте лайк и подписывайтесь! ! ССЫЛКА НА ДЗЕН-КАНАЛ и TELEGRAM.

Второй проект канал "Русский язык не для всех".

Понравилась статья? Поделиться с друзьями:
Математика не для всех
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: