Как компьютер проверяет, простое ли число
Простые числа — кирпичики, из которых собрано всё остальное. Но как машина за доли секунды решает, простое перед ней число или нет, если их триллионы? Разбираем приёмы — от школьного перебора до хитрого теста, который иногда даёт сбой.
Число 97 — простое, а 91 — нет, хотя оба выглядят одинаково загадочно. Спорим, ты не отличишь их на глаз за секунду? А компьютер проверяет числа из сотен цифр почти мгновенно — и от этого зависит, взломают ли твою переписку. Давай разберёмся, как он это делает.
Что вообще значит «простое»
Простое число делится без остатка только на единицу и на само себя. 2, 3, 5, 7, 11, 13 — простые. А вот 12 простым не будет: его можно разложить как 2×6 или 3×4. Числа, у которых есть «лишние» делители, называют составными.
Простые числа — это что-то вроде атомов в мире чисел. Любое целое число можно собрать из них перемножением, причём единственным способом. 60 — это 2×2×3×5, и никак иначе. Именно поэтому простые так важны: на их свойствах держится криптография, которая защищает банковские платежи, мессенджеры и пароли.
Проверить, простое ли маленькое число, легко. Вся хитрость начинается, когда в числе сотни цифр — а именно такие используют в шифровании.
Способ в лоб: перебираем делители
Самая прямая мысль: чтобы понять, простое ли число n, попробуем поделить его на 2, 3, 4, 5 и так далее. Если хоть на чём-то делится нацело — оно составное. Если ни на чём не поделилось до самого n — простое.
Это работает, но жутко медленно. Представь, что ты ищешь, можно ли разложить число 1000003 на множители, и честно делишь его на миллион вариантов подряд. Скучно и долго. К счастью, есть красивая экономия: достаточно проверить делители только до квадратного корня из числа.
Почему так? Если число n раскладывается на два множителя a×b, то они не могут оба быть больше корня из n — иначе их произведение было бы больше самого n. Значит, один из множителей точно меньше или равен корню. Это как искать пару обуви в коробках: если бы оба ботинка лежали в дальней половине полки, вместе они бы туда просто не поместились — один обязательно ближе к началу.
Для числа 1000003 корень — около 1000. Вместо миллиона проверок остаётся всего тысяча. Уже в разы быстрее, и для чисел до миллиардов этот метод вполне годится.
Когда чисел много: решето Эратосфена
А если тебе нужны не одно число, а все простые до миллиона? Перебирать делители для каждого — расточительно. Тут спасает приём, придуманный больше двух тысяч лет назад греком Эратосфеном.
Идея простая до гениальности. Выписываем подряд все числа. Берём 2 — она простая, а вот все её кратные (4, 6, 8, 10…) вычёркиваем: они точно составные. Берём следующее невычеркнутое число — 3, оно простое, вычёркиваем 6, 9, 12, 15… Потом 5, потом 7 и так далее.
- То, что осталось невычеркнутым, — и есть все простые числа.
- Каждое составное вычёркивается его делителями, поэтому ничего лишнего не теряется.
- Метод не делит числа вообще — он только «зачёркивает», а это очень быстро для компьютера.
Похоже на то, как просеивают муку через сито: мелкое (простые) проваливается и остаётся, а комки (составные) застревают и убираются. Отсюда и название — решето.
Гигантские числа и хитрый тест
Теперь самое интересное. В криптографии используют простые числа из сотен цифр. Даже способ «до корня» здесь бессилен: корень из такого числа сам по себе астрономически велик, и никакой компьютер не переберёт столько вариантов за разумное время.
Поэтому математики придумали тесты, которые не ищут делители, а проверяют простоту по косвенным признакам. Один из таких — тест Ферма. Он опирается на любопытное свойство: если число p простое, то для почти любого a выполняется хитрое равенство с остатками от деления степеней. Если равенство нарушилось — число точно составное.
Но есть подвох. Иногда составное число притворяется простым и проходит проверку. Это как фальшивая монета, которая звенит точь-в-точь как настоящая. Чтобы не попасться, тест повторяют много раз с разными a — настоящий обманщик рано или поздно проколется.
На практике чаще используют усиленную версию — тест Миллера—Рабина. Он тоже вероятностный: формально он не доказывает простоту на сто процентов, но если прогнать его, скажем, 40 раз, шанс ошибки становится меньше, чем вероятность, что твой компьютер сломается прямо во время вычисления. Для реальной жизни этого более чем достаточно.
Так как же компьютер выбирает способ
Получается, единого «правильного» метода нет — компьютер подбирает инструмент под задачу:
- Маленькое число и нужен честный ответ — перебор делителей до корня.
- Нужен список всех простых до какого-то предела — решето Эратосфена.
- Огромное число для шифрования — тест Миллера—Рабина, быстро и с ничтожным риском ошибки.
Любопытно, что в 2002 году математики придумали тест (его называют AKS), который гарантированно и быстро доказывает простоту любого числа без капли везения. Это был прорыв в теории. Но на практике он медленнее вероятностных тестов, поэтому шифрование по-прежнему доверяет «фальшивомонетчику» Миллеру—Рабину — он просто шустрее.
Так что в следующий раз, отправляя сообщение в защищённом мессенджере, вспомни: где-то в глубине твоего телефона компьютер только что подобрал пару гигантских простых чисел, сорок раз проверил их на подлинность — и всё это за неуловимую долю секунды.