Простые числа
Простые числа намного полезнее, чем вы можете подумать, полагая их чисто умозрительными конструктами.
Простые числа — те числа, которые делятся без остатка только на само себя и 1. Это означает, что простое число нельзя представить в виде произведения (состоящего только из целых положительных чисел), кроме как:
[простое число] х 1 = [простое число]
Простые и составные
Составные числа — это числа, у которых есть делители, кроме самих себя и 1. Таким образом, все целые положительные числа, кроме 0 и 1, — либо простые, либо составные. Любое составное число можно представить в виде произведения простых сомножителей, то есть его можно разложить на множители, включающие только простые числа. Это наводит на мысль о важности простых чисел: это первичные блоки, из которых можно построить все остальные числа. Распределение простых чисел Теорема о распределении простых чисел, доказанная в XIX в., утверждает, что вероятность того, что случайным образом выбранное число n — простое, везде пропорциональна количеству цифр в нем, или логарифму n. Это означает, что чем больше число, тем меньше вероятность того, что оно будет простым.
Средний интервал между следующими друг за другом простыми числами к n приблизительно равен логарифму n, или ln(n).
Найти простое
Один из способов определения простого числа — «тест простоты». Если n — исследуемое число, то нужно попробовать разделить его на все числа больше 1 и меньше 1/2 n.
Самое большое обнаруженное простое число (на апрель 2015) содержит 17 425 170 знаков, это 257 885 161 – 1. Не стоит засиживаться до ночи, пытаясь выяснить следующее, если только вы не специализируетесь на этом, однако Фонд электронных рубежей (Electronic Frontier Foundation) назначил премию за первое простое число минимум в 100 миллионов знаков, а также за первое простое число минимум в пол миллиарда знаков.
Величайшие математические умы, а теперь еще и самые сложные компьютерные программы, давно пытаются найти закономерности в простых числах, но никакой предсказуемой закономерности до сих пор не было обнаружено.
Решето Эратосфена
Древнегреческий математик Евклид Александрийский, живший во II или III вв. до н. э., известен нам как первый человек, который выделил простые числа. Другой древнегреческий математик Эратосфен, II в. до н. э., представил свое так называемое «решето» для установления простых чисел. Оно годится только для относительно малых чисел, но его просто использовать.
Нарисуйте таблицу с 10 колонками и столькими рядами, сколько вам нужно, чтобы вместить числа, которые вы хотите проверить: если вы хотите проверить числа до n, нужно сделать таблицу от 1 до n. Начиная с 4, продвигайтесь по таблице и вычеркивайте все, что делится на 2. Затем вычеркните все, что делится на 3, затем — на 5, затем — на 7 и т. д., прокладывая путь сквозь простые числа. Когда вы доберетесь до делителя 1/2 n – 1, можете остановиться, так как большие числа не могут быть делителем n или меньших чисел. Числа, которые не были зачеркнуты, — простые.
Прискорбное пренебрежение
После Древней Греции и вплоть до XVII в. в интерес к простым числам почти отсутствовал. Даже в XVII в., простые числа не использовались нигде, кроме как в чистой математике, но ими, по крайней мере, стало позволительно поиграть. Они заняли свое законное место в компьютерную эпоху, с появлением необходимости в разработке шифровальных алгоритмов.
Есть работа
Простые числа пребывали в ленивом бездействии, пока не пришла необходимость в шифровании данных. Сейчас мы ежедневно посылаем несметное количество защищенных транзакций и других секретных данных через интернет, а простые числа предоставляют аналог защищенных фургонов, в которых перевозят данные. Начнем, перемножив два очень больших простых числа, чтобы получить составное число:
Р1 х Р2 = С
Составное число используется для генерации кода, который называется открытый ключ, который банк (или кто-нибудь) посылает человеку, желающему зашифровать свои данные. Если вы покупаете что-нибудь онлайн, данные вашей кредитки должны быть зашифрованы с использованием этого публичного ключа, шифрование происходит на вашем конце связи. Зашифрованные данные окажутся пустым набор слов, если будут перехвачены в процессе передачи. Когда данные вашей карты прибывают на другой конец, закрытый ключ — созданный из Р1 и Р2 — используется для расшифровки.
Это работает, так как очень сложно найти простые числа, из которых было получено составное, когда речь идет о больших числах. Любому хакеру понадобится 1000 лет компьютерного времени, чтобы взломать код и найти первоначальные простые числа. Именно потому, что так сложно взломать современный шифр, правительства скорее действительно предпочтут, чтобы разработчики встраивали «бэкдор» в свои системы, что позволяет им порой следить за тем, что делают люди.