Factorization of the number, problems of its theory and the position of the author
The problem of the factorization of numbers did not arise yesterday, it goes back thousands of years. One can only wonder why, in 1900, at the Mathematical Congress, D. Hilbert did not include it in his list of 23 problems, and later she did not make it into the list of unsolved mathematical problems of S. Ulam. The special attention and interest of mathematicians to the problem became apparent only in recent decades. Perhaps the impetus was the opening of a new direction - two-key cryptology, the emergence of public key ciphers. It can be assumed that today's interest in the problem of factorization of numbers is dictated by some uncertainty about the theoretical justification for the resistance to the disclosure of the very popular today two-key cipher (private key) RSA, which in principle can be broken without knowing the private key. Keyless decryption . It is just that the necessary results for this have not yet been found in the theory of algebraic rings. But there is an equally important aspect of this problem - the absence of an operation inverse to the multiplication of numbers. A simple, fast and affordable multiplicative decomposition of composite numbers can become such an arithmetic operation, and will replenish the arsenal of computational tools of mathematics.
Brief description of the current situation in the field of factorization
In order to clarify the situation today in the field of factorization of natural numbers (elements of the natural series of numbers (NPS)) and assess the possibilities of the current level of its resolution by RSA in 1991, a list of 42 test numbers of various digits from 100 to 617 decimal digits was formed and published later called the RSA numbers. The company invited everyone to try their hand and use mathematical training in solving the problem of factoring large numbers (SFC) from this list. To stimulate the activity of participants for each factorized number was awarded a prize. Under the conditions of such a competition, it was stipulated that all the numbers in the list were obtained by multiplying only two primes of almost the same digit capacity and that the difference of these factors is of the same order of magnitude (that is, numbers not close to each other). The “competition” lasted for more than two decades and has not yet been completed (the list of numbers has not been decomposed). Perhaps the "competition" will continue for more than one decade. To date, the decomposition results of a total of 13 first numbers of the list have been published. The largest of them is described by 232 decimal digits, the factors are formed by the 116th digit. Publication about this 2010.
')
Table 1 - Achievements in the field of factoring large numbers (RSA cipher comparison modules), the list of which was announced by RSA in 1991.
The analysis of almost 20-year 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 SFCS depend significantly on this property of the factorized number as its length. The longer the number, the more years it took to factor it.
After 10-15 years, the representatives of the company stopped worrying about the imminent collapse, they are quietly and successfully operating to this day. So in the financial report of the company for 2003, it was said that about 500 million copies of encryption programs were sold on the market. The cipher's resistance to cracking is ensured by the impossibility of resolving the SFCF in time acceptable for practice (hours, days). This is confirmed by many years of attempts to factor the numbers from the list and research in this area. But it does not deny that, with the invention of a more advanced algorithm for solving SFCP or some other attacking algorithm (for example, keyless decryption), the cipher will not stand.
If the principle of algorithmization of the ZFBCH solution remains the same, then the company will simply prolong the life cycle of the cipher by simply increasing the key length, the performance of which, of course, will be worse, but it will remain acceptable for some users.
In this paper, the algorithms that solve SFCS over the years will not be considered. We can only say that they all use the ideas of numerical sieves, starting from the sieve of Eratosthenes, then Bruna, Selberg, Linnik, Lenstra and so on ... These algorithms are consistently modified in time and improved over the course of decades, and now and there. Involving 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 a dead end. Increasing the speed of calculators, paralleling processes within the framework of the remaining 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 seems so. It is necessary to jointly consider the number and the surrounding area, jointly develop mathematical algorithms for solving SFCP based on the properties of the factorizable numbers and the numerical system that would be free from the digit capacity of the numbers, do not depend on their length. At the same time, the properties of the numerical system cannot be ignored, which is quite clearly demonstrated by the “Law of Distribution of Divisors in the NPS” opened by the author. This is a new theoretical fundamental result. The law of distribution of dividers . The law specifies for any composite odd natural number (snnch), where in the limited area of ​​the NPSH lie its divisors or multiples of them. Only when the above conditions are met, the algorithm will be able to provide high speed, and the time t to receive the solution will not depend on the length of the number N.
The potentialities of such algorithms are confirmed by the well-known signs of the divisibility of numbers. Thus, the property of a number to have a convolution s (N) is the sum of digits of a number that is 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 into 3 almost instantly. Other properties, called divisibility features, used in the factorization of N, provide a successful solution to finding private decompositions. 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 possibility to close the problem of factorization almost instantly in particular cases. In this, I see one of the hints to us from the side of the numerical system, the possibilities of solving the SFCF that are hidden from us so far. Another hint is keyless decryption. The frequency of the appearance of the source text is obvious, look for the period.
Hence the need and the need to search for new properties that are free from the number length and use them in the development of factorization algorithms. An example of such a new property is the new Φ-invariant of number found by the author. The new invariant of number .
Modeling and research basis
In most mathematical studies of objects, an important role is played by mathematical models of objects. The development of such models for an individual number and their system (NPS) represents an independent direction in research. The author in the published works proposed several different models of both the NPS and individual natural numbers.
The reader (not the gods burn the pots), who wants to seriously engage (not on the knee, as one of the commentators wrote) the problem of factorization of numbers, and possibly other objects (matrices, polynomials ...), the modeling approaches described in the works will greatly help and can initial examples.
Where today you can read about the distribution of the divisors of a natural number in the NPS? Who of the famous mathematicians published materials about it? Where in the NRCh can there be prime numbers, and where not? Prohibition area . How can you simulate a natural series? How are the numbers NRCH? Classes of Numbers
These and other questions arose for the author, who had to look for answers, shoveling, we can say, mountains of literature from N. Bourbaki and multi-volume encyclopedias to textbooks of creatively working authors. We have not yet managed to find answers to a number of questions, and some had to create answers on our own. Something was able to strictly prove something remains at the level of hypotheses.
Perhaps not all readers of the presented results will seem interesting and important. The author is convinced to those who are interested, the results will be very useful. I think that for the time being there is simply nowhere to read about it. These are new and original results. Anyone who can be objective can see and appreciate it.
The series of published works sets forth a certain knowledge base in a well-defined area: the NPS and its elements. After these publications, my students had the opportunity to more thoroughly get acquainted with the material that was presented to them orally or not at all. Among students there are schoolchildren, students, university graduates, specialists with degrees and academic degrees. First of all, their reaction to the text and their questions to the author matter for me. In our life there are things more important than ratings and karma, and in general I am grateful to Habra for the opportunity to place his texts with him.
On the form and style of writing texts
In the comments to my work, readers made comments, suggestions, advice and criticism. I thank everyone for their attention to the work. I am not a programmer (I do not encode algorithms in high-level languages), not an IT program. I write as I see fit and learn design. The style of presentation of the work I chose deliberately. The desire to present the material is simple and accessible even for the novice reader-researcher and has 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 from the reader always requires some effort and time costs. Offered to the attention of the reader of the work are not easy reading, this is not a listing of interesting and interesting facts. Superficial familiarization with the work of some readers leaves a general feeling of pseudoscience or nonsense. What can you do about it? I do not 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 for the reader, did not accompany a cross-cutting numerical example, and still misuses the phrase "it follows easily from here ...". Even P. Laplace once had to do with one such “from here it’s easy ...” to spend about two months to fill the gap.
For myself, I think that a good example of the presentation of sometimes not simple questions are the original texts of Euler or Newton. Now they don't write in this style. I recommend, if you're lucky, in a second-hand bookseller, open the old folio of these authors and look through it. Latin, on which the text is written, you can skip, but the mathematical calculations are quite modern and cause admiration. Even simple transformations are carried out in detail, and, apparently, formulas are also commented in Latin text.
Brief description of the current situation in the field of factorization
In order to clarify the situation today in the field of factorization of natural numbers (elements of the natural series of numbers (NPS)) and assess the possibilities of the current level of its resolution by RSA in 1991, a list of 42 test numbers of various digits from 100 to 617 decimal digits was formed and published later called the RSA numbers. The company invited everyone to try their hand and use mathematical training in solving the problem of factoring large numbers (SFC) from this list. To stimulate the activity of participants for each factorized number was awarded a prize. Under the conditions of such a competition, it was stipulated that all the numbers in the list were obtained by multiplying only two primes of almost the same digit capacity and that the difference of these factors is of the same order of magnitude (that is, numbers not close to each other). The “competition” lasted for more than two decades and has not yet been completed (the list of numbers has not been decomposed). Perhaps the "competition" will continue for more than one decade. To date, the decomposition results of a total of 13 first numbers of the list have been published. The largest of them is described by 232 decimal digits, the factors are formed by the 116th digit. Publication about this 2010.
')
Table 1 - Achievements in the field of factoring large numbers (RSA cipher comparison modules), the list of which was announced by RSA in 1991.
The analysis of almost 20-year 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 SFCS depend significantly on this property of the factorized number as its length. The longer the number, the more years it took to factor it.
After 10-15 years, the representatives of the company stopped worrying about the imminent collapse, they are quietly and successfully operating to this day. So in the financial report of the company for 2003, it was said that about 500 million copies of encryption programs were sold on the market. The cipher's resistance to cracking is ensured by the impossibility of resolving the SFCF in time acceptable for practice (hours, days). This is confirmed by many years of attempts to factor the numbers from the list and research in this area. But it does not deny that, with the invention of a more advanced algorithm for solving SFCP or some other attacking algorithm (for example, keyless decryption), the cipher will not stand.
If the principle of algorithmization of the ZFBCH solution remains the same, then the company will simply prolong the life cycle of the cipher by simply increasing the key length, the performance of which, of course, will be worse, but it will remain acceptable for some users.
In this paper, the algorithms that solve SFCS over the years will not be considered. We can only say that they all use the ideas of numerical sieves, starting from the sieve of Eratosthenes, then Bruna, Selberg, Linnik, Lenstra and so on ... These algorithms are consistently modified in time and improved over the course of decades, and now and there. Involving 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 a dead end. Increasing the speed of calculators, paralleling processes within the framework of the remaining 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 seems so. It is necessary to jointly consider the number and the surrounding area, jointly develop mathematical algorithms for solving SFCP based on the properties of the factorizable numbers and the numerical system that would be free from the digit capacity of the numbers, do not depend on their length. At the same time, the properties of the numerical system cannot be ignored, which is quite clearly demonstrated by the “Law of Distribution of Divisors in the NPS” opened by the author. This is a new theoretical fundamental result. The law of distribution of dividers . The law specifies for any composite odd natural number (snnch), where in the limited area of ​​the NPSH lie its divisors or multiples of them. Only when the above conditions are met, the algorithm will be able to provide high speed, and the time t to receive the solution will not depend on the length of the number N.
The potentialities of such algorithms are confirmed by the well-known signs of the divisibility of numbers. Thus, the property of a number to have a convolution s (N) is the sum of digits of a number that is 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 into 3 almost instantly. Other properties, called divisibility features, used in the factorization of N, provide a successful solution to finding private decompositions. 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 possibility to close the problem of factorization almost instantly in particular cases. In this, I see one of the hints to us from the side of the numerical system, the possibilities of solving the SFCF that are hidden from us so far. Another hint is keyless decryption. The frequency of the appearance of the source text is obvious, look for the period.
Hence the need and the need to search for new properties that are free from the number length and use them in the development of factorization algorithms. An example of such a new property is the new Φ-invariant of number found by the author. The new invariant of number .
Modeling and research basis
In most mathematical studies of objects, an important role is played by mathematical models of objects. The development of such models for an individual number and their system (NPS) represents an independent direction in research. The author in the published works proposed several different models of both the NPS and individual natural numbers.
The reader (not the gods burn the pots), who wants to seriously engage (not on the knee, as one of the commentators wrote) the problem of factorization of numbers, and possibly other objects (matrices, polynomials ...), the modeling approaches described in the works will greatly help and can initial examples.
Where today you can read about the distribution of the divisors of a natural number in the NPS? Who of the famous mathematicians published materials about it? Where in the NRCh can there be prime numbers, and where not? Prohibition area . How can you simulate a natural series? How are the numbers NRCH? Classes of Numbers
These and other questions arose for the author, who had to look for answers, shoveling, we can say, mountains of literature from N. Bourbaki and multi-volume encyclopedias to textbooks of creatively working authors. We have not yet managed to find answers to a number of questions, and some had to create answers on our own. Something was able to strictly prove something remains at the level of hypotheses.
Perhaps not all readers of the presented results will seem interesting and important. The author is convinced to those who are interested, the results will be very useful. I think that for the time being there is simply nowhere to read about it. These are new and original results. Anyone who can be objective can see and appreciate it.
The series of published works sets forth a certain knowledge base in a well-defined area: the NPS and its elements. After these publications, my students had the opportunity to more thoroughly get acquainted with the material that was presented to them orally or not at all. Among students there are schoolchildren, students, university graduates, specialists with degrees and academic degrees. First of all, their reaction to the text and their questions to the author matter for me. In our life there are things more important than ratings and karma, and in general I am grateful to Habra for the opportunity to place his texts with him.
On the form and style of writing texts
In the comments to my work, readers made comments, suggestions, advice and criticism. I thank everyone for their attention to the work. I am not a programmer (I do not encode algorithms in high-level languages), not an IT program. I write as I see fit and learn design. The style of presentation of the work I chose deliberately. The desire to present the material is simple and accessible even for the novice reader-researcher and has 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 from the reader always requires some effort and time costs. Offered to the attention of the reader of the work are not easy reading, this is not a listing of interesting and interesting facts. Superficial familiarization with the work of some readers leaves a general feeling of pseudoscience or nonsense. What can you do about it? I do not 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 for the reader, did not accompany a cross-cutting numerical example, and still misuses the phrase "it follows easily from here ...". Even P. Laplace once had to do with one such “from here it’s easy ...” to spend about two months to fill the gap.
For myself, I think that a good example of the presentation of sometimes not simple questions are the original texts of Euler or Newton. Now they don't write in this style. I recommend, if you're lucky, in a second-hand bookseller, open the old folio of these authors and look through it. Latin, on which the text is written, you can skip, but the mathematical calculations are quite modern and cause admiration. Even simple transformations are carried out in detail, and, apparently, formulas are also commented in Latin text.
Source: https://habr.com/ru/post/226395/
All Articles