July 30, 2014 at 14:00The law of distribution of the divisors of a natural number in the NDF
One of the urgent problems of information security is the confidentiality of messages, which is ensured in RSA-like ciphers using cryptographic protection of messages. Such protection is successfully implemented with knowledge of the distribution law of the dividers of a composite number (module of the residue ring) in a natural number series (NRF) and the presence of a cryptographic system (CGS), within which messages circulate.
The basis of CGS is encryption algorithms, an encryption key management system, cryptographic protocols, hash functions and an electronic signature. Each cipher and, accordingly, the encryption algorithm has a set of characteristics, on the basis of which users make the choice to use one or another cipher. Obviously, preference is given to a cipher with a sufficiently high level of resistance to opening the cipher key and, accordingly, the content of the protected message.
The life time of high-quality ciphers until their disclosure and publication about this is calculated in years, and in very high-quality decades. Among 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 factorization of a large number (ZFBCH) - the cipher module in an acceptable time for the user. This time is calculated in years. For example, a composite number of 232 decimal digits was factorized in 2010, and it was announced on a list on the RSA website, among others in 1991. The list starts with a number of 100 digits. The first 18 numbers over the past years by the efforts of mathematicians around the world and PC have been consistently laid out over the past years, which indicates a 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.
Theory of the theory
In this paper, the problem of factorization of natural numbers is addressed. The given N and determined objects (dividers) are linked to the main object - NRF. The use of the properties of the NDF and the properties of composite numbers that are not related to their bit depth indicate another direction for finding a solution to the factorization problem. The above theorem and example 3 indicate which elements need to be focused on, localize these elements within the NRF, and limit the scope of the search. The regions themselves receive a model description.
In the work, 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 has an indexed position. It is required to determine the natural divisors - factors N. Factors (divisors) of the number are also located in their positions of the NRF, which are always located closer to the beginning, to the left of the position of N. All positions from zero to N - 1 are occupied by smaller N numbers forming the final ring of residues by the compound to a module whose role is played by N. Obviously, among the smaller numbers (elements of the residue ring) there will also be divisors, and if the divisors are small, then multiples of these divisors. You can always specify two composite divisors if for N there are more than two, or two simple ones. Let there be only two proper divisors, i.e.N = pq .
We formulate a divisor theorem for a composite odd N.
Theorem . The square of the half-difference of the divisors is comparable modulo their product N with the square of the half-sum of the divisors, which is formally written as[(pq) / 2] 2 ≡ [(p + q) / 2] 2 (modN) .
Indeed, for the right-hand side, given that N = pq, squaring the half-sum and opening the brackets, we obtain the expression
(p 2 + 2pq + q 2 - 4N) / 4 = (p 2 - 2pq + q 2 ) / 4 = [ (pq) / 2] 2 , which
coincides with the left side, which proves the theorem.
It follows from the theorem that among the elements of the residue ring modulo N there is an element x whose square modulo N coincides with the square of the half-sum of the divisors and the difference of this square with the module 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 elements of the ring allows us to form a closed system of algebraic equations, the solution of which will be the desired divisors.
Example 1 . Let a pair of natural primes p = 47,q = 67 and N = pq = 3149 be given . For the divisors, we calculate the half-sum (67 + 47) / 2 = 57, and (67-47) / 2 = 10 their half-difference, and also perform the transformations of the right-hand 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 divisors is the first (smaller) element of the ring (point x LFD), which leads to a factorization of N. Of course, such a point is unknown to us, as well as the half-difference point of the divisors.
In the algebraic finite residue rings by the composite module, with lexicographic ordering of the elements in ascending order, all quadratic residues (SEC) are also ordered, but at first glance their sequence looks rather chaotic.
It is convenient to divide such a sequence of HVB into three parts. The first, initial part is called trivial. It is formed by quadratic residues modulo N - full squares, since the elements of the square, which are smaller than the modulus, are not reduced (are not modulo reduced). In this part, we include, in order, all quadratic residues that are not full squares. This is followed by the middle part, the left border of which is the first quadratic residue encountered - a full square. Thus, everything before him is the initial part. The final part of the list of CVI is separated from the middle part by the position of the NRF, in which the last quadratic residue appears - the full square. The last part may not be at all if the quadratic residue of the element (N-1) / 2 turns out to be a full square. This is a fairly common situation,
Example 2. Let a cipher module N = d1 • d2 = 2091 be given. In general, the divisors are unknown.
In this example, the point at which the middle part of the quadratic residue sequence begins is the position immediately following the trivial part. The trivial part of the list includes squares from 1 to 45, (to the nearest square to the bottom of the module, without exceeding it), and the next position equal tox = 46 (46 <N, 46 2 > N) has a square squared subtraction,
46 2 (modN) = 25. Moreover, the divisors of 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 above about the properties of the 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-hand side46 2 - 2091 = 5 2 = 25 , which coincides with the square of the left-hand side of the relation from the theorem. The half-sum of the divisors is indeed the first point, which leads to a factorization of N.
A remarkable fact is 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 full square. The following example illustrates the possibilities of quadratic residues of a finite ring if they are full squares.
Illustration of the distribution law of the divisors of a composite module
Example 3. The composite module N = 119 is specified. It is necessary to find the LDP points at whichx2> N and x 2 (mod N) = r (x) = ⃞ Is the full square, where x is the current point of the NRF. After performing all the necessary transformations, you can get the results summarized in table 1.
A brief comment on the table.
The bottom two rows of the table contain: the penultimate one is the squares of the current elements x of the ring, and the last row is the squares of their complements x1, wherex1 = N - x . The fourth row from the bottom contains the KBW of the ring elements, which are full squares (exclusion of the point x = 11, its KBV r (11) = 2 and x = 59, its KBV 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 distribution law of the divisors d i , i = 1 (1) ..., of a composite number N is the relation defining the set of positions of the LFD, in which the divisors and multiples of them are located, depending on the given N. All divisors and multiples of them are the values in the boundary points of the intervals symmetric with respect to the pointsx <N, x 2 > N, x 2 (mod N) = r (x) , in which the RWS r (x) are full squares, i.e. d i = x ± √r (x), i = 1 (1) ... .
After obtaining x with the specified property, pairs of values of d 1 , d 2 are found . The number N can be divided into them and found in the same way other divisors for the quotient less N. If the resulting d1 , d 2 are not prime numbers, then applying the Euclidean GCD Algorithm to any of d 1 , d 2 and the module N, they find their next common divisor. So they act until the full decomposition of N into prime factors.
The paper does not describe the path of finding x, which excludes exhaustive search, and the author understands what problems will be encountered along this path. Separate preparatory questions for solving this problem by the author are presented in his previous publications.
The basis of CGS is encryption algorithms, an encryption key management system, cryptographic protocols, hash functions and an electronic signature. Each cipher and, accordingly, the encryption algorithm has a set of characteristics, on the basis of which users make the choice to use one or another cipher. Obviously, preference is given to a cipher with a sufficiently high level of resistance to opening the cipher key and, accordingly, the content of the protected message.
The life time of high-quality ciphers until their disclosure and publication about this is calculated in years, and in very high-quality decades. Among 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 factorization of a large number (ZFBCH) - the cipher module in an acceptable time for the user. This time is calculated in years. For example, a composite number of 232 decimal digits was factorized in 2010, and it was announced on a list on the RSA website, among others in 1991. The list starts with a number of 100 digits. The first 18 numbers over the past years by the efforts of mathematicians around the world and PC have been consistently laid out over the past years, which indicates a 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.
Theory of the theory
In this paper, the problem of factorization of natural numbers is addressed. The given N and determined objects (dividers) are linked to the main object - NRF. The use of the properties of the NDF and the properties of composite numbers that are not related to their bit depth indicate another direction for finding a solution to the factorization problem. The above theorem and example 3 indicate which elements need to be focused on, localize these elements within the NRF, and limit the scope of the search. The regions themselves receive a model description.
In the work, 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 has an indexed position. It is required to determine the natural divisors - factors N. Factors (divisors) of the number are also located in their positions of the NRF, which are always located closer to the beginning, to the left of the position of N. All positions from zero to N - 1 are occupied by smaller N numbers forming the final ring of residues by the compound to a module whose role is played by N. Obviously, among the smaller numbers (elements of the residue ring) there will also be divisors, and if the divisors are small, then multiples of these divisors. You can always specify two composite divisors if for N there are more than two, or two simple ones. Let there be only two proper divisors, i.e.
We formulate a divisor theorem for a composite odd N.
Theorem . The square of the half-difference of the divisors is comparable modulo their product N with the square of the half-sum of the divisors, which is formally written as
Indeed, for the right-hand side, given that N = pq, squaring the half-sum and opening the brackets, we obtain the expression
coincides with the left side, which proves the theorem.
It follows from the theorem that among the elements of the residue ring modulo N there is an element x whose square modulo N coincides with the square of the half-sum of the divisors and the difference of this square with the module 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 elements of the ring allows us to form a closed system of algebraic equations, the solution of which will be the desired divisors.
Example 1 . Let a pair of natural primes p = 47,
The half sum of the divisors is the first (smaller) element of the ring (point x LFD), which leads to a factorization of N. Of course, such a point is unknown to us, as well as the half-difference point of the divisors.
In the algebraic finite residue rings by the composite module, with lexicographic ordering of the elements in ascending order, all quadratic residues (SEC) are also ordered, but at first glance their sequence looks rather chaotic.
It is convenient to divide such a sequence of HVB into three parts. The first, initial part is called trivial. It is formed by quadratic residues modulo N - full squares, since the elements of the square, which are smaller than the modulus, are not reduced (are not modulo reduced). In this part, we include, in order, all quadratic residues that are not full squares. This is followed by the middle part, the left border of which is the first quadratic residue encountered - a full square. Thus, everything before him is the initial part. The final part of the list of CVI is separated from the middle part by the position of the NRF, in which the last quadratic residue appears - the full square. The last part may not be at all if the quadratic residue of the element (N-1) / 2 turns out to be a full square. This is a fairly common situation,
Example 2. Let a cipher module N = d1 • d2 = 2091 be given. In general, the divisors are unknown.
In this example, the point at which the middle part of the quadratic residue sequence begins is the position immediately following the trivial part. The trivial part of the list includes squares from 1 to 45, (to the nearest square to the bottom of the module, without exceeding it), and the next position equal to
46 2 (modN) = 25. Moreover, the divisors of 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-hand side
A remarkable fact is 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 full square. The following example illustrates the possibilities of quadratic residues of a finite ring if they are full squares.
Illustration of the distribution law of the divisors of a composite module
Example 3. The composite module N = 119 is specified. It is necessary to find the LDP points at which
A brief comment on the table.
The bottom two rows of the table contain: the penultimate one is the squares of the current elements x of the ring, and the last row is the squares of their complements x1, where
The distribution law of the divisors d i , i = 1 (1) ..., of a composite number N is the relation defining the set of positions of the LFD, in which the divisors and multiples of them are located, depending on the given N. All divisors and multiples of them are the values in the boundary points of the intervals symmetric with respect to the points
After obtaining x with the specified property, pairs of values of d 1 , d 2 are found . The number N can be divided into them and found in the same way other divisors for the quotient less N. If the resulting d1 , d 2 are not prime numbers, then applying the Euclidean GCD Algorithm to any of d 1 , d 2 and the module N, they find their next common divisor. So they act until the full decomposition of N into prime factors.
The paper does not describe the path of finding x, which excludes exhaustive search, and the author understands what problems will be encountered along this path. Separate preparatory questions for solving this problem by the author are presented in his previous publications.