Реализация индексных алгоритмов поиска простых чисел с помощью параллельных вычислений

1 / 9

DOI: 10.18698/0236-3933-2015-6-82-90
УДК 511.333;511.337
РЕАЛИЗАЦИЯ ИНДЕКСНЫХ АЛГОРИТМОВ ПОИСКА ПРОСТЫХ
ЧИСЕЛ С ПОМОЩЬЮ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
В.А. Минаев1, М.П. Сычев1 , С.А. Никонов 1 , Д.В. Никеров2
1МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
e-mail: ;
2Российский новый университет, Москва, Российская Федерация
e-mail:
Для реализации новых подходов к обеспечению безопасности информационных
систем предложен индексный алгоритм поиска простых чисел с использовани-
ем параллельных вычислений. Проведена оценка быстродействия алгоритма в
зависимости от мощности используемой вычислительной системы.
Ключевые слова: простые числа, составные числа, кольцевая факторизация, ин-
дексный алгоритм, параллельные вычисления.
IMPLEMENTATION OF INDEX PRIME NUMBERS
SEARCH ALGORITHMS USING PARALLEL COMPUTING
V.A. Minaev1 , M.P. Sychev1 , S.A. Nikonov1 , D.V. Nikerov2
1Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail: ;
2Russian New University, Moscow, Russian Federation
e-mail:
The article considers implementation of new approaches ensuring the information
systems security. For this purpose, index prime number search algorithms using
parallel computing is developed. The assessment of the algorithm performance
depending on computer system power is made.
Keywords: prime numbers, composite numbers, wheel factorization, index algorithm,
parallel computing.
Реализация целого ряда алгоритмов обеспечения информационной
безопасности, шифрования/дешифрования информации связана с про-
цедурой поиска и использования простых чисел. Для ускорения ука-
занной процедуры авторами в целях нахождения полного множества
простых чисел на определенном отрезке натурального ряда предло-
жен метод, использующий индексы составных чисел, или индексный
алгоритм [1–3].
Этот метод базируется на результатах работы [4]. Суть его состо-
ит в том, что вычисляются индексы составных чисел, указывающие
их место в натуральном ряду, а затем для нахождения самих простых
чисел выполняется поиск составных чисел c использованием разрабо-
танных авторами индексных алгоритмов.
82 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 6