Глава 4. Простые числа

В первых двух главах мы изучали некоторые свойства простых чисел, без которых много не докажешь, и два алгоритма, без которых много не вычислишь. Содержание этой главы более явно связано с нашей конечной целью — RSA-криптосистемой. В самом деле, для уверенности в безопасности реализации RSA мы должны уметь подбирать большие простые числа: по два для каждого пользователя. В настоящей главе мы приступаем к решению этой задачи. Сначала рассмотрим простые числа, получающиеся из полиномиальных, экспоненциальных и праймориальных формул. Важным следствием изучения праймориальной формулы будет доказательство бесконечности множества простых чисел. Глава заканчивается обсуждением решета Эратосфена — старейшего из известных методов нахождения простых чисел и прародителя всех современных решет.

§ 4.1. Полиномиальная формула

Представление большинства людей о «формуле простых чисел» можно было бы выразить в следующем определении. Функция называется формулой простых чисел, если

простое число для каждого Как мы увидим, это определение слишком амбициозно. Вместо «формулы простых чисел» мы будем искать функции, среди значений которых часто встречаются простые числа. Поскольку многочлен — простейшая из возможных функций, стоит начать с вопроса: существует ли полиномиальная формула простых чисел?

Как следует из определения, данного выше, многочлен

с целыми коэффициентами во является формулой простых чисел, если число простое для каждого положительного целого Поэкспериментируем с многочленом Начнем с вычисления для нескольких натуральных значений переменной х. Результат представлен в следующей таблице.

(см. скан)

Заметим, что если х нечетно, то четно. Таким образом, всегда четное, а значит и составное число для нечетных значений х (за исключением так как Значит, если простое, то х обязательно четное. Следовательно, если бы числа были простыми при каждом четном х, то многочлен был бы формулой простых чисел. К сожалению, это не так; например,

составное число. Итак, многочлен не дает формулу простых чисел в смысле данного выше определения. Конечно, это только один пример, и мы могли бы надеяться, что нам не повезло с выбором многочлена. Но следующий результат показывает, что дело не в этом.

Теорема. Для данного многочлена существует бесконечно много положительных целых чисел при которых число составное.

Мы докажем эту теорему только для многочленов степени 2. Общий случай доказывается аналогично, только формулы будут более громоздкими, и усилия, затрачиваемые для их понимания, могут легко затмить ключевые идеи.

Пусть с — многочлен с целыми коэффициентами Мы можем предполагать, что Это означает, что положителен для достаточно больших значений переменной х. Если составное число для каждого натурального то доказывать нечего. Заметим, что такое на самом деле случается; например, если Таким образом, мы можем предполагать: существует такое натуральное число что простое.

Пусть произвольное натуральное число. Вычислим значение Возникает резонный вопрос: откуда появилось Наилучший ответ на него заключен в выкладках, приведенных ниже. Мы хотим найти

Раскрывая квадрат и собирая вместе члены, содержащие получаем

Заметим, что выражение в первой скобке равно так что

Формула (1.1) склоняет нас к предположению о разложимости числа Действительно, оно равно произведению на натуральное число, что означает окончание доказательства. К сожалению, в этом рассуждении есть ошибка. Число будет простым только в том случае, если выражение в скобках в правой части формулы (1.1) не равно 1. Поэтому нам нужно найти такое значение при котором

Последнее неравенство эквивалентно

Поскольку число положительно (по предположению), требуемое неравенство выполнено только если

Заметим, что может быть положительным числом в том случае, если b отрицательно и меньше, чем

Что же мы доказали? Мы показали, что если многочлен с целыми коэффициентами и положительным а, и число простое, то является составным для всех . В частности, найдется бесконечно много натуральных значений х, при которых составное число.

Как мы уже отмечали, похожее доказательство работает и для многочленов произвольной фиксированной степени. Конечно, вычисление значения не такое компактное, но главная трудность связана с определением нижней границы для Поскольку у нас был квадратный многочлен, эта граница легко получалась из линейного неравенства. В общей ситуации, когда мы работаем с многочленом степени нижняя граница для определяется из неравенства, содержащего

многочлен степени Эта трудность проиллюстрирована в упражнении 1, где рассматривается случай кубического многочлена. Если же степень многочлена больше 3, то простой формулы, выражающей нижнюю границу для нет. В такой ситуации мы были бы рады показать, что нижняя граница в принципе существует, даже если не сможем выписать для нее точную формулу. Доказательство существования нижней границы требует применения элементов математического анализа, и мы не будем его приводить. Доказательство этой теоремы можно найти в [41] ([Д. 14]).

Доказанная теорема означает, что ответ на вопрос, сформулированный в начале параграфа, отрицателен. Однако мы рассматривали только многочлены от одной переменной. Неожиданным образом существуют многочлены от нескольких переменных, все положительные значения которых — простые числа. Проблема в том, что эти многочлены во многом неопределенны, так что их использование для нахождения простых чисел не очень практично. Примеры смотри в [41] ([Д. 14]).