Для начала, дорогой читатель, давай вспомним, какие числа вообще называются простыми:
Натуральное число p является простым, если оно не равно 1 и делится только на 1 и на себя
Историческая справка
Первые упоминания о простых числах известны с очень давних времен. Около 300г. до нашей эры в книге "Начала" Евклид излагал важные темы о простых числах, например бесконечность простых чисел, лемма Евклида и др.
Уже более двух тысячелетий люди ломают головы над простыми числами. Давайте же разберемся, что в них такого особенного!)
Вопросы, связанные с простыми числами
- Сколько их? 10, 100, 1000 или бесконечное количество?
- Есть число n. Как узнать, простое ли оно?
- Существует ли формула, генерирующая простые числа?
- Раз их столько ученых постоянно изучают, какие существуют применения на практике?
Ну а теперь давайте разбираться с каждым пунктом по отдельности!)
Простых чисел бесконечно много
Это самое простое утверждение. Первое доказательство приписывается Евклиду (да-да, тому самому из Древней Греции).
Доказательство довольно простое, если хотите разобраться, вот ссылка на статью. Впоследствии многие ученые привели другие доказательства этого факта.
И вот тут всплывает еще один интересный вопрос: раз простых чисел бесконечно много, насколько большие числа нам известны?
Наибольшее известное простое
Один из известных рекордов поставил в свое время Эйлер:
А последним известным числом является число Мерсенна, открытое в 2018 году:
Оно содержит 24 862 048 цифр!!!
Интересный факт
За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 долларов.
Алгоритмы проверки на простоту
А вот тут мне уже есть чем вас порадовать. Всего лишь в 2002 году смогли доказать, что решение этой задачи существует за полиномиальное время. Если бы задача решалась за экспоненту, то ни один компьютер не смог бы с ней справиться за приемлемое время. Ему бы понадобилось десятки, а может и сотни лет. Поэтому этот результат оказался очень значимым.
Ну это все здорово, а где же сам алгоритм?
В том же 2002 году индийскими учеными был представлен алгоритм AKS. Суть действия в нем достаточно сложная, но главное, что он может решить нашу задачу и при этом он:
- универсален (работает для любых чисел, даже очень больших и страшных)
- полиномиален (в теории достаточно быстрый)
- детерменирован (его результат всегда абсолютно точный)
- безусловен (не зависит от недосказанных гипотез)
Кто хочет ознакомиться с ним подробнее, нажмите здесь.
Применение на практике
Если числа занимают около 1024 бит памяти, то для работы данного алгоритма понадобится 1 000 000 000 Гб памяти, что конечно же очень затрудняет его использование.
Есть области математики, в которых теория и практика сильно расходятся. И это тот самый случай.
Для некоторых классов чисел используются либо алгоритмы перебора, либо специальные тесты. Но в общем случае работают вероятностные методы (ссылки на примеры таких методов: тест Ферма, тест Миллера-Рабина, тест Соловея-Штрассена). Это значит, что результат такого теста верен не абсолютно, а с некоторой вероятностью. Работают они быстро, но бывают и ложные якобы простые числа))
Как генерировать простые числа?
Как мы узнаем чуть позже, в некоторых областях очень нужны большие количества простых чисел. Так откуда ж их брать? Может существует какая-то формула, по которой будут считаться эти числа?
Многие известные ученые пытались найти такую формулу, например Эйлер предложил использовать следующий многочлен:
Однако он перестает работать при n = 41.
Но все же существует многочлен, корнями которого являются только простые числа:
Помните про премию за самое большое простое число? Не спроста ее дают, оказывается задача генерации простых чисел очень уж нелегкая)
Практическое применение простых чисел
Самое интересное применение - криптография. Мы должны сказать большое спасибо простым числам за то, что может обмениваться сообщениями достаточно безопасно!
Если хотите узнать подробнее, как это работает, откликнетесь в комментариях. И я расскажу принцип работы криптографии с открытым ключом (RSA).
На этом наша статья подошла к концу. Информации было много, надеюсь, вы не сильно устали)
Другие интересные статьи на моем канале:
Невозможное возможно! 1 + 2 + 3 + 4 + … = -1/12. Правда или математический трюк?
Почему 0^0 = 1 ? Как интуиция нас обманывает
Почему математики не играют в казино?