Журнал «Continuum. Математика. Информатика. Образование»
Выпуск №4 (20) (2020)
УДК 511.1
DOI 10.24888/2500-1957-2020-4-94-110
ПОДХОД К ПОИСКУ ПРОСТЫХ ЧИСЕЛ СРЕДИ ЧЛЕНОВ ПОСЛЕДОВАТЕЛЬНОСТИ НАТУРАЛЬНОГО РЯДА СПЕЦИАЛЬНОГО ВИДА
В статье рассматривается проблема поиска простых чисел из заданного диапазона и факторизации больших чисел. Актуальность исследования обусловлена распространением ассиметричных криптографических алгоритмов в качестве методов обеспечения безопасного сеанса в глобальной сети, что обуславливает потребность дополнительных исследований, уточняющих свойства ряда простых чисел. Механизмы поиска простых чисел востребованы криптологией как для повышения безопасности работы глобальной сети, так и для разработки новых методов атак на ассиметричные криптографические системы шифрования. В работе рассматривается последовательность чисел, для которой ряд простых чисел является подпоследовательностью. Для построения этой последовательности предлагается разбить ряд натуральных чисел на полуинтервалы, границами которых являются произведения некоторого количества первых простых чисел. Показано, что на каждом таком полуинтервале имеет место множество специального вида, которому, в том числе, принадлежат простые числа, попадающие в соответствующий полуинтервал. Это множеств представляет интерес, так как его плотность ниже плотности натурального ряда. Это означает потенциальную возможность построения данного множества алгоритмом с относительно низкой асимптотической сложностью. В работе приводится и доказывается ряд утверждений и следствий из них, проливающих свет на свойства последовательности, полученной из объединения множеств специального вида. Показано на языке теории множеств возможного итеративного построения исследуемой последовательности, а также то, что для неё ряд простых чисел является подпоследовательностью. Полученные теоретические результаты позволяют спроектировать алгоритм поиска простых чисел в заданном диапазоне, а также создают задел на построение быстрых алгоритмов факторизации больших чисел.
AN APPROACH FOR SEARCHING PRIME NUMBERS AMONG MEMBERS OF CONSTRUCTED IN SPECIAL WAY SUBSE-QUENCE OF INTEGERS
The article deals with the problem of finding Prime numbers from a given range and factorizing large numbers. The relevance of the research is due to the spread of asymmetric cryptographic algorithms as methods for ensuring a secure session in the global network, which causes the need for additional research that clarifies the properties of a number of Prime numbers. Mechanisms for searching for Prime numbers are in demand by cryptology both to improve the security of the global network, and to develop new methods of attacks on asymmetric cryptographic encryption systems. In this paper, we consider a sequence of numbers for which a series of Prime numbers is a subsequence. To construct this sequence, we propose to divide a series of natural numbers into semi-intervals whose boundaries are products of a certain number of first primes. It is shown that on each such half-interval there is a set of a special type, which, among other things, belongs to the primes that fall into the corresponding half-interval. This set is interesting because its density is lower than the density of the natural series. This means that it is possible to construct this set using an algorithm with relatively low asymptotic complexity. The paper presents and proves a number of statements and their consequences, which shed light on the properties of the sequence obtained from the Union of sets of a special type. It is shown in the language of set theory that a possible iterative construction of the sequence under study is possible, as well as that a series of primes is a subsequence for it. The obtained theoretical results allow us to design an algorithm for searching for Prime numbers in a given range, and also create a Foundation for building fast algorithms for factorization of large numbers.
Список литературы
-
Бараш Л. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел: Безопасность информационных технологий. // Черноголовка: Институт теоретической физики им. Л. Д. Ландау. 2005. С. 27-38.
-
Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003.
-
Ландау Э. Основы анализа. М.: ИЛ, 1947.
-
Матысик О. В., Трофимук А. А. Теория чисел. Брест: Изд-во БрГУ, 2013.
-
Шеврин Л. Н. Общая алгебра. Глава IV. Полугруппы. М.: Наука, 1991. Т. 2.
-
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Триумф, 2002.
-
Chen J.R. On the Distribution of Almost Primes in an Interval // Sci.: Sinica18, 1975. 611-627.
-
Guy R. Unsolved Problems in Number Theory: Pseudoprimes. Euler Pseudoprimes. Strong Pseudo-primes. //New York: Springer-Verlag. 1994. 28-29.
-
Lawrence C. Elliptic Curves: Number Theory and Cryptography. Washington: Chapman & Hall/CRC. 2003.
-
Miller G. L. Riemann's hypothesis and tests for primality. // Journal of Computer and Systems Sci-ences. 1976. 300-317.
-
Montgomery H., Vaughan R. The exceptional set of Goldbach's problem // Poland, Poznan, Institute of Mathematics of the Polish Academy of Sciences: Actaarithmetica, 1975. 353-370.
-
Strassen V., Solovay R. A Fast Monte-Carlo Tests for Primality // SIAM Journal on Computing. 1977. №6(1). 84-85.