Построение простых чисел

Для генерации близкого к п простого числа:

• 1) сгенерируйте случайное ?-битовое число т, где к ~ log2n;
• 2) старший и младший биты положите равными единице, старший бит гарантирует требуемую величину простого числа, младший — его нечетность;
• 3) убедитесь в том, что т не делится па 3, 5 и т. д. до некоторого заданного простого числа, это отбракует заметную долю (более 50%) составных чисел, проверяемых на простоту;
• 4) если выбранный тест показал, что число т составное, то выберите следующее число и примените выбранный тест, в частности, если выбирать числа вида т + 2i, где /‘ = 1,2,то для построения простого числа потребуется применить тест в среднем не более In п раз.

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

Теорема 16.3. Пусть q — нечетное простое, т — четное, тогда нечетное число р = qm + 1 — простое, если р < (2q + I)² и выполнены следующие условия: Ъ^т = 1 (modp), 2^т Ф 1 (modр).

М Пусть каноническое разложение числа р в произведение степеней.

_v k к 1

простых нечетных делителей р_х, …, p_s имеет вид р = р_х…р/_У и а есть порядок числа 2 по modр. Тогда d| (р — 1) по первому условию, d не делит (р — 1) / q по второму условию и d | (р (р) по теореме Эйлера. В силу простоты q d, и значит, q | ср (р), где ф (р) = -p^kfp — 1)…(р₄ — 1);

Если q е {р_х, …, pj, то р = qn при некотором натуральном п в соответствии с каноническим разложением числа р. Тогда по условию qn = qm + 1, отсюда q 1, т. е. имеем противоречие. Следовательно, q? [р_х, …, p_s}, значит, q делит один из множителей (р_х — 1), …, (p_s — 1). Пусть для определенности q (j) — 1), тогда р_х = qn + 1 при некотором четном п. Отсюда qm+ 1 = р=рр'= (qn + 1) г при некотором нечетном г. Следовательно, г- 1 = = q (m — nr), и наконец, р = (qn -г 1 )(ql + 1) при некоторых четных п и / = = т — пг, где п > 2 и / > 0.

Если р составное, то / > 2, так как число qn¹ + 1 = р_х — простое. Отсюда р > (2q + I)², что противоречит условию. Значит, / = 0 и р простое. ?

Алгоритм генерации простых чисел построен по итеративному принципу и позволяет получать простые числа с длиной двоичной записи не менее 17 битов.

Пусть требуется построить ?-битовое простое число. Тогда построим убывающую последовательность чисел ?₀, t_x,…, t_s__u t_s, где t₀ = t, t_i+x = L/ 2_|, i = 0, 1, …, 5−1, t_s__x > 17 > t_s. Алгоритм выполняет 5+1 шаг. На 0-м шаге методом пробных делений строится простое число р₀ с длиной двоичной записи t_s. На г-м шаге с использованием теоремы 16.2 строится простое число Pi с длиной двоичной записи t_s__t, i = 1,…, 5.

Опишем i-й шаг, 1 < i < s. Пусть имеется простое число pi__x с длиной двоичной записи t_s__hX, тогда строим число q с длиной двоичной записи t_{s ;} вида q = Pi__xm + 1, где т — четное число, полученное с помощью датчика случайных чисел. Далее в соответствии с теоремой проверяем простоту числа q, а именно два условия: 2<�Н = 1 (modg) и 2^т * 1 (mod^).

Если выполнены оба условия, то р_х — q — простое число. Если хотя бы одно из условий не выполнено, то число q считаем составным, строим число q' = Pi__x(m + 2) + 1, проверяем простоту q' и т. д. до получения простого числа Pj в ряду q, q',…