close

Вход

Забыли?

вход по аккаунту

?

Высокопроизводительный алгоритм генерации простых чисел в произвольном диапазоне с применением кольцевой факторизации.

код для вставкиСкачать
обзор
МИНАЕВ1 Владимир Александрович,
доктор технических наук, профессор
ВАСИЛЬЕВ2 Николай Петрович,
кандидат технических наук, доцент
ЛУКЬЯНОВ3 Вениамин Владимирович
НИКОНОВ4 Семен Андреевич
НИКЕРОВ5 Дмитрий Викторович
ВЫСОКОПРОИЗВОДИТЕЛЬНЫЙ
АЛГОРИТМ ГЕНЕРАЦИИ ПРОСТЫХ
ЧИСЕЛ В ПРОИЗВОЛЬНОМ
ДИАПАЗОНЕ С ПРИМЕНЕНИЕМ
КОЛЬЦЕВОЙ ФАКТОРИЗАЦИИ
Даются определения порядка индексного алгоритма и паттерна размещения составных чисел. Рассмотрены индексные
алгоритмы вычисления простых чисел в сочетании с методом кольцевой факторизации для предварительного отбора составных чисел. Производится сравнение индексных алгоритмов различного порядка.
Ключевые слова: простые числа, высокоскоростной алгоритм генерации, кольцевая факторизация, индексный алгоритм.
The definitions of the index algorithm order and pattern layouts of composite numbers are given. The Primes index calculation
algorithms in combination with the method of wheel factorization for pre-selection of composite numbers are considered. Comparison
of different order index algorithms is made.
Keywords: primes, high speed generation algorithm, wheel factorization, index algorithm.
П
ростые числа используются для
шифрования информации. Так,
например, известный алгоритм шифрования RSA использует два простых
числа для формирования открытого
ключа. При этом, чтобы расшифровать содержимое конфиденциального
письма, надо провести процесс факторизации некоторого очень большого
числа, т.е. разложить его на сомножители, которые являются простыми числами.
Решение задачи факторизации при
этом – исключительно вычислительно-емкая процедура, так как помимо
нахождения сомножителей, каждый
из них необходимо проверить на простоту.
1
3
Для генерации простых чисел методом
просеивания (исключение составных
чисел, т.н. «решето») применяются решета Эратосфена, Аткина и Сундарама
в разных модификациях и производные от этих алгоритмов.
В 2011 г. опубликована работа В.А. Минаева [1], в которой описывается алгоритм, являющийся основой для создания новых высокопроизводительных
алгоритмов, превосходящих по скорости вычисления простых чисел все
предыдущие. Алгоритм основывается
на теореме о полном множестве простых чисел.
Автор доказал, что полное множество
простых чисел вида {6 k+1}, k = 1,2,3…
(по определению В.А. Минаева – плюс
– РосНОУ, профессор; 2 – НИЯУ МИФИ, доцент;
– НИЯУ МИФИ, аспирант; 4,5 – РосНОУ, аспирант.
простые числа) формируется путем
вычитания из общего множества чисел
{+qi} вида {6 k+1}; k = 1,2,3…, определенного как {+S}, подмножества составных чисел
, определяемых с помощью уравнений:
(1)
где m = 0,1,2…; i = 1,2,3…
А полное множество простых чисел
вида {6∙k-1}; k = 1,2,3…(минус простые
числа) – путем вычитания из общего множества чисел {–qi} вида {6 k-1};
k = 1,2,3…, определенного как {‒S}, подмножества составных чисел
, вычисляемых из соотношений:
49
Спецтехника и связь № 5 2013
(2)
где m = 0,1,2…; i = 1,2,3…
Смысл алгоритма, предложенного в
[1], связан не с прямым вычислением
простых чисел, а с нахождением полного множества составных того же вида
{6 k ± 1}; k = 1,2,3…., и последующим
вычитанием соответствующих множеств.
В настоящей статье описываются новые индексные алгоритмы генерации
простых чисел, на сегодняшний день
самые быстрые, основой разработки
которых является теорема, доказанная
в [1], и правило знаков, сформулированное там же.
ндексный алгоритм
И
второго порядка для
генерации простых чисел
Эти составные числа адресуются во
множестве –S или +S следующими четырьмя индексами:
k1 = (–qk + k),
–
k2 = (+qk – k),
–
k3 = (–qk – k),
+
+
k4 = ( qk + k)
+
(10)
или в векторном виде (вектор включает по две компоненты):
_
_
k = (±qk + k), –k = (±qk – k),
+
(11)
где k = 1,2,3,….
Приведем примеры адресации (табл.
1, 2), используя формулы (5) – (11), при
n = 1.
Отметим, что для ускорения поиска
простых чисел на определенном отрезке натурального ряда для предварительного отбора составных чисел
в работе [2] реализован и исследован
индексный алгоритм, построенный с
использованием кольцевой факторизации для 3# = 6 (примориал простых
чисел 2x3). Она позволила на предварительном этапе отсеять значительную часть составных чисел – 66,66…%.
На рис. 1 приведено графическое изображение кольцевой факторизации
для 3# и 5# [3 – 4].
ндексные зависимости
И
формирования составных
чисел
Согласно правилу знаков [1], любые
составные числа из множеств –S и
+
S представляются в виде произведений:
c(–qk, +qn) = –qk × +qn,
c(+qk, –qn) = +qk × –qn,
(3)
c(–qk, –qn) = –qk × –qn,
c(+qk, +qn) = +qk × +qn,
(4)
–
–
+
+
где k, n = 1,2,3,….
Подставляя соответствующие значения
для ±qk и ±qn, получим соотношения:
c(–qk, +qn) = 6 × (n ×–qk + k) – 1,
c(+qk, –qn) = 6 × (n ×+qk – k) – 1,
+ –
c( qk, –qn) = 6 × (n ×–qk – k) + 1,
+ +
c( qk, +qn) = 6 × (n ×+qk + k) + 1.
–
–
(5)
(6)
(7)
(8)
Из (5) – (8) следует, что всевозможные
сочетания n и k (k, n = 1,2,3,…) позволяют получить весь набор составных
чисел вида {6×i ± 1}, i = 1,2,3,…; в любом заданном интервале.
Так, например, при n = 1 выражение,
стоящее в скобках формул (5) – (8),
описывает получение следующего набора составных чисел:
Рис. 1. Графическое изображение кольцевой факторизации для 3# и 5#
Таблица 1. Адресация составных чисел с использованием
+
k-индексной зависимости
k
1
1
4
8
13
127
5 (множество –S)
7 (множество +S)
25 (множество +S)
47 (множество –S)
79 (множество +S)
761 (множество –S)
+
k1, +k4
5+1=6
7+1=8
25+4=29
47+8=55
13+79=92
127+761=888
qk
±
k2, –k3
–
–
–
(9)
c( qk, 5) = 6×( qk – k) + 1,
c(+qk, 7) = 6×(+qk + k) + 1.
+
+
50
–
–
c ( ±qk1 +k1,)
c ( ±qk1 +k4,)
±
±
35 (множество –S)
49 (множество +S)
175 (множество +S)
329 (множество +S)
553 (множество +S)
5327 (множество –S)
Таблица 2. Адресация составных чисел с использованием
–
k-индексной зависимости
k
c(–qk, 7) = 6×(–qk + k) – 1,
c(+qk, 5) = 6×(+qk – k) – 1,
qk
±
1
1
4
8
13
127
5 (во множестве –S)
7 (во множестве +S)
25 (во множестве +S)
47 (во множестве –S)
79 (во множестве +S)
761 (во множестве –S)
5 ‒ 1=4
7 ‒ 1=6
25 ‒ 4=21
47 ‒ 8=39
79 ‒ 13=66
761 ‒ 127=634
c ( ±qk1 –k2,)
c ( ±qk1 –k3,)
±
±
25 (во множестве +S)
35 (во множестве ‒S)
125 (во множестве ‒S)
235 (во множестве +S)
395 (во множестве ‒S)
3805 (во множестве +S)
МЕТОДЫ
обзор
Нужно отметить, что для 7# (примориал простых чисел равен 2x3x5x7) –
отсеивается больше 77% составных чисел, а для 251# – около 90%.
Учитывая важность предварительного просеивания, в настоящей работе
обосновываются и исследуются индексные алгоритмы, построенные с применением кольцевой факторизации
для примориалов, превышающих значение 6.
Введем понятие порядок индексного алгоритма, под которым подразумевается количество первых простых чисел,
использованных при соответствующей
кольцевой факторизации. Например,
для 3# = 2 × 3 = 6 порядок индексного
алгоритма равен 2, а для 5# = 2 × 3 × 5
= 30 – порядок равен 3.
Число k = 1,2,3…, участвующее в формировании пары чисел, каждое из которых принадлежит множеству –S или
+
S, определим как k-индекс.
k-индекс адресует числа множеств –S и
+
S следующим образом: одному его значению одновременно соответствуют по
одному элементу из каждого множества; при этом соответствие между k-индексом и элементом в каждом из множеств – взаимно однозначное.
Множества –S и +S будем называть
симметричными по отношению друг к
другу, поскольку их элементы формируются симметрично относительно одного и того же k-индекса с разностью 2,
т.е. для симметричных элементов множеств –S и +S разность +qk – –qk = 2.
В связи с тем, что каждое составное число есть член какой-либо арифметической прогрессии [5], был поставлен вопрос: можно ли адресовать все составные числа во множествах –S и +S через
k-индексы и первые члены арифметических прогрессий, порождающих их
подмножества?
Решение данного вопроса имеет существенную вычислительную и практическую ценность, так как определение
массива индексов, соответствующих
массиву составных чисел, позволяет
избежать выделения огромной памяти
под хранение последних в результате
решений уравнений (1), (2).
Нужно отметить, что существующие
до сегодняшнего дня методы получения очередного простого числа учитывали все найденные предыдущие
простые и составные числа, в то время
как индексный подход позволяет без
Таблица 3. Примеры адресации составных чисел через их индексы
qk
k
5
(–S)
1
19
(+S)
3
25
(+S)
4
n
+
kn
±
c(+kn,)
1
2
3
4
5
1
2
3
4
1
2
6
11
16
21
26
22
41
60
79
29
54
35 (–S)
65 (–S)
95 (–S)
125 (–S)
155 (–S)
133 (+S)
247 (+S)
361 (+S)
475 (+S)
175 (+S)
325 (+S)
kn
c(–kn,)
–
±
4
9
14
19
24
16
35
54
71
21
46
25 (+S)
55 (+S)
85 (+S)
115 (+S)
145 (+S)
95 (–S)
209 (–S)
323 (–S)
437 (–S)
125 (–S)
275 (–S)
Таблица 4. Скорость вычислений и требуемая для работы
алгоритма память на различных интервалах
Диапазон
5÷1∙109
5÷2∙109
5÷3∙109
5÷4∙109
5÷5∙109
20
10 ÷1020+1∙109
1020÷1020+2∙109
1020÷1020+3∙109
1020÷1020+4∙109
1020÷1020+5∙109
Время, с
22
48
74
101
164
105
162
222
287
360
Память, МГб
317
635
953
1271
1589
317
635
953
1271
1589
Рис. 2. Зависимость производительности индексного алгоритма
от длины интервала в диапазоне 5÷5∙109.
учета «предыстории» вычислять простые и составные числа в заданном
произвольном интервале на множестве натуральных чисел при задании его
нижней и верхней границы.
Предположим, требуется получить
простые числа в диапазоне от одного
миллиарда до двух. Для ранее известных методов приходилось задавать
только верхнюю границу, т.е. 2 млрд,
выполнять ресурсоемкие расчеты, а затем отсекать ненужные значения простых и составных чисел. В нашем же
случае задаются обе границы, и расчет
51
Спецтехника и связь № 5 2013
Используя формулы (12), составим следующую таблицу примеров (табл. 3).
Анализируя столбцы табл. 3, можно
заметить, что +kn адресуют все составные числа в том множестве (–S или +S)
которому принадлежит ±qk, а –kn – в
симметричном множестве. Причем
адресуемые составные числа кратны
соответствующему ±qk. Это дает возможность, определив граничные условия на ±kn и соответственно максимально необходимые для этого qk, n и
k, исходя из границ интервала, найти
все простые числа.
ценка производительности
О
работы индексного
алгоритма второго порядка
Рис. 3. Зависимость производительности индексного алгоритма
от длины интервала в диапазоне 1020÷1020+5∙109.
Индексный алгоритм второго порядка
был реализован на C++ и протестирован на скорость вычислений и занимаемую при работе память. Результаты
тестов отражены в табл. 4.
Корректность работы алгоритма проверена с использованием источников для
20-разрядных и менее чисел [6 – 8] в
пределах первых 50 млн простых чисел.
Интересно отметить, что на начальном интервале расчета 5÷5∙109 время
вычислений экспоненциально зависит
от величины интервала (рис. 2) – квадрат коэффициента корреляции равен
0,973, а при очень больших значениях n
можно использовать линейное приближение (рис. 3), где квадрат коэффициента корреляции составляет 0,9975.
равнение производительС
ности алгоритмов
Рис. 4. Сравнение скоростей работы алгоритмов вычисления всех простых
чисел на интервале от 1 до n
ведется только в их пределах для требуемых значений простых и составных.
Для произвольного n обобщим выражения (11) в виде уравнений:
_
k n = n × ±qk + k,
_
‒
k n = n × ±qk – k,
+
(12)
где k,n = 1,2,3,…
Члены этих арифметических прогрессий – это k-индексы, адресующие элементы множеств –S или +S; При этом
52
qk может быть как простым, так и
составным числом. Члены прогрессии
адресуют составные числа, некоторые
из них могут адресоваться и другой kиндексной прогрессией, формируя «дубли».
В работе [5] отмечено, что все «дубли»
игнорируются при вычитании составных вида {6 k ± 1}, k = 1,2,3…, из объединения множеств +S и –S, в результате остаются только простые числа вида
{6 k ± 1}, k = 1,2,3….
±
Проведем сравнительные тесты различных алгоритмов вычисления простых
чисел, работающих в одинаковых условиях: каждый из них был реализован
на языке C++, запускался на одном и
том же компьютере, на вход подавались
одни и те же интервалы от 1 до n и замерялось время, за которое алгоритм
выделит все простые числа на данном
интервале. Результаты измерений представлены на рис. 4.
На рис. 5 по оси ординат отложены
верхние пределы интервалов вычислений, т.е. n+1000 (нижние пределы
отличались от верхних на 1000). По оси
абсцисс – время, за которое алгоритм
вычислял все простые числа на заданном интервале.
МЕТОДЫ
обзор
Предварительное просеивание с применением метода
кольцевой факторизации
в индексных алгоритмах
произвольного порядка
Рассмотрим более детально индексный алгоритм второго порядка для
нахождения простых чисел в заданном
отрезке [Nmin; Nmax], исходя из результатов работы [2]. Для этого применим
кольцевую факторизацию для 3# к отрезку [1; Nmax], введем обозначения
где k = 0,1,2, … kmax (для максимально
возможного k = kmax должно быть выполнено условие
и занесем эти данные в табл. 5.
В левом столбце таблицы приведена последовательность индексов 0, 1, 2, … kmax,
в двух других столбцах – отображения
этой последовательности во множества
вида {6k + 1} и {6k + 5}, содержащие
как простые, так и составные числа, а
также единицу.
Перейдем к следующему этапу – отсеву оставшихся после кольцевой факторизации составных чисел из множеств
{q6k+1} и {q6k+5}, где k = 0, 1, 2, … kmax.
Как показано в [2], все составные числа, кратные числам q6i+1 или q6i+5, где
i = 0, 1, 2, … imax (для максимально возможного i = imax должно быть выполнено условие
≤ Nmax), можно исключить из табл. 5, вычислив массив
их индексов с помощью соответствующих соотношений.
Для фиксированного q6i+1 последовательность
, где m = 1, 2, 3, … ,
индексирует все кратные ему составные числа во множестве {q6k+1}, а
последовательность
, где
m = 1, 2, 3, … , индексирует все кратные q6i+1 составные числа во множестве
{q6k+5} [2].
Для заданного отрезка [Nmin; Nmax] из
вышеупомянутых последовательностей
нужно выбирать те их члены, которые
индексируют числа, содержащиеся
внутри него. Пример для q6·1+1 = 7 приведен в табл. 6, в левом столбце которой отмечены индексы m· q6·1+1, где
m = 1, 2, 3, … , а во втором и третьем
столбцах отмечены кратные q6·1+1 числа,
Рис. 5. Сравнение скоростей работы алгоритмов генерации простых чисел на
интервале от n до n+1000 при различных n.
Таблица 5. Результаты кольцевой факторизации
для 3# в табличном виде
Индекс
q6k+1
q6k+5
0
1
2
3
4
…
kmax
1
7
13
19
25
…
6kmax + 1
5
11
17
23
29
…
6kmax + 5
индексируемые последовательностями
соответственно
(m·q6·1+1+ 1) = {8, 22, 29, 36, …} и
(m·q6·1+1 – 2) = {5, 19, 26, 33, …}.
Для фиксированного q6i+5, в свою очередь, уже другая последовательность
(m·q6i+5 – i), где m = 1, 2, 3, … , индексирует все кратные этому q6i+5 составные
числа во множестве {q6k+1}, а последовательность (m·q6i+5 + i – 1), где m =
1, 2, 3, … , индексирует все кратные q6i+5
составные числа во множестве {q6k+5}.
Опять же для заданного отрезка
[Nmin; Nmax] из вышеупомянутых последовательностей нужно выбирать
те их члены, которые индексируют
числа, содержащиеся внутри этого отрезка. Пример для q6·0+5= 5 приведен в
табл. 7, в левом столбце которой отмечены индексы m·q6·0+5, где m = 1, 2, 3, …
, а во втором и третьем отмечены кратные q6·0+5 числа, индексируемые последовательностями соответственно
(m·q6·0+1 – 1) = {4, 24, 29, 34, …} и
(m·q6·0+1) = {5, 25, 30, 35, …}.
Таким образом, если перебрать все
подходящие q6i+1 и q6i+5, то из заданного
отрезка [Nmin; Nmax] можно отсеять все
Таблица 6. Пример адресации
составных чисел при q6·1+1 = 7
k
q6k+1
q6k+5
0
…
5
6
7
8
…
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
…
1
…
31
37
43
49
…
115
121
127
133
139
145
151
157
163
169
175
181
187
193
199
205
211
217
…
5
…
35
41
47
53
…
119
125
131
137
143
149
155
161
167
173
179
185
191
197
203
209
215
221
…
53
Спецтехника и связь № 5 2013
Таблица 7. Пример адресации
составных чисел при q6·+5
0 =5
k
q6k+1
q6k+5
0
…
4
5
…
24
25
26
27
28
29
30
31
32
33
34
35
…
1
…
25
31
…
145
151
157
163
169
175
181
187
193
199
205
211
…
5
…
29
35
…
149
155
161
167
173
179
185
191
197
203
209
215
…
составные числа и тем самым определить в нем все простые.
ндексный алгоритм
И
произвольного порядка
Сформируем индексный алгоритм
произвольного порядка n для нахождения простых чисел в заданном отрезке
[Nmin; Nmax], обобщив изложенный алгоритм второго порядка.
Применим кольцевую факторизацию
для pn# к отрезку [1; Nmax], примем
обозначения, аналогичные принятым
выше
= pn#∙k + 1,
= pn#∙k + pn+1,
...
= pn#∙k + pn+s,
где k = 0, 1, 2, … kmax (для максимально
возможного k = kmax должно быть выполнено условие
≤ Nmax), и занесем эти данные в табл. 8:
В левом столбце табл. 8 приведена последовательность индексов 0, 1, 2, … kmax,
в других столбцах – отображения этой
последовательности в множества вида
{pn#·k + 1},
{pn#·k + pn+1},
под которым будем понимать схему
размещения кратных q чисел в строках
с индексами 0, 1, … (q – 1) табл. 8. Покажем, что этот паттерн повторяется в
строках с индексами
…
{pn#·k + pn+r},
…
{pn#·k + pn+s},
содержащие как простые, так и составные числа, а также единицу.
Использованные обозначения – p1 = 2,
p2 = 3, … pn – записанные по возрастанию простые числа, n = 1, 2, 3,…; pn# –
примориал (произведение всех простых
чисел, меньших либо равных pn); pn+1, …
pn+r, … pn+s – записанные по возрастанию числа из интервала (pn; pn#), являющиеся простыми или всевозможными
произведениями простых чисел из этого
же интервала; s — количество простых
чисел и их произведений на интервале
(pn; pn#); r = 1, 2, 3, … s.
Перейдем к следующему этапу – отсеву оставшихся после кольцевой факторизации составных чисел из множеств
{
}, {
}, … {
}, … {
},
где k = 0, 1, 2, … kmax. Кратные числу q
составные числа можно исключить, вычислив их индексы, для чего обобщим
полученные для индексного алгоритма
второго порядка соотношения на произвольный порядок. При этом
q ∈{Q} = {pn#·i + 1} ∪ {pn#·i + pn+1} ∪ …
∪ {pn#·i + pn+r} ∪ … ∪ {pn#·i + pn+s},
где i = 0, 1, 2, … imax (для максимально
возможного i = imax должно быть выполнено условие (
)2 ≤ Nmax), r = 1, 2, 3,
… s. Чтобы вычислить эти индексы, введем для фиксированного q ∈ {Q} числа
tqj , где j = 1, 2, … (s + 1). Числа tqj определяются в диапазоне [0; q – 1] и принимают значения из первого столбца
табл. 8 соответственно тому, на какой
строке в (j + 1)-ом столбце находится
кратное q число. Это означает, что для
каждого q определяется свой паттерн
tqj, q ∈ {Q},
(13)
m·q, … , (m + 1)·q – 1,
где m=0, 1, 2, … . Число, стоящее в
(j + 1)-ом столбце табл. 8 на строке
с индексом
m∙q + tqj,
(14)
при j > 1 равно
pn#∙(m∙q + tqj) + pn+j–1 = pn#∙tqj +
+ pn+j–1 + pn#∙m∙q
(15)
или (при j = 1)
pn#∙(m∙q + tqj) + 1 = pn#∙tqj+ 1 +
+ pn#∙m∙q,
(16)
а значит, отличается от стоящего в
(j+1)-ом столбце табл. 8 на tqj-й строке
числа (при j >1 – pn#∙tqj + pn+j–1, или
при j = 1 – pn#∙tqj + 1 по определению
кратного q) на pn#∙m∙q и, следовательно, делится на q.
Очевидно, что для определенного отрезка [Nmin; Nmax] из последовательностей (14) нужно выбирать те их члены,
которые индексируют числа, содержащиеся внутри этого отрезка в табл. 8.
Рассмотрим в качестве примера отсеивание кратных q30+7
·0 чисел при выполнении индексного алгоритма третьего
порядка. Третий порядок индексного
алгоритма означает, что нужно взять 3
первых простых числа и перемножить
их – 2 × 3 × 5 = 30, после чего составить
таблицу кольцевой факторизации, содержащую все простые числа и состоящую из членов прогрессий {30k + 1},
{30k + 7}, {30k + 11}, {30k + 13},
{30k + 17}, {30k + 19}, {30k + 23},
{30k + 29}. Для отсеивания всех кратных 7 чисел нужно в диапазоне индексов [0; 6] определить паттерн (13) для
числа 7:
Таблица 8. Результаты кольцевой факторизации для pn# в табличном виде
Индекс
54
…
…
0
1
pn+1
…
pn+r
…
pn+s
1
pn#·1 + 1
pn#·1 + pn+1
…
pn#·1 + pn+r
…
pn#·1 + pn+s
…
…
…
…
…
…
…
kmax
pn#·kmax + 1
pn#·kmax + pn+1
…
pn#·kmax + pn+r
…
pn#·kmax + pn+s
МЕТОДЫ
обзор
Таблица 9. Пример адресации составных чисел при q = q30+7
·0 = 7
k
30k + 1
30k + 7
30k + 11
30k + 13
30k + 17
30k + 19
30k + 23
30k + 29
0
1
2
3
4
5
6
1
31
61
91
121
151
181
7
37
67
97
127
157
187
11
41
71
101
131
161
191
13
43
73
103
133
163
193
17
47
77
107
137
167
197
19
49
79
109
139
169
199
23
53
83
113
143
173
203
29
59
89
119
149
179
209
7
8
9
10
11
12
13
211
241
271
301
331
361
391
217
247
277
307
337
367
397
221
251
281
311
341
371
401
223
253
283
313
343
373
403
227
257
287
317
347
377
407
229
259
289
319
349
379
409
233
263
293
323
353
383
413
239
269
299
329
359
389
419
14
15
16
17
18
19
20
421
451
481
511
541
571
601
427
457
487
517
547
577
607
431
461
491
521
551
581
611
433
463
493
523
553
583
613
437
467
497
527
557
587
617
439
469
499
529
559
589
619
443
473
503
533
563
593
623
449
479
509
539
569
599
629
…
…
…
…
…
…
…
…
…
tqj = {3,0,5,4,2,2,6,3},
для j = 1, … 8, q = 7.
(17)
Далее следует во множестве диапазонов индексов {[7; 13], [14; 20], …}
исключить соответственно паттерну
(17) кратные 7 числа, которые будут
находиться по формуле (14) на тех же
местах, что и в диапазоне [0; 6]. Описанный процесс показан в табл. 9, полученной из табл. 8 при n = 3.
Таким образом, если в заданном отрезке [Nmin; Nmax] с помощью соответствующих паттернов (13) отсеять
составные числа (15) и (16), кратные
всем подходящим q (13), то в нем останутся только простые числа. Отметим,
что количество паттернов равно количеству элементов множества {Q},
которое зависит от значения Nmax.
Следовательно, на отрезках равного
размера с различным Nmax количество паттернов будет больше у отрезка с
большим Nmax. Перейдем к исследованию индексных алгоритмов различного порядка.
сследование индексных
И
алгоритмов различного
порядка
Рассмотренные индексные алгоритмы
реализованы на языке C++ с исполь-
Рис. 6. Сравнение скоростей работы индексных алгоритмов генерации
простых чисел на отрезке размером 106 (считая от значения ординаты)
зованием библиотеки GMP для работы с большими числами и проверены
на совпадение результатов генерации
с первыми 50 млн простых чисел [6
– 8]. Индексные алгоритмы второго,
третьего и четвертого порядков исследовались на время работы при различных отрезках и различных нижних
границах на компьютере с процессором Intel Core i3 2,93 ГГц. Увеличив-
55
Спецтехника и связь № 5 2013
Рис. 7. Сравнение скоростей работы индексных алгоритмов генерации
простых чисел на отрезке размером 5·107 (считая от значения ординаты)
миллионного отрезка индексный алгоритм второго порядка работает быстрее
остальных, а четвертого – существенно отстает. Однако уже на отрезке 5·107
(рис. 7) видно, что индексный алгоритм
третьего порядка по времени работы
практически сравнялся по скорости с
алгоритмом второго порядка, а на больших отрезках – стал работать быстрее.
Аналогичная ситуация повторяется на
отрезке 109 (рис. 8): индексный алгоритм четвертого порядка по времени
работы сравнялся с индексным алгоритмом третьего порядка, а на отрезке
4·109 (рис. 9) – стал функционировать
быстрее.
Таким образом, для бóльших отрезков индексные алгоритмы генерации
простых чисел большего порядка работают лучше, чем для меньших. Напротив, для меньших отрезков индексные алгоритмы генерации простых
чисел меньшего порядка работают
лучше, чем для бóльших. Происходит
это потому, что для большего отрезка
увеличивается время определения соответствующих ему паттернов, согласно которым отсеиваются составные
числа. Для меньшего отрезка наблюдается обратная ситуация – паттерны
находятся быстрее.
Выводы
Рис. 8. Сравнение скоростей работы индексных алгоритмов генерации
простых чисел на отрезке размером 109 (считая от значения ординаты)
шееся время работы по сравнению с
[2] обусловлено 64-битным представлением чисел в упомянутой статье.
Использование представления mpz_t
из GMP дало возможность судить о
56
поведении алгоритмов за пределом
64-битного представления.
На рис. 6 – 9 представлены результаты
работы алгоритмов для соответствующих отрезков. Из рис. 6 видно, что для
1 Развитие положений работ [1 – 2]
связано с реализацией индексного принципа нахождения составных чисел, заключающегося в вычислении не самих
чисел, а массива соответствующих им
индексов. Такой подход способен существенно увеличить производительность
алгоритмов вычисления простых чисел,
а, следовательно, скорость факторизации составных чисел, что напрямую
связано с алгоритмами шифрования
конфиденциальной информации.
2 Кроме того, индексные алгоритмы
ориентированы на решение задач:
♦♦ дальнейших исследований в области
простых чисел, в частности – оценки распределения простых чисел в
произвольном диапазоне, проверки
решения открытых математических
проблем;
♦♦ создания генератора случайных
простых чисел для криптографических приложений;
♦♦ поиска оптимальных значений простых чисел при использовании хеш-
МЕТОДЫ
обзор
Рис. 9. Сравнение скоростей работы индексных алгоритмов генерации
простых чисел на отрезке размером 4·109 (считая от значения ординаты)
таблиц в базах данных и других задач, связанных с их применением.
3 Индексные алгоритмы в их текущей реализации представляют принципиально новый подход к поиску
простых чисел. Однако требуется их
оптимизация применительно к объему
кэш-памяти используемого процессора. В то же время индексные алгоритмы с использованием кольцевой
факторизации не требовательны к
вычислительным ресурсам, поскольку
оперируют с булевым массивом. Благодаря своей многозадачной структуре
алгоритм легко модифицируется как
многопоточный с реализацией на GPU.
В частности они легко реализуемы при
параллельном вычислении, используя
кластерные вычислительные технологии NVIDIA CUDA [9–11], Open MP,
Open MPI и другие
Литература
1. М
инаев В.А. Теорема о полном множестве простых чисел. – М.: НИЯУ МИФИ, 2011. – 24 с.
2. Минаев В.А., Васильев Н.П., Лукьянов В.В., Никонов С.А., Никеров Д.В. Высокопроизводительный алгоритм генерации простых чисел в произвольном диапазоне./ Материалы XIV Международной научной конференции «Цивилизация знаний:
проблемы и смыслы образования», 2013. – М.: РосНОУ.
3. Wheel factorization – [Электронный ресурс]. URL: http://primes.utm.edu/glossary/xpage/WheelFactorization.html. (Дата
обращения: 13.06.2013).
4. Wheel factorization – [Электронный ресурс]. URL: http://en.wikipedia.org/wiki/Wheel_factorization. (Дата обращения:
18.06.2013).
5. М
инаев В.А. Простые числа: новый взгляд на закономерности формирования. – М.: Логос, 2011. – 80 с.
6. The first fifty million primes – [Электронный ресурс]. URL: http://primes.utm.edu/lists/small/millions/. (Дата обращения:
10.06.2013).
7. The Prime Pages (prime number research, records and resources) [сайт]. URL: http://primes.utm.edu/ (дата обращения
17.02.2013)
8. Простые числа [сайт]. URL: http://ru.numberempire.com/primenumbers.php (дата обращения 25.04.2013)
9. Cuda Best Practices Guide:: CUDA Toolkit Documentation [сайт]. URL: http://docs.nvidia.com/cuda/cuda-c-best-practicesguide/index.html (дата обращения 07.02.2013)
10. Б
оресков А.В. Основы работы с технологией CUDA./ Харламов А.А. – М.: ДМК Пресс, 2010. – 232 с.
11. Параллельные вычисления на GPU. Архитектура и программная модель CUDA: учеб. пособие./ Боресков А.В. и др. Предисловие.: В.А. Садовничий. – М.: Издательство Московского Университета, 2012. – 336 с.
57
1/--страниц
Пожаловаться на содержимое документа