Factorization of number, problems of its theory and position of the author

         The problem of factorization of numbers did not arise yesterday, it goes back thousands of years. One can only guess why in 1900 at the Mathematical Congress D. Hilbert did not include her in the list of his 23 problems, and later she did not get on the list of unsolved mathematical problems of S. Ulam. The special attention and interest of mathematicians in the problem was indicated only in recent decades. Perhaps the stimulus was the discovery of a new direction - two-key cryptology, the emergence of public-key ciphers. We can assume that today's interest in the problem of factorization of numbers is dictated by some uncertainty regarding the theoretical justification of the resistance to disclosure of the two-key RSA cipher (private key), which is very popular today, which, in principle, can be cracked without knowing the private key. Keyless Decryption. Just in the theory of algebraic rings, the necessary results for this have not yet been found. But there is an equally important aspect of this problem - the lack of an operation inverse to the multiplication of numbers. A simple quick and affordable multiplicative decomposition of composite numbers can become such an arithmetic operation, and will replenish the arsenal of computational tools in mathematics.


              A brief description of the current situation in the field of factorization

         In order to clarify the current situation in the field of factorization of natural numbers (elements of the natural number series (NRF)) and evaluate the possibilities of its current resolution by RSA in 1991, a list of 42 test numbers of various digits from 100 to 617 decimal digits was compiled and published, later called RSA numbers. The company invited everyone to try their hand and use mathematical training in solving the problem of factorization of large numbers (ZFBCH) from this list. To stimulate the activity of participants, a bonus was assigned for each factorized number. Under the conditions of such a contest, it was stipulated that all the numbers in the list were obtained by multiplying only two primes of practically the same bit depth and that the difference of these factors had the bit depth of the same order (i.e. the numbers are not close to one another). The "competition" has been stretching for more than two decades and is not yet complete (the list of numbers is not laid out). Perhaps the "competition" will continue for more than one decade. To date, the decomposition results of only 13 first numbers of the list have been published. The largest of them is described by 232 decimal digits, the factors are formed by 116 digits. Publication about this 2010.

    Table 1 - Achievements in the field of factorization of large numbers (RSA cipher comparison modules), a list of which was announced by RSA in 1991.


         An analysis of almost 20 years of efforts and the results of successful factorization of RSA numbers allows us to conclude that the methods used by teams and individual mathematicians in solving the HFBP depend significantly on such a property of the factorizable number as its length. The longer the number, the more years it took to factorize it.
         After 10-15 years, representatives of the company ceased to worry about the imminent collapse, calmly and successfully operate to this day. So in the financial report of the company for 2003 it was said that ≈500 million copies of encryption programs were sold on the market. The resistance of the cipher to cracking is ensured by the impossibility of solving the ZFBCH for a practice acceptable (hours, days). This is confirmed by many years of attempts to factorize the numbers from the list and research in this area. But at the same time, it is not denied that when inventing a more advanced algorithm for solving the MFBCH or any other attacking algorithm (for example, keyless decryption), the cipher will not stand.
         If the principle of the algorithmization of the solution of the HFBCH remains the same, then the company by simply increasing the key length will extend the life cycle of the cipher, the speed of which, of course, will be worse, but will remain acceptable for some users.
         In this paper, we will not consider algorithms that solve the HFBCH for years. We will only say that they all use the ideas of numerical sieves, starting from the sieve of Eratosthenes, then Brun, Selberg, Linnik, Lenstra, etc. ... These algorithms have been consistently modified and improved over time over decades, and “things are still there.” The use of the theory of elliptic curves somewhat improves the situation, but does not lead to a radical change in the situation.
         I consider the named direction and approach as a whole to be a dead end. Improving the speed of calculators, parallelizing processes within the framework of the continuing principle will not improve the situation. Just the solution will become more expensive.

              Motivation for a new approach A

         promising way out of this situation is seen as follows. It is necessary to jointly consider the number and the area surrounding it, to jointly develop mathematical algorithms for solving the FBCH based on the properties of factorizable numbers and the number system, which would be free of the number of bits of numbers, not depend on their length. The properties of the numerical system cannot be ignored, which is quite clearly demonstrated by the author's "Law of Distribution of Divisors in the LDP". This is a new theoretical fundamental result. The law of distribution of dividers. The law indicates for any composite odd positive integer (SNP) where, in a limited area of ​​the NRF, its divisors or its multiples lie. Only if the above conditions are met, the algorithm can provide high speed, and the time t for obtaining a solution will not depend on the length of the number N.
         Confirmation of the potential capabilities of such algorithms are well-known signs of divisibility of numbers. So, the property of a number to have a convolution s (N) is the sum of the digits of a multiple of three does not depend on its length or this dependence is very weak. Numbers of arbitrary length with this property on a PC are divided by 3 almost instantly. Other properties, called the signs of divisibility, used in the factorization of N, provide a successful solution to finding private expansions. Unfortunately, the currently known properties of numbers and their systems do not provide a complete solution to the problem. On the other hand, they demonstrate the ability to close the factorization problem almost instantly in particular cases. In this, I see one of the hints to us from the side of the numerical system, about the possibilities of solving the ZFBCH hidden from us so far. Another hint is keyless decryption.
         Hence, the need arises and the need to search for new properties free of the length of the number and their use in the development of factorization algorithms. An example of such a new property is the new φ-invariant of the number found by the author. The new number invariant .

              Modeling and the basis of research

         In most mathematical studies of objects, mathematical models of objects play an important role. The development of such models for an individual number and their system (NRF) represents an independent direction in research. In the published works, the author proposed several different models of both the NRF and individual natural numbers.
         For the reader (not the gods who burn the pots), who wants to seriously tackle (not on his knee, as one of the commentators wrote) the problem of factorization of numbers, and possibly other objects (matrices, polynomials ...), the modeling approaches presented in the papers will be of great help and can serve initial examples.
         Where today you can read about the distribution of the divisors of the natural number in the LDP? Which of the famous mathematicians published materials about this? Where can primes be in the NRF, and where not? The area of ​​the ban . How can you simulate a natural series? How are the numbers of NRFs arranged? Classes of numbers
    These and other questions arose from the author, who had to look for answers, shoveling one might say mountains of literature from N. Bourbaki and multivolume encyclopedias to textbooks by creatively working authors. So far, it has not been possible to find answers to a number of questions, and some had to be created independently. Something was able to rigorously prove, something remains at the level of hypotheses.
         Perhaps, not all readers will find the presented results interesting and important. The author is convinced to whom it is interesting, the results will be very useful. I think that there’s simply nowhere else to read about it. These are new and original results. Those who are able to be objective can see and appreciate it.
         A series of published works sets out a specific knowledge base in a clearly defined field: NRF and its elements. After these publications, my students got the opportunity to more thoroughly get acquainted with the material that they presented verbally, or did not communicate at all. Among students, people with different levels of training include schoolchildren, students, graduates of universities, specialists with degrees and with academic degrees. First of all, my reaction to the text and their questions to the author matter to me. In our life there are things more important than ratings and karma, but in general I am grateful to Habr for the opportunity to place my texts with him.

              About the form and style of writing texts

          In the comments on my work, readers expressed comments, suggestions, advice and criticism. Thank you all for your attention to the work. I am not a programmer (I do not code algorithms in high-level languages), not an IT specialist. I am writing as I see fit and studying design. The style of presentation of the work I chose consciously. The desire to present the material is simple and accessible, even for a novice reader-researcher, and determined the elementary nature of the concepts, definitions and means used. This, of course, does not mean that everything in the texts is very simple. To assimilate the content and meaning of any work, the reader always requires some effort and time. The work presented to the reader’s attention is not an easy read, this is not a listing of interesting curious facts. A superficial familiarization with the work of some readers leaves a feeling of pseudoscience or nonsense in general. What can you do about it? I don’t even want to advise.
         Personal experience shows how difficult it is to delve into someone else's work if its author did not set himself the task of making it accessible and understandable to the reader, did not accompany him with a numerical example and still abuses the phrase “it follows easily ...”. Even P. Laplace once had to spend about two months on one such “it should be easy from here ...” to fill the gap.
         For myself, I think that the original texts of Euler or Newton are a good example of the presentation of sometimes difficult questions. Now they don’t write in this style. I recommend, if you're lucky, with a second-hand book dealer, open the old folio of these authors and look through it. You can skip the Latin in which the text is written, but the mathematical calculations are quite modern and cause admiration. In detail, even simple transformations are carried out leisurely, and, apparently, formulas are also commented on in Latin text.

    Also popular now: