Law of distribution of number divisors (extended version)
Currently, the problem of factoring a composite semiprime number is insurmountable if the number of digits is large enough (hundreds of digits). In number theory, the issue of factorization of numbers is not given due attention and hence the lack of fundamental results.
When I was assigned by a university department to prepare and teach a new discipline, “Cryptographic Methods of Information Security,” I had to think and delve deeper into the topic. It was 1979. There simply were no open published sources on cryptography in the USSR. In the West, in addition to monographs, several periodicals were published.
My reasoning then was simple. Since modern systems for encoding and encrypting information are mainly numerical, it is necessary to create models of the numerical systems themselves and their elements (numbers), on which one could conduct research, experiment, and test hypotheses
Law of distribution of divisors of natural numbers
It became clear that we need to start with the natural series of numbers (NRF) – a system that underlies cryptographic methods of information protection. A continuous sequence of increasing positive integers (one-dimensional, linear model), where adjacent elements differ by one. But representations of this system are possible in spaces of different dimensions: 1 – linear, 2 – planar, 3 – volumetric.
The famous spiral of S. Ulam began to be considered by me as a two-dimensional complete model NRF. To carry out the research, I had to create the tools for working with the model myself. The volumetric model was discussed here. On a plane, a point (number N (x1xO)) has two coordinates: when specifying them, you must be able to determine N and back – when given N find coordinates x1xO, and also solve other problems. The leading role of odd numbers quickly became apparent.
Understanding this made it possible to create a truncated planar model of the natural series of numbers, which is based on the sum and difference of the squares of natural numbers or hyperbolic-circular dependencies. The model is guaranteed to contain all odd numbers, but not all even numbers. The tools for manipulating numbers were again created by me myself.
All textbooks, manuals, and problem books available from second-hand booksellers on number theory were collected on my desktop. So here it is. NRF goes to infinity, therefore, in models you can specify arbitrarily large numbers and work with them.
Numbers – elements of models can be represented in multiplicative or additive form. I did not try to immediately complicate the model. Valid number option N = pq – semiprime number – product of two primes p And q numbers. It was clear that this meaning N limits the initial fragment of the NRF for research and formation of the model, contains all odd numbers and their multiples less than N.
Marking of a fragment of the NRF
Let's make the assumption that we know the divisors N = pq. The obvious fact is that for composite numbers Nsomewhere near the beginning of the series fragment there will be dm = p – minor divisor Nand then its multiples will be entered into the register cells with a constant step; will also meet somewhere db = q is a larger divisor and its multiples will be observed with their constant step. But how to see them and identify them? We only know the component N. The assumption made ensures the creation of a clear picture. Cells occupied by multiples of different divisors are marked with a different color fill.
Example 1. Table 1 analyzes for the number N=77 distribution of multiple divisors, their positions are marked with shading (for dm green and for db blue). These are the boundaries of closed decision intervals, the centers Xts intervals correspond to squares of positions, which are also marked with fill (yellow).
Table 1. Fragment NRF and quadratic residues modulo N = 77
Indeed, for all closed intervals [7, 11]; [11,14]; [14, 22]; [22,28]; [21, 22]; [21,33]; [33,35]their boundaries are multiples of different divisors (fill of different colors), all except [11,14]; [28,33] And [21, 22] have an odd length KVV at the middle (yellow) central point – a complete square.
In the interval [7, 11] length L=5 in the center of KVV(xci =9) = 4, remoteness of borders k =√4 =2. In the border positions there are GL = 9 – 2 = 7Гп = 9 + 2 = 11 divisors with equal multiplicity factors 1.That is, the interval [7,11] – decisive interval. Dividers dm=7,db =11 Interval [21, 33] also decisive. Its length L = 13, center xci = 27, KVV(27) = 36, remoteness of borders k = √36 = 6. Gl = 27 – 6 = 3˖7 = 21Гп = 27 + 6 = 3˖11 = 33 divisors with equal multiplicity factors 3. Dividers dm= 7, db = 11 are calculated by the Euclidean GCD algorithm.
In reality for numbers and their KVV we must recognize only squares. They detect closed intervals called decisive intervals. Final calculation of divisor values di = GCD(N,xts ±k), Where k– distance of the border from the center.
Understanding the designations and symbols in Table 2, everything fell into place after marking the fragment. It turned out that the position of deductions in the lists KVKdividers control N.
We will consider closed intervals between cells occupied by different divisors (with different fills). Lengths L closed intervals, measured by the number of positions (register cells) between the boundaries (GlGn – left\right) intervals formed by different divisors (filled with different colors) and their multiples can take on even and odd values. For odd L there is a point (position) in the intervals Xts the center of the interval (see Tables 1, 2), which always corresponds to the squares of the KVK. Let us give the wording of the law.
Now we remove the assumption (that the divisors are known). Only squares remain from the markings (Table 2). Surprisingly, none of the famous mathematicians stopped their attention on this or began to delve into the essence of the distribution of divisors of a composite number N. To understand what we are talking about, let’s imagine a fragment of the NRF (bottom line of table. 2) numbers. Let's define composite comparison modules N1, N2, N3 and for the entire NRF N → ∞. For each number of NRFs, we calculate the quadratic residue according to the given modules. In other words, we will find the remainders from dividing the squares of numbers into modules and write them down in the modulus line.
At first, when X2 < Niin all lines the same squares follow one after another. Next we have X2 > Ni the picture is changing. In the lines for Ni Various numbers (division remainders) appear, occasionally interspersed with squares. But the behavior of the squares in this area looks chaotic; it is impossible to predict where, when and what the next square will appear for a specific row and for the entire array of rows. But now we know what's going on here
I'm in the table 2 I present only three lines, but the scattering of squares (yellow) in them does not contain any hints of an explanation or the existence of a law governing the process of their appearance. Perhaps no one had formed a model of a fragment of the NRF before me. I did not come across this in monographs and works of classics. If any of the readers have come across something similar, please feel free to let me know the source. I will be very grateful and grateful to you.
Table 2. Fragments of the NRF and lists of quadratic residues of rings Z117, Z119, Z133, Z.
Table 2 contains information about divisors of composite modules, but this should have been seen.
The division of the NRF into segments can not be limited to a fragment, but can be continued beyond it up to infinity, but only in the positive direction of the argument X.
Left column of the table 2 contains different component modules N. The table contains fragments of lists of quadratic residues modulo N=dmdb for numerical residue rings with different comparison modules, they generate sequences containing complete squares that are in no way related to one another and to the positions of the squares in the NRF (bottom row of the table). In the 4th line (N => ∞) the squares of a series of integers do not change or move.
Table analysis 2 shows that for different numbers N the trivial area may coincide, and subsequent appearances of KVV = KVK are distributed differently for everyone, which is difficult to explain without knowledge ZRD numbers. A common property can be considered the repetition of the values of the KVV residues(12) = KVV(26)=11; KVV(18)=KVV(39)=58 in the top line; KVV(23)=KVV(40)=53 in the second line; KVV(14) = KVV(40) = 79; KVV(18) = KVV(21) = 90KVV(25) = KVV(38)= 40 in the third line. Arguments KVV(x) = const with equal values differ by a multiple of one of the divisors of the composite module of the string.
Really, 12+2·7 = 26, 18 +3·7 = 39 in the top line; 23 + 17 = 40 in the second line;
14+2·13 = 40, 18 +3 = 21, 25+13 = 38 in the third line. Such dependencies also hold for repeated perfect squares. So in the second line five squares are repeated 4, 16, 25, 81,100. For them KVV(2) = KVV(2 + 17) = 4KVV(4) = KVV(4 + 2 17) = 16,
KVV(5) = KVV(5+7) = 25KVV(9) + KVV(9 + 17) = 81KVV(10) = KVV(10+ 2·7) = 100.
Example 2. Composite module specified N=119. It is necessary to find NRF points Xin which
x < N, x2 > N And x2(mod N) = r(x) =k2 – a complete square, where X — current point of the NRF. After performing all the necessary transformations, you can obtain the results summarized in Table 3.
Table 3. Fragment of NRF and quadratic residues modulo N = 119
Brief commentary on Table 3.
The two bottom rows of the table contain: the penultimate one – the squares of the current elements X rings, and the last line is the squares of their complements X1Where X1 = N – x. The fourth line from the bottom contains the KVV elements of the ring, which are complete squares (except for the point
x = 11its KVV = r(11) = 2 And x = 59its KVV = r(59) = 30 ).
This picture of the distribution of quadratic residues of a finite residue ring always occurs. This served as the basis for the formulation of the Law of Distribution of Divisors (LDD) of a composite natural number. Above (Fig. 2-5) are the decisive intervals corresponding N = 119 (table 3).
Extension of the law of distribution of divisors to RCN
Why 1st version The law of distribution of divisors of a composite number is not applicable for a number of integers (RCC)? This series, in contrast to NRFallows negative values of variables. The NRF, at the cost of simplifying calculations, imposes restrictions on the applicability of the ZRD for other media (rows). Thus, in the 1st version of the ZRD, restrictions are introduced.
First, all numeric values of variables must not exceed the value N;
Secondly, negative numeric values are not allowed;
Thirdly, the set of points narrows Xcapable of being centers of decisive intervals
(TsRI). Only points become such centers KCHKVin which KVV = KVK.
The presentation of the extended version of the ZRD number, as before, will begin with the fact that there is an ordered series Z integers whose elements are placed in positions (cells) of some shift register.
Known given composite odd number N with the assumption of known divisors dm And db. This assumption is necessary to obtain relationships, mathematical dependencies that facilitate the extraction of divisors from the model. We will limit our consideration (with the possibility of expansion) to the fragment Nр, symmetrical relative to the zero point – the origin.
The basic concepts, research concept and approach remain the same.
Let's mark the positions (Table 4 columns X1XO) a continuous fragment of integers, including, in addition to the interval (1, N) and part of the region of negative numbers. Such a fragment can be arbitrarily expanded left/right, while maintaining the marking of positions into small ones (dm) and large (db) intervals that are counted from the origin, placed at the position with zero.
Elimination (removal) of restrictions
In the first version (publication 2014) the ZRD of a composite semiprime number N = pq = dmdb a limited approach was considered, which was determined, on the one hand, by the choice of the number N NRF, and on the other – mathematical tools – modular arithmetic, which made all calculations quite simple.
The first limitation is removed. inclusion of negative values of multiples of divisors, which also exist when x < 0 in the range from – ∞ to 0and to exclude their consideration in theory means to artificially limit its capabilities. Inclusion of the number as a carrier of the ZRD Z – a series of integers (RCC) in addition to the NRF, allows the use of negative integers, which was unacceptable within the NRF.
The second limitation is eliminated by abandoning the method of modular arithmetic, which significantly expands the possibilities of using the manifestation of the CRD of a composite number. The point is that modulo comparison of all elements X carrier (including the squares of the central point RI) makes them smaller than this module, which narrows the search area for RIs and the calculation of RI boundaries. In principle, the squares in the center of the RI can be larger in module when the boundaries of the RI are sufficiently moved apart (expanded).
Construction of the decision interval
When specifying a composite number N its divisors are unknown to us. About the decisive interval we know only its properties. If for the elements of a fragment of a number series the CVVs are calculated using a composite modulo N and among them there is a complete square k2then this square always corresponds Xts the center of the decisive interval, and its value is the square of the distance of the boundaries from the center. Taking the square root k from KVV = KVK, i.e. from the found square, we determine the distance between the boundaries of Gl and Gn RI from its center Xts, Gl = Xts – k, Gn = Xts +k and the meaning of boundaries.
Among intervals whose boundaries are multiples of different divisors, only those that have an odd number can be decisive. L length and accordingly Xts center point. Such a point in the new version of the air defense system must also always correspond to a complete square. First degree k of this square – specifies the distance of the RI boundaries from its center.
How do such squares appear in the extended version of the ZRD? We square the next point Xwithout assuming that it turns out to be the center of the RI, this is determined by the modulo residue N. If the residue is a square, then X – the center of RI and this happens rarely. But the deduction is always less than the modulus Nand the square X there may be more module (X2 > N). Such a square for the current point X does not generate RI, since the left boundary becomes zero.
The modulo reduction operation is a multi-step reduction of the square by the modulus N at each step until the result becomes less than the module. In the new version, we do not exclude the possibility at some search step (reducing X2 for large X and increases for small X) get a new smaller square, X2 >Xm2 > KVV, but larger KVV. On the other hand, for small X their squares are not large and we find a new square by repeatedly summing the module with KVV + N + N + …+ N we get a larger square.
The question arises whether this (smaller/larger) square will describe the distance of the interval boundaries from the point X, But should the boundaries be multiples of different divisors?
Let's explain the situation with examples.
Example 3. (Obtaining a new square by multiple magnification X2, summing with modulus). Setting up a composite module N = 119. In ordered sequence Z of integers, we select the fragments to the left and right of zero. As before, let’s build a multi-line number model N=119within which we select the trivial region KVV = KVK. First number Xwhose square exceeds N equals x = 11. Its square 112 = 121, and KVV = 112 – 119 = 2. Such a square does not ensure the construction of RI, since, for example, Гl = Xts – k = 11 – 11 = 0 the multiplicity condition for the divisor is not satisfied.
Can this one x = 11 to be the center of RI? For this to happen, it is necessary for x = 11 find the corresponding square that will determine the distance k borders from x = 11containing multiples of different divisors.
Let's construct an RI with center at x = 11. To do this, deduct KVV = 2 we will sum the module many times N = 119, until we get a new square 2 +119 + 119 + …+ 119 = 2025.
Such a square exists and is obtained at the 17th step of summation.
We calculate in a loop by i with verification of obtaining a square at each step.
i = 1, 2+119 =121Meaning 121 does not create RI, but it can be increased to a new square.
i=2, 121+119 = 240 = ⃞?NO; i=3, 240 + 119 = 359 = ⃞?NO; i=4, 359+119 = 478 = ⃞?NO
i=5, 478 +119 = 597= ⃞? NO; i =6, 597 +119 = 716 = ⃞? NO; i=7, 716+119 = 835 = ⃞?NO
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
i =15,1668+119=1787= ⃞? NO; i =16,1787+119=1906 = ⃞?NO; i =17,1069+119=452 = ⃞?YES.
At the point x = 11 we found a new square. Let's calculate the distance k borders and the borders of the Republic of Ingushetia themselves:
k = 45; the boundaries turned out to be multiples of different divisors:
Gl = Xts – k = 11 – 45 = – 34 = (-2)˖17,
Gn = Xts + k = 11 + 45 = 56 = 8˖7.
Everything worked out, but the left border of the RI has a negative value (we will attribute the sign to the coefficient). This RI does not belong to the NRF (coefficient – 2 < 0), but belongs to the series of integers.
Example 4. (Obtaining a new square by repeatedly subtracting the modulus from X2). Let's define a composite module N=119, And x = 106, KVV(x) = 50. We are building Xts squared 1062 = 11236 > N. Such a square does not ensure the construction of RI, since Gl= Xts – k = 106 –106 = 0.
We will reduce the square and check the result 11236 –119 –119 – … –119 = 3025 = 552 until we get a new smaller square. At the 69th step we get a new smaller square
Xm2 = 3025 = 552. The same square can be obtained faster by repeatedly adding the modulus to the residue25 once. Let's check the multiplicity of the divisors of the boundaries of the interval centered at the point x = 106,
Gl = Xts – k = 106 – 55 = 51 = 3˖17,
Gn = Xts + k = 106 + 55 = 161 = 23˖7.
The example follows: point x = 106 is the center of the RI, the boundaries of the RI are multiples of the divisors N,
another square (smaller) obtained at the central point k2 = 3025<1062describes the distance of the borders from the center of the Republic of Ingushetia.
And a more general conclusion: the construction of decisive intervals is possible at other points of the fragment, except for those that have KVV = KVK. If we consider RCCH as the carrier of the SRD, then all calculations and results are acceptable.
In contrast to the previous version of the ZRD, the number of RIs has increased, and the previously excluded element
x = 11 became the center of the new Republic of Ingushetia.
The boundaries of the intervals contain values that are multiples of different divisors with integer coefficients. We also get a positive answer to the earlier question – the element x = 11 can be the center of a decisive interval if we choose not an NRF but a sequence of integers as the carrier of the RRD, since negative values of elements are not allowed in the NRF.
It is important to note that the difference of squares 452 – 112 for element x = 11 must be completely divisible by module Ni.e. be a multiple of modulus Nnamely, 452 – 112 = 1904 = 16·119.
It follows from this that the square of a number 45 can be obtained in a purely formal way, namely, by successively increasing the value 121square of the number (x = 11) on N=119. This is like a modulo reduction operation “in reverse”, not by decreasing, but by increasing.
Continuing to obtain squares for x = 12, 13, 14, 15, 16, 17, 18, 19 etc., we ask whether these values can be RI centers, and if so, how is this ensured?
At the point x = 122 = 144 just use modulo reduction N, 144 – 119 = 52;
Calculating the boundaries of Ch =12 – 5 = 1 ·7; GP = 12 + 5 = 1 17;
At the point x = 132 = 169; 169 + 119 +119 +…+119 = 3025 = 552 And 3025 –169 = 24 119;
Calculating the boundaries of Ch =13 – 55 = – 42 = (–6) 7; Гп =13 + 55 = 68 = 4·17;
At the point x = 142 = 196; 196 + 119 +119 +…+119 = 11025 =1052 And 11025 – 196 = 91 119;
Calculating the boundaries of Ch =14 – 105 = – 91 = (–11) 7; Gp =14 + 105 = 119 = 1 119;
At the point x = 152 = 225; 225 + 119 +119 +…+119 = 1296 =362 And 1296 – 196 = 1071 = 9 119;
Calculating the boundaries of Ch =15 – 36 = – 21 = (–3) 7; GP = 15 + 36 = 51 = 3 17;
At the point X = 162 = 256; 256 + 119 +119 +…+119 = 1089 =332 And 1089 – 256 = 833 = 7 119;
Calculating the boundaries of Ch =16 – 33 = – 17 = (–1) 17; Gp = 16 + 33 = 49 = 7 7;
At the point x = 172 = 289; 289 + 119 + +…+119 = 10404 =1022 And 10404 – 289 =10115 = 85·119;
Calculating boundaries Gl =17 – 102 = – 85 = (–5) ·17; GP = 17 + 102 = 119 = 1 7 17;
At the point X = 182 = 324; 324 + 119 + 119+…+119 = 2704 =522 And 2704 – 324 =2380 = 20·119;
Calculating boundaries Gl =18 – 52 = – 34 = (–2) ·17; GP = 18 + 52 = 70 = 10 7;
At the point x = 192 = 361; use modulo reduction N, 361 – 3 119 = 4 at the point Xts.
These examples illustrate the capabilities of the extended version of the ZRD number.
Conclusion
The new version of the ZRD extends the law to a number of integers. Expands the capabilities of constructing decisive intervals at current points of the RCC. To do this, new squares are calculated at these points, determining the distance of the RI boundaries from its center.
The first version of the ZRD, taking into account the restrictions imposed on the variables by the natural series of numbers (NSN), serves as a special, simpler case of the new version
Literature in Russian
1. Koblitz N. Number theory and cryptography course — 2nd edition — M.: Scientific publishing house TVP2001. – 254 p. — ISBN 978-5-85484-014-9978-5-85484-012-5
2. Cheremushkin A.V. Lectures on arithmetic algorithms in cryptography – M.: MCNMO2002. – 104 p. — ISBN 978-5-94057-060-8
3. Vasilenko O. N. Number-theoretic algorithms in cryptography – M.: MCNMO2003. – 328 p. — ISBN 978-5-94057-103-2
4. Ishmukhametov Sh. T. Factorization methods for natural numbers: study guide – Kazan: Kazan University2011. – 190 p.
5. Nesterenko A. Yu. Number-theoretic methods in cryptography – M.: Moscow State Institute of Electronics and Mathematics2012.–224 pp.–ISBN 978-5-94506-320-4
6. Knuth, D. The Art of Programming = The Art of Computer Programming. – Moscow: Williams, 2007. – T. 2. – 832 p. — ISBN 978-5-8459-0081-4.
7. Introduction to cryptography / Yashchenko, V. V. – Moscow: MCNMO1999. – 272 p. — ISBN 5-900916-40-5.
8. Schneier, B. Applied cryptography. Protocols, algorithms, source texts in C language = Applied Cryptography. Protocols, Algorithms and Source Code in C. – Moscow: Triumph, 2002. – 816 p. — 3000 copies. — ISBN 5-89392-055-4.
in English
Bressoud, D.M. Factorization and Primality Testing. – N.Y.: Springer-Verlag, 1989. – 260 p. — ISBN 0-387-97040-1.
Mahoney, MS The Mathematical Career of Pierre de Fermat. – 2. – Princeton: Princeton University Press, 1994. – P. 324-332. — 438 p. — ISBN 0-691-03666-7
