Решето Эратосфена

Пробное деление

ПРОВЕРКА НА ПРОСТОТУ

Простые числа необходимы для большинства криптографических систем с открытыми ключами.

Теоретический материал к вопросу построения больших простых чисел можно найти в [7] и [11]. Здесь будут сформулированы только некоторые практические

подходы к формированию больших простых чисел. Для генерации больших простых чисел могут быть использованы следующие два подхода:

· формируются случайные числа заданного порядка, и при помощи существующих тестов

проверяется, являются ли они простыми.

· по определенному алгоритму генерируются простые числа, и при помощи определенных тестов производится проверка чисел на простоту.

Сначала рассмотрим те тесты, которые используются при реализации первого подхода

формирования простого числа.

Один из самых простых способов проверки числа p на простоту состоит в последовательном делении числа p на все нечетные числа, которые содержатся в

интервале [2, p ]. Если в процессе деления получим целый результат, то число p – составное. Если же при переборе всех нечетных чисел из интервала [2, p ]

разделить число p на эти числа нацело нельзя, то число p – простое. Данный метод называется пробным делением. Этот метод трудоемок по числу арифметических операций, и он используется в основном для проверки небольших простых чисел.

Если мы хотим составить таблицу всех простых чисел среди чисел

2, 3,…, N, то надо последовательно вычеркнуть все числа, которые делятся

· на 2, кроме 2;

· на 3, кроме 3;

· на 5 кроме 5;

· на следующее число, которое не вычеркнуто,

кроме этого числа;

и т. д.В итоге среди чисел от 1 до N останутся лишь простые числа. Для реализации метода нужен большой объем памяти ЭВМ, однако для составления таблиц простых чисел он является наилучшим [11]. Более того, разрабатываются специальные процессоры, на которых операции «просеивания» выполняются очень эффективно [7].

Замечание. Пробное деление и решето Эратосфена можно применять при решении задачи разложения целого числа на множители.

Дата добавления: 2013-12-13