В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа Мы нашли простое число i . Пометим все следующие числа, крат- ные i , как составные. for j ∈ 2 i, 3 i, 4 i, . . . , b n/i c i do b j ← 0 od Поищем следующее простое число в нашем списке. Можно пока- зать, что этот цикл никогда не приведет к условию i > n , по достижении которого функция выполняла бы доступ к несуще- ствующему b i . repeat i ← i + 1 until b i = 1 od Теперь все простые числа помечены флажками 1. Соберем их в список. P ← [ ] for k ∈ 2 , 3 , 4 , . . . , n do if b k = 1 then P ← P k k fi od return P В основе этого алгоритма лежит очень простая идея. Каждое составное число c делится на простое число, меньшее c . Каждому из чисел от 2 до n ставится в соответствие флажок, который указывает, может ли данное чис- ло быть простым. Сначала все числа помечаются как потенциально простые. Для этого их флажки устанавливаются равными 1. Переменной i присваива- ется значение первого простого числа, т.е. 2. Разумеется, ни одно из чисел, кратных 2, не может быть простым, поэтому мы помечаем числа 2 i, 3 i, 4 i и т.д. как составные, изменяя их флажки на 0. Затем увеличиваем i , пока не доберемся до следующего кандидата на звание простого числа. Отметим, что этот “кандидат” не делится ни на одно из простых чисел, меньших его самого, — в противном случае он был бы уже помечен как составное число. Следовательно, новое значение i является простым числом. Аналогичным об- разом будем помечать составные числа и искать новое простое число, пока i 2 не станет б´ольшим, чем n . Очевидно, в результате применения данного алгоритма ни одно простое число не будет ошибочно помечено как составное, поскольку это делается лишь тогда, когда найден его делитель. (Цикл, который помечает числа как составные, последовательно перебирает значения 2 i, 3 i, . . . . Каждое из этих чисел имеет множитель i , а потому не может считаться простым.) 11.3. Арифметика по модулю простого числа 213 Почему можно остановиться, когда i 2 > n ? Предположим, число k яв- ляется составным. Пусть p — его наименьший делитель, больший едини- цы. Мы уже знаем, что p — это простое число (согласно лемме 2). Пусть q := k/p . Можно утверждать, что p ≤ q ; в противном случае q было бы делителем k , меньшим p , что противоречит определению p . Теперь пока- жем, что p ≤ √ k . Если бы p было больше чем √ k , мы бы получили, что k = p · q > √ k · q ≥ √ k · p > √ k · √ k = k . Из этого неравенства следует, что k > k , а это явное противоречие. Таким образом, p ≤ √ k . Мы показали, что любое составное число k делится на простое число, которое меньше или равно √ k . Из этого следует, что любое составное число ≤ n обязательно делится на простое число ≤ √ n . Если i 2 > n , то i > √ n . Но мы уже пометили все числа, кратные каким-либо простым числам, меньшим i , как составные, поэтому больше составных чисел в списке быть не должно. Оставшиеся числа списка, помеченные как простые, действительно являются таковыми. Последняя часть алгоритма организует все найденные простые числа в список и возвращает их как результат выполнения функции. Описанный алгоритм можно было бы несколько оптимизировать, но мы решили отказаться от оптимизации в пользу простоты понимания. При пра- вильной реализации этот алгоритм работает очень быстро. Возможно, вас интересует, зачем нам нужны малые простые числа. Ока- зывается, что их можно использовать для генерации больших простых чисел, которые нам вскоре понадобятся. 11.3 Арифметика по модулю простого числа Простые числа играют такую важную роль в криптографии прежде всего потому, что могут применяться для выполнения арифметических операций по модулю. Пусть p — простое число. Когда мы вычисляем результат арифметической операции по модулю p , то используем только числа 0 , 1 , . . . , p − 1 . Основное правило выполнения операций по модулю простого числа состоит в следую- щем: мы используем целые числа так, как обычно, но каждый раз, получая результат r , берем его значение по модулю p . Операция взятия по модулю очень проста: мы делим r на p и отбрасываем целую часть полученного ре- зультата. Остаток от деления r на p и будет искомым ответом. Например, чтобы вычислить значение 25 по модулю 7, мы делим 25 на 7, в результа- те чего получаем частное 3 и остаток 4, который и будет ответом, а значит, (25 mod 7) = 4 . Запись ( a mod b ) применяется для обозначения непосред- ственной операции взятия числа a по модулю b , но, поскольку вычисления |