Простые числа и их роль в шифровании
Простые числа делятся только на единицу и на самих себя. Они служат основой разложения целых чисел на множители, встречаются в задачах шифрования и ставят перед математикой вопросы без окончательного ответа.
Умножить два целых числа обычно проще, чем по результату восстановить исходные множители. Для небольших чисел разница почти незаметна: число 35 быстро распадается на 5 и 7. Но при определённых условиях увеличение размера чисел превращает обратную задачу в серьёзное вычислительное препятствие. На этой разнице основана часть современной криптографии.
В центре истории стоят простые числа. Они кажутся скромными объектами школьной арифметики, однако соединяют понятные каждому действия с вопросами, которые до сих пор остаются открытыми. Их свойства важны задолго до появления компьютеров и продолжают изучаться независимо от практических применений.
1Что значит «простое»
Натуральное число больше единицы называется простым, если у него ровно два положительных делителя: единица и оно само. Таковы 2, 3, 5, 7 и 11. Число 9 составное, потому что делится также на 3. Единицу к простым числам не относят.
Любое целое число больше единицы можно разложить на простые множители. Например, 60 получается как 2 × 2 × 3 × 5. Если не учитывать порядок множителей, такое разложение единственно. Это свойство делает простые числа своеобразными строительными деталями умножения.
Сравнение с деталями помогает понять и место единицы. Если бы она считалась простым множителем, её можно было бы дописывать к разложению сколько угодно раз. Тогда привычная формулировка единственности потребовала бы дополнительных оговорок. Современное определение сохраняет правило ясным и удобным.
2Решето Эратосфена
Один из способов найти простые числа в заданном промежутке называется решетом Эратосфена. Сначала выписывают числа начиная с двойки. Первое невычеркнутое число оставляют, а его большие кратные вычёркивают. Затем переходят к следующему невычеркнутому числу и повторяют действие.
После двойки исчезают её кратные: 4, 6, 8 и далее. После тройки вычёркиваются ещё оставшиеся кратные трёх. Числа, которые проходят через это «сито», оказываются простыми. Составное число обязательно имеет простой делитель и потому не может остаться незамеченным.
Для поиска до выбранной границы не нужно проверять все числа подряд до самого конца. Достаточно обработать простые числа, не превышающие квадратного корня из границы. Если составное число имеет два множителя, хотя бы один из них не больше его квадратного корня.
| Число | Положительные делители | Вид |
|---|---|---|
| 2 | 1, 2 | Простое |
| 9 | 1, 3, 9 | Составное |
| 13 | 1, 13 | Простое |
| 15 | 1, 3, 5, 15 | Составное |
3Почему простых бесконечно много
Доказательство бесконечности простых чисел можно понять без сложных вычислений. Представим, что удалось составить полный конечный список всех простых. Перемножим числа из списка и прибавим единицу. Полученное число не делится без остатка ни на одно из перечисленных простых.
Причина проста: произведение делится на каждое число списка, а добавленная единица оставляет остаток. Новое число может само оказаться простым. Если оно составное, среди его простых делителей всё равно найдётся число, которого в списке не было. В обоих случаях предположение о полном списке нарушается.
Это рассуждение не даёт способа каждый раз получать простое число одним прибавлением единицы. Оно доказывает другое: любой конечный перечень обязательно неполон. Так арифметическая операция превращается в вывод о бесконечном множестве.
4Где возникает шифрование
В некоторых системах с открытым ключом используются произведения больших простых чисел. Часть сведений делают открытой, а другую часть сохраняют в тайне. Математические связи позволяют выполнять нужные операции с открытыми данными, не раскрывая весь секретный материал.
Известный пример такого подхода — RSA. Для него существенна трудность разложения большого специально выбранного числа на множители. Перемножить исходные простые числа относительно легко, а восстановить их из произведения при подходящих размерах существенно сложнее известными классическими способами.
Здесь важно различать проверку простоты и поиск множителей. Можно достаточно эффективно установить, что большое число простое, не перебирая все возможные делители по школьной схеме. А разложение другого большого числа на простые множители остаётся отдельной задачей с иными вычислительными затратами.
Не вся криптография устроена одинаково. Существуют методы, основанные на других математических задачах, а также системы с общим секретным ключом. Поэтому фраза «всё шифрование держится на простых числах» была бы неверной. Простые числа играют заметную роль, но не объясняют всю защиту информации.
5Вопросы без окончательного ответа
По мере роста чисел простые встречаются в среднем реже. При этом они не прекращаются, а расстояния между соседними простыми меняются. Простое правило, которое в бытовом смысле перечисляло бы их без проверки и сразу объясняло все промежутки, из школьного определения не следует.
Один из известных вопросов касается пар простых чисел с разностью два. Примеры таких пар — 11 и 13, 17 и 19. Предположение о том, что подобных пар бесконечно много, известно как гипотеза о простых близнецах. Оно отличается от доказанного утверждения о бесконечности всех простых чисел.
Другая знаменитая задача — сильная гипотеза Гольдбаха: каждое чётное целое число больше двух предполагается представимым как сумма двух простых. Проверка множества примеров поддерживает догадку, но не заменяет доказательство для всех чисел. Именно эта разница между наблюдением и общим выводом делает простую арифметику настоящим исследованием.