В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа Прежде чем переходить к доказательству теоремы Евклида, приведем еще одну простую лемму. Лемма 2. Пусть n — положительное число, большее единицы. Пусть d — наименьший делитель числа n , больший единицы. Тогда d — простое число. Доказательство. Прежде всего следует убедиться в том, что определение числа d корректно. (Если существует такое положительное число n , у кото- рого нет наименьшего делителя, то определение d дано некорректно и лемма теряет смысл.) Мы знаем, что n является делителем n и n > 1 . Таким обра- зом, у числа n должен существовать и наименьший делитель, больший 1. Чтобы доказать, что d является простым числом, используем стандарт- ный математический прием — reductio ad absurdum , или доказательство от противного (proof by contradiction) . Чтобы доказать утверждение X , предпо- ложим, что оно неверно, и покажем, что это предположение в конце концов приводит к противоречию. Если предположение о том, что X неверно, при- водит к противоречию, это, очевидно, означает, что X верно. В нашем случае предположим, что d не является простым числом. Тогда у него должен быть делитель e , такой, что 1 < e < d . Но мы знаем из лем- мы 1, что если e | d и d | n , то e | n , поэтому e является делителем n и e < d . Но это противоречит тому, что d является наименьшим делителем n . Поскольку мы пришли к противоречию, наше предположение должно быть неверным, а значит, d является простым числом. ¤ Пусть вас не беспокоит несколько запутанный метод доказательства — к нему нужно привыкнуть. Теперь можно доказать, что количество простых чисел бесконечно. Теорема 1 (Евклида). Существует бесконечное количество простых чисел. Доказательство. Еще раз воспользуемся доказательством от противного. Предположим, что количество простых чисел конечно, а значит, их можно записать в виде конечного списка. Обозначим эти числа как p 1 , p 2 , p 3 , . . . ., p k , где k — количество простых чисел. Введем число n := p 1 p 2 p 3 . . . p k + 1 (про- изведение всех простых чисел плюс 1). Возьмем наименьший делитель числа n , больший единицы, и снова обо- значим его как d . Мы знаем, что d — это простое число (согласно лемме 2) и d | n . Но ни одно простое число из нашего конечного списка простых чисел не является делителем n . Действительно, все числа p i являются делителями числа ( n − 1) , а n при делении на любое из этих чисел дает остаток 1. Мы получили, что d является простым числом, но его нет в списке всех простых чисел. Это противоречит тому, что список p 1 , p 2 , p 3 , . . . , p k содержит все суще- ствующие простые числа, а значит, наше предположение о конечности этого 11.2. Генерация малых простых чисел 211 списка неверно. Таким образом, существует бесконечное количество простых чисел. ¤ Примерно такое доказательство и было дано Евклидом более 2000 лет назад. На протяжении многих веков было получено множество результатов, ка- сающихся распределения простых чисел. Что интересно, ученые так и не вы- вели универсальной формулы того, как найти все простые числа из конкрет- ного интервала, поскольку они располагаются в случайном порядке. Многие простые гипотезы так и не были доказаны. Например, гипотеза Гольдбаха утверждает, что каждое четное число, большее 2, является суммой двух про- стых чисел. Это утверждение легко проверить с помощью компьютера для относительно малых четных чисел, но математики все еще не знают, является ли это утверждение верным для всех четных чисел. Для общего развития нелишне ознакомиться и с фундаментальной тео- ремой арифметики : любое целое число, большее единицы, может быть пред- ставлено в виде произведения простых чисел, и такое представление является однозначным (если не учитывать порядок, в котором записываются эти про- стые числа). Например: 15 = 3 · 5 , 255 = 3 · 5 · 17 , а 60 = 2 · 2 · 3 · 5 . Мы не будем приводить доказательство этой теоремы в данной книге. Интересующиеся могут найти его в любом учебнике по теории чисел. 11.2 Генерация малых простых чисел Иногда под рукой полезно иметь список малых простых чисел. Для по- лучения последних воспользуемся так называемым “решетом Эратосфена”; этот алгоритм генерации малых простых чисел все еще считается лучшим. функция SmallPrimeList вход: n Максимально возможное значение простого числа. Должно удовлетворять условию 2 ≤ n ≤ 2 20 . выход: P Список всех простых чисел ≤ n . Ограничим значение n . Если оно слишком большое, нам не хватит памяти. assert 2 ≤ n ≤ 2 20 Инициализируем список флажков. Каждому из них будет присвоено значение 1. ( b 2 , b 3 , . . . , b n ) ← (1 , 1 , . . . , 1) i ← 2 while i 2 ≤ n do |