The distribution law of the divisors of a natural number in the NRC
One of the current problems of information security is the confidentiality of messages, which is provided in RSA-like ciphers using cryptographic protection of messages. Such protection is successfully implemented with knowledge of the distribution law of divisors of a composite number (residue ring module) in the natural number series (NPS) and the presence of a cryptographic system (CGS), within which messages are circulated.
The basis of the CGS consists of encryption algorithms, encryption key management system, cryptographic protocols, hashing functions and electronic signature. Each cipher and, accordingly, an encryption algorithm has a set of characteristics on the basis of which users make a choice for the use of one or another cipher. It is obvious that preference is given to a cipher with a sufficiently high level of resistance to opening the cipher key and, accordingly, the contents of the protected message.
The lifetime of high-quality ciphers until their disclosure and publication of this is calculated for years, and very high-quality for decades. Among the symmetric and asymmetric ciphers, the two-key RSA cipher is very popular. It has been known since 1978, the year of the first publication describing the algorithm.
The strength of this cipher is determined by the impossibility of solving the mathematical problem of factoring a large number (SFCF) —the cipher module in a reasonable time for the user. This time is calculated over the years. For example, a composite number of 232 decimal digits was factorized in 2010, and it was announced on the RSA website list in 1991, among others. The list begins with a number of 100 digits. The first 18 numbers over the past years through the efforts of mathematicians around the world and the PC have consistently decomposed all the past years, which indicates the great interest of mathematicians in this problem. The last number in the list contains 617 digits, which corresponds to a cipher key with a length of 2048 binary digits.
The main provisions of the theory
This paper addresses the problem of factoring natural numbers. The binding of the specified N and defined objects (dividers) to the main object - NPS is carried out. The use of the properties of NPS and the properties of composite numbers that are not related to their digit capacity indicate a different direction for finding a solution to the problem of factorization. The above theorem and Example 3 indicate which elements need to be focused on, localize these elements within the NPS and limit the search areas. The regions themselves receive a model description.
In this paper, the problem is formulated as follows. The composite number N is given by the position on the axis of the natural series of numbers, where each number is assigned an indexed position. It is required to define natural dividers - factors N. Factors (dividers) numbers are also placed in their NPS positions, which are always located closer to the beginning, to the left of N. All positions from zero to N - 1 are occupied by smaller N numbers that form the final residue ring for the composite a module whose role is played by N. Obviously, among the smaller numbers (elements of the residue ring) there are also dividers, and if the dividers are small, then the multiples of these dividers. You can always specify two component divisors if there are more than two for N, or two are simple. Let own divisors be only two, i.e.N = pq .
We formulate the theorem on divisors of the compound odd N.
Theorem . The squared half-difference of the divisors is comparable in magnitude to their product N with the squared half-sum of the divisors, which will be formally written as[(pq) / 2] 2 ≡ [(p + q) / 2] 2 (modN).
Indeed, for the right side, given that N = pq, squaring a half-sum and expanding the brackets, we get the expression
(p 2 + 2pq + q 2 - 4N) / 4 = (p 2 - 2pq + q 2 ) / 4 = [(pq) / 2] 2 ,
coincides with the left-hand side, which proves the theorem.
It follows from the theorem that among the elements of a residue ring modulo N there is an element x whose square modulo N coincides with the square of the half-sum of divisors and the difference of this square with the modulus of the ring is equal to another element r of the ring whose value coincides with the square of the half-difference of the divisors. Finding such ring elements makes it possible to form a closed system of algebraic equations, the solution of which will be the required divisors.
')
Example 1 Let a pair of natural primes be given p = 47,q = 67 and N = pq = 3149 . We calculate the half-sum for dividers (67 + 47) / 2 = 57, and (67- 47) / 2 = 10 their half difference, and also perform the transformations of the right side 57 2 - 3149 = 3249 - 3149 = 100 = 10 2 , which coincides with the square of the left side of the expression from the theorem.
The half-sum of the dividers is the first (smaller) element of the ring (point x NPS), which leads to the decomposition of N into factors. Of course, this point is unknown to us, as well as the half-difference point of the divisors.
In algebraic finite residue rings in a composite module, when lexicographically ordering elements in ascending order, all quadratic residue (KVV) are also ordered, but at first glance their sequence looks rather chaotic.
It is convenient to divide such a sequence of EBC into three parts. The first, initial part is called trivial. It is formed by quadratic residues modulo N — complete squares, since the square elements, which are less than the modulus, are not reduced (are not given modulo). In this part, we will include in order and all quadratic residues - not full squares. This is followed by the middle part, the left border of which is the first met quadratic residue — the complete square. Thus, everything before him is the initial part. The final part of the KVV list is separated from the middle part by the position of the NPS, in which the last quadratic residue — the full square — appears. The last part may not be at all if the quadratic residue of the element (N-1) / 2 turns out to be a complete square. This is a fairly common situation, it takes place for the canonical composite module.
Example 2. Let the cipher module be given N = d1 • d2 = 2091. Dividers are generally unknown.
In this example, the point that begins the middle part of a sequence of quadratic residues is the position immediately after the trivial part. The trivial part of the list includes squares from 1 to 45, (up to the nearest square to the module, not exceeding it), and the next position, equal tox = 46 (46 <N, 46 2 > N), has a total square squared residue,
46 2 (modN) = 25. In this case, the dividers N are found from the relationdi = 46 ± √25 = 46 ± 5, whence d1 = 46 + 5 = 51 and d2 = 46 - 5 = 41 . For this case, it is easy to verify that what was said earlier about the properties of divisors is true.
We calculate the half-sum (51 + 41) / 2 = 46, the half-difference (51 - 41) / 2 = 5 and perform the transformations of the right side46 2 - 2091 = 5 2 = 25, which coincides with the square of the left side of the relation from the theorem. The half-sum of dividers is really the first point, which leads to the decomposition of N into factors.
It is also a remarkable fact that a quick search for divisors is determined not only by such a first point (it is not so easy to get to it), but by any quadratic residue — a complete square. The following example illustrates the capabilities of the quadratic residues of a finite ring if they are full squares.
Illustration of the law of distribution of dividers of the composite module
Example 3 Set the composite module N = 119. It is necessary to find the NFR points at whichx <N, x 2 > N and x 2 (mod N) = r (x) = ⃞ is a full square, where x is the current NFR point. After performing all the necessary transformations, you can get the results summarized in Table 1.
A brief comment on the table.
The bottom two lines of the table contain: the penultimate - the squares of the current elements of the x-ring, and the last line - the squares of their complement x1, wherex1 = N - x . The fourth line from the bottom contains KVV ring elements, which are full squares (except for the point x = 11, its KVV r (11) = 2 and x = 59, its KVV r (59) = 30 ). Such a picture of the distribution of quadratic residues of a finite residue ring always holds. This served as the basis for the formulation of the Law of Distribution of Divisors (RDA) of a composite natural number. The law is formulated as follows.
The law of distribution of divisors d i , i = 1 (1) ..., the composite number N is the ratio that determines the set of positions of the NPS in which the dividers and their multiple values depending on the given N are placed. All the dividers and their multiple are values in boundary points of intervals symmetric with respect to the pointsx <N, x 2 > N, x 2 (mod N) = r (x), in which the CVB r (x) are full squares, i.e. d i = x ± √r (x), i = 1 (1)… .
After obtaining x with the specified property, pairs of d 1 , d 2 values are found. The number N can be divided into them and found in the same way other dividers for the private smaller N. If the obtained d 1 , d 2 are not prime numbers, then applying the Euclidean GCD to any of d 1 , d 2 and the module N, find their next common divider. This is the case until the complete decomposition of N into prime factors.
The work does not describe the way of finding x, which excludes complete enumeration, and the author understands what problems will be encountered along this way. Separate preparatory questions for solving this problem are presented by the author in his previous publications.
The basis of the CGS consists of encryption algorithms, encryption key management system, cryptographic protocols, hashing functions and electronic signature. Each cipher and, accordingly, an encryption algorithm has a set of characteristics on the basis of which users make a choice for the use of one or another cipher. It is obvious that preference is given to a cipher with a sufficiently high level of resistance to opening the cipher key and, accordingly, the contents of the protected message.
The lifetime of high-quality ciphers until their disclosure and publication of this is calculated for years, and very high-quality for decades. Among the symmetric and asymmetric ciphers, the two-key RSA cipher is very popular. It has been known since 1978, the year of the first publication describing the algorithm.
The strength of this cipher is determined by the impossibility of solving the mathematical problem of factoring a large number (SFCF) —the cipher module in a reasonable time for the user. This time is calculated over the years. For example, a composite number of 232 decimal digits was factorized in 2010, and it was announced on the RSA website list in 1991, among others. The list begins with a number of 100 digits. The first 18 numbers over the past years through the efforts of mathematicians around the world and the PC have consistently decomposed all the past years, which indicates the great interest of mathematicians in this problem. The last number in the list contains 617 digits, which corresponds to a cipher key with a length of 2048 binary digits.
The main provisions of the theory
This paper addresses the problem of factoring natural numbers. The binding of the specified N and defined objects (dividers) to the main object - NPS is carried out. The use of the properties of NPS and the properties of composite numbers that are not related to their digit capacity indicate a different direction for finding a solution to the problem of factorization. The above theorem and Example 3 indicate which elements need to be focused on, localize these elements within the NPS and limit the search areas. The regions themselves receive a model description.
In this paper, the problem is formulated as follows. The composite number N is given by the position on the axis of the natural series of numbers, where each number is assigned an indexed position. It is required to define natural dividers - factors N. Factors (dividers) numbers are also placed in their NPS positions, which are always located closer to the beginning, to the left of N. All positions from zero to N - 1 are occupied by smaller N numbers that form the final residue ring for the composite a module whose role is played by N. Obviously, among the smaller numbers (elements of the residue ring) there are also dividers, and if the dividers are small, then the multiples of these dividers. You can always specify two component divisors if there are more than two for N, or two are simple. Let own divisors be only two, i.e.
We formulate the theorem on divisors of the compound odd N.
Theorem . The squared half-difference of the divisors is comparable in magnitude to their product N with the squared half-sum of the divisors, which will be formally written as
Indeed, for the right side, given that N = pq, squaring a half-sum and expanding the brackets, we get the expression
coincides with the left-hand side, which proves the theorem.
It follows from the theorem that among the elements of a residue ring modulo N there is an element x whose square modulo N coincides with the square of the half-sum of divisors and the difference of this square with the modulus of the ring is equal to another element r of the ring whose value coincides with the square of the half-difference of the divisors. Finding such ring elements makes it possible to form a closed system of algebraic equations, the solution of which will be the required divisors.
')
Example 1 Let a pair of natural primes be given p = 47,
The half-sum of the dividers is the first (smaller) element of the ring (point x NPS), which leads to the decomposition of N into factors. Of course, this point is unknown to us, as well as the half-difference point of the divisors.
In algebraic finite residue rings in a composite module, when lexicographically ordering elements in ascending order, all quadratic residue (KVV) are also ordered, but at first glance their sequence looks rather chaotic.
It is convenient to divide such a sequence of EBC into three parts. The first, initial part is called trivial. It is formed by quadratic residues modulo N — complete squares, since the square elements, which are less than the modulus, are not reduced (are not given modulo). In this part, we will include in order and all quadratic residues - not full squares. This is followed by the middle part, the left border of which is the first met quadratic residue — the complete square. Thus, everything before him is the initial part. The final part of the KVV list is separated from the middle part by the position of the NPS, in which the last quadratic residue — the full square — appears. The last part may not be at all if the quadratic residue of the element (N-1) / 2 turns out to be a complete square. This is a fairly common situation, it takes place for the canonical composite module.
Example 2. Let the cipher module be given N = d1 • d2 = 2091. Dividers are generally unknown.
In this example, the point that begins the middle part of a sequence of quadratic residues is the position immediately after the trivial part. The trivial part of the list includes squares from 1 to 45, (up to the nearest square to the module, not exceeding it), and the next position, equal to
46 2 (modN) = 25. In this case, the dividers N are found from the relation
We calculate the half-sum (51 + 41) / 2 = 46, the half-difference (51 - 41) / 2 = 5 and perform the transformations of the right side
It is also a remarkable fact that a quick search for divisors is determined not only by such a first point (it is not so easy to get to it), but by any quadratic residue — a complete square. The following example illustrates the capabilities of the quadratic residues of a finite ring if they are full squares.
Illustration of the law of distribution of dividers of the composite module
Example 3 Set the composite module N = 119. It is necessary to find the NFR points at which
A brief comment on the table.
The bottom two lines of the table contain: the penultimate - the squares of the current elements of the x-ring, and the last line - the squares of their complement x1, where
The law of distribution of divisors d i , i = 1 (1) ..., the composite number N is the ratio that determines the set of positions of the NPS in which the dividers and their multiple values depending on the given N are placed. All the dividers and their multiple are values in boundary points of intervals symmetric with respect to the points
After obtaining x with the specified property, pairs of d 1 , d 2 values are found. The number N can be divided into them and found in the same way other dividers for the private smaller N. If the obtained d 1 , d 2 are not prime numbers, then applying the Euclidean GCD to any of d 1 , d 2 and the module N, find their next common divider. This is the case until the complete decomposition of N into prime factors.
The work does not describe the way of finding x, which excludes complete enumeration, and the author understands what problems will be encountered along this way. Separate preparatory questions for solving this problem are presented by the author in his previous publications.
Source: https://habr.com/ru/post/229601/
All Articles