Get best of the week

A model of a natural series of numbers and its elements. Multiple Row Cells




In another work from a series of articles on the natural series of numbers (NRF), the concepts and notation G 2 ± are used - the NRF model in the form of a discrete (from cells with coordinates (x1, xo)) infinite plane ( see here ), in which the composite is even or the odd natural number (VLF) in each cell of the model is described by the relation N = x1 2 ± xo 2 . We consider another important property of the Natural Series of Numbers, the multiplicity of model cells, to the RSA cipher module, which is important for solving the problem of factorization of large numbers (ZFBCH).

About algebraic rings and the RSA cipher


The cipher RSA and the like is basically based on a strict mathematical construction - a finite numerical residue ring (KCHKV) modulo a composite number N = dmdb, where dm is a smaller prime divisor, db is a larger divisor.

The requirement for the key (in particular, to the N module) of the cipher is that both divisors should be primes of very high capacity (up to 300 decimal digits). see here

Another important requirement for a cipher key is the requirement for the difference of the divisors
| db - dm | = Δ. It should have the same high capacity as the dividers themselves. A simple example of the KPKV is the initial fragment of a natural series of numbers with the addition of a zero element. All numbers in a row form a ring from 0 to N - 1. More details about rings can be found in textbooks on higher algebra.

The resistance of the RSA cipher to key disclosure is estimated as very high and all the efforts of cryptanalysts in the world to crack the cipher since its publication (1978) have not been successful so far. There are a number of reasons for this situation.

The published algorithms for implementing attacks on the cipher are based on the concept of a numerical sieve proposed by Eratosthenes before the new era. With each new publication, we see a slightly improved, improved version of the algorithm, but, apparently, these improvements are not enough to succeed. The idea of ​​the sieve of Eratosthenes [1] was progressive in his time, but now it does not work.

On the Internet there is a list of RSA numbers that the company is invited to factorize. The list was published in 1991, and it is far from complete. An analysis of the results of the multiplicative decomposition of numbers from the list is available, as the numbers themselves are open to all.

From the analysis it follows that the more digits in the description of the number, the more time was required for its decomposition. The conclusion is that the decomposition of the module N uses algorithms that are very sensitive to the capacity of numbers, that is, the algorithms use the properties of numbers that are very dependent on their capacity. I mean properties like the "signs of divisibility" of numbers. They practically do not depend on the bit depth of the factorizable number ( see here ).

Published works are limited, as a rule, to the processing of the number itself, ignoring its environment, the properties of near and distant neighbors within a specific number system. Very high hopes of the authors and expectations are assigned to new computing devices: quantum, photon, molecular, and the like.

Authors of publications and owners of the company, i.e. encryption algorithms do not deny other new approaches, and do not exclude the possibility of creating new algorithms based on new ideas, for which the task of factorization of large numbers will not stand and its solution will be successful. I, as the author of this publication, are attracted by just new original developments in the field of solving the WFCH.

Most of my publications are devoted to just new approaches, starting with the synthesis of models of the natural series of numbers, studying their properties and using such properties in the development of new original algorithms for solving the ZFBCH. Moving in this direction, it was possible to establish (open) the Law of Distribution of Divisors (RDA) of the number N in the NRCh RDA .

Verticals (columns) G 2 ± - NRF models


An example of such a new approach is the use of sums of pairs of squared numbers. These numbers are taken from the NRF and must satisfy the requirements: two numbers are adjacent and their sum is equal to the composite number N that we want to factor, two more numbers are squares satisfying the equation N + x1 2 = xo 2 .

Another requirement: the sum of the squares of adjacent numbers of the additive decomposition with the two squares found must have equal (matching) values ​​( see here ). If it is possible to fulfill the above requirements, then factorization of N is guaranteed. Example 1 below illustrates this possibility.

The considered scheme is original, differs from the one proposed by L. Euler and other mathematicians in a simpler and more transparent understanding.

Example 1 . ( Sum of squares ). The composite number N = dmdb = 209723 is given. It is required to find its multiplicative decomposition, that is, the values ​​of the factors dm and db.
Solution . We use the properties of the sums of squares in 2+ - the hyperbolic-circular model.

We take the square root of N, √209723 = 457.955 = 458 and round to a larger integer.
Next, we find the differences of the following squares and the number N with checking the equality of this difference to the full square: 458 2 - 209723 = 41 ≠ ▢, 459 2- 209723 = 958 ≠ ▢, 460 2 - N ≠ ▢,
461 2 - N ≠ ▢,

462 2 - 209723 = 3721 = 61 2 = ▢. At the 5th step, the desired difference is equal to the full square. We find the additive decomposition of N = 209723 = sm + sb = 104861 + 104862 into adjacent terms. Check the equality of the sum of squares in the cells of the model
N (x11, xo) = N (x11, sm), N (x12, xo2) = N (x12, sb),
where sm, sb are the column numbers, and x11 and x12 are the row numbers , models. These numbers are determined from the equality relations of the sums of squares.

sm 2 + 462 2 = 104861 2 + 213444 = 10995829321 + 213444 = 10996042765;
sb 2 + 61 2 = 104862 2 + 3721 = 10996039044 + 3721 = 10996042765. The amounts in the cells, as expected, turned out to be equal to each other.

For such sums, we write the equality sm 2 + 462 2 = sb 2 + 61 2 and transform it into the equality of the difference of squares 462 2 - 61 2 = sb 2 - sm 2 . On the right, the difference of the squares is always equal to N, and the left difference is converted to the product
462 2 -61 2 = (462 - 61) (462 + 61) = 401 · 523 = 209723 = N.

Both factors are prime numbers, i.e. factorization of the number N is completed successfully. The disadvantage of this approach is the need to find the sum of squares with matching values ​​in adjacent columns of the model. With large numbers, this is a rather time-consuming operation. In essence, this task is reduced to the selection of such a square, which, when summed with the number N, gives a larger square.

Horizontal (rows) G 2- - low-frequency models


Working with numbers, solving urgent problems like HFBCH or the discrete logarithm suggests that the researcher somehow ordered and classified numbers ( here ) and does not work blindly, not at random, but predicts the expected result, based on the hypotheses about the result.

One of the properties of the rows (horizontals) of the G 2- - NRF model is the linear dependence of the values ​​of each cell of the next model line on the values ​​in the cells of the previous one, which is expressed by simple summation of the values ​​from the cells of the upper of two adjacent rows with a constant value from the last cell of the lower row is
N (x1, xo) = N (h1-1 ho) + N (x1, x1 - 1), ho runs while the entire bottom line (see Table 1) Clickable



Figure 1-Values ​​that are multiples of the composite odd numbers in the first 100 (highlighted by a fill)
The figure shows cells filled with a fill with numbers equal to the product of the numbers of the diagonals.

The peculiarity of these numbers is that the numbers of the diagonals in the CCCH modulo N, considered as elements of the ring, when they are displayed (squaring) and the result is modulo the rings remain themselves (fixed elements).

The first number as the module is N = 15. For it, the multiple cell contains the product of the numbers of the diagonals 10 · 6 = 60 = 15 · 4 multiple of the module with the coefficient k = 4. For the numbers of the diagonals: 6 2 ≡ 6 (mod15); 10 2 ≡ 10 (mod15).

Take the second number as the module N = 35. For it, the multiple cell contains the product of the numbers of the diagonals 21 · 15 = 315 = 35 · 9 multiple of the module with a coefficient k = 9. For the numbers of the diagonals: 15 2 ≡ 15 (mod35);
21 2 ≡ 21 (mod35). So it will be for all numbers N belonging to the long diagonal D1, in the line of which the multiple N cell is indicated by filling.

Example 2. ( Calculation of a multiple cell ). The composite KChKV module N = 77 is set. according to properties 1,2, the value in the cell N (x1 = 39, xo = 17) is calculated as the sum of the values ​​in the cell above the given and in the last cell of the row x1 = 39 equal to the CCFV modulus.
N (x1, xo) = N (x1 = 39, xo = 17) = N (38, 17) + N (39, 39 - 1) => 1232 = 1155 +77.
N (x1, xo) = N (x1 = 39, xo = 17) = N (38, 17) + N (39, 39 –1) = 38 2 - 17 2 + 39 2 - 38 2 => 1232 = 1155 +77.

On the other hand, the value in each cell of an arbitrary row is calculated as the difference of the squares of the coordinates of the cell or as the product of the difference of the coordinates of the cell and their sum
N (x1, xo) = N (x1 = 39, xo = 17) = 39 2 - 17 2 = ( 39 - 17) (39 + 17) = 22.56 = 1232 = 16.77.

There are other less obvious ways to calculate the value in the cell.

The considered example is remarkable in that it establishes a formalized connection of the model under consideration with a finite numerical ring of residues by the composite module.

It is known that the long first diagonal 2 ± is the NRF model. contains in its cells all the following numbers, odd in a row, which can be considered as modules for reducing algebraic structures. The structures themselves are formed from elements - natural numbers. Here we will not delve into the concepts of higher algebra, but we will indicate only facts that are interesting from the point of view of their representation in the G 2 - - model of NRF.

Among all the elements of the QPCW structure modulo N, there is a set I = {x}, which are called idempotents, and whose squares, after reduction (modulo reduction), retain their valuesx 2 ≡ x (mod N). Such elements are called motionless in the theory of mappings. Further, we will denote idempotents by the symbols I1, II, ...

Another class of elements, the set H = {x} of the QCF, called involutions, has the following property x 2 ≡ 1 (mod N). Further, we will denote involutions by the symbols 1, 2, ...

The role of such ring elements is very great in solving applied problems, and here we will consider some interesting and useful facts for solving the HFBC. The fact is that the theory of rings does not answer the question which of the elements of the ring are idempotents, which are involutions. How to establish these elements, how to determine their values, for a given module N of the ring.

It turns out that idempotents are, in addition, elements that are multiples of different divisors of module N. Their product modulo is zero, since it is a multiple of N, but the sum of two idempotents is equal to N + 1. Having the idempotent value, we can solve the problem of finding the greatest common factor (common both for the module and for idempotent).

And from here it’s not far to solving the problem of factorization of the ring module, which will ensure that the private key of the asymmetric cipher is found and the attack on such a cipher is successful.

The considered example with a cell having a value that is a multiple of the value in the rightmost cell of the row (a multiple of the cell) has the peculiarity that the product of the diagonals in the multiple of the cell is the product of the idempotents of the ring.

Factorization of N using idempotents of a finite number ring


VLF N. Factorization Schemes. Use of KPKV idempotents.
All ( 1 , ) G 2 - cells are unique and are combined in lines: horizontal with numbers 1 (they contain number 1 cells), verticals with numbers 1, diagonals: short (K) with numbers x1 + xo and long (D) with numbers x1 - xo.

In each cell (x1, xo) of the model, lines of the named types intersect, the numbers of which are determined by the coordinates of the cell. The cells of the model may contain not any numbers, but only representable differences of the squares of other numbers (coordinates).

The horizontal of the model can be set by its number x1, and the vertical by the number xo, respectively. Each cell contains the number N (x1, xo) = x1 2 - xo 2. The last horizontal cells form a long diagonal D1 and contain the values

N (x1, x1 - 1) = x1 2 - x1 2 + 2x1–1 = 2x1 - 1,

depending on the horizontal number. The cells of this diagonal contain all the following odd numbers in a row. For the range of numbers [d1min, d1max], d1min, d1max ∊ D1, the sum of their values ​​determines the additive form of the number N.

Example 3 ( Calculation of the kN value of a multiple cell as the sum of the elements of a fragment of the diagonal D1 )

= 77 + 75 + 73+ ... + 37+ 35 = 1232 = 16 · 77 = 22 · 56 ,
where i = 1 (1) 22 . The latter means that the number of terms (22) in total is equal to a smaller divisor


N (x1, xo), and the average term (56) is the larger divisor of N (x1, xo).

If the cells of the main To diagonal G 2 ± - model with the equation x1 = xo are included in the G 2 - - model, then the value in them will be zero. Then, when generating values ​​in the cells of the row with the number x1 in its last cell, we get the value 2x1–1, since it sums up with the value from the cell of the row with the number x1–1 located above it and this value is 0. Important properties of G 2 - - The model and its cells are as follows.

Property 1. All numbers in the cells of the current horizontal x1 can be obtained from the numbers in the corresponding cells of the previous (upper) horizontal with the number x1 - 1 by summing their values ​​with a constant value of 2x1 - 1.

Table 1 - Fragment G 2 - - models of 2 lines 38th and 39th, N = 77



Indeed, N (x1, xo) = N (x1 –1, xo) + 2x1 - 1 = x1 2 - 2x1 + 1+ 2x1 - 1– xo 2 = x1 2 - ho 2 .

Property 2. The second property follows from the first. Any number N (x1, xo) in the horizontal cell with the number x1 can be obtained as the sum of the values ​​in the cells of the fragment of the long diagonal D1, of which the larger d1max is the number in the last horizontal cell x1, and the smaller d1min is the number in the cell intersecting the diagonal D1 with vertical ho.

Property 3 . For a squared VLF N placed in the extreme right cell of the horizontal x1, in this horizontal there is a cell in which a multiple of N will be placed, that is, the number kN, k> 1. Searching for such a cell is a nontrivial problem that is difficult to solve.

An illustration of this property is the data in Table 2. For numbers of the first hundred that are squareless and composite N, placed in cells d1∊ D1 with a value of 2x1 - 1, another cell (x1, xo) containing the value N (x1, xo) = kd1 is a multiple d1.

Table 2.


K · D is the product of the diagonals intersecting in the cell with the value of kN.

Property 4 . All numbers N (x1, xo) in the cells of the current horizontal x1 can be obtained as the product of the numbers of the diagonals a = x1 + xo short and b = x1 - xo long, intersecting in these cells.

It is convenient to illustrate the properties with a numerical example.
Example 4 . We will consider 2 -- model. We set N = pq = 7 · 11 = 77 for factorization of the ELF. This is an odd number and for it there is a cell in the long diagonal D1 that lies horizontally with the number x1 = ½ (N + 1) = 39.

The number 77 itself is placed in the last cell of this horizontal, containing, like all other cells, the difference of the squares of the coordinates x1 2 - xo 2 .

The first cell of this horizontal in the vertical xo = 0 is occupied by the number
x1 2 = 39 2 = 1521. The value of the number in any intermediate cell of the horizontal x1 is, on the one hand, the product of the numbers b = x1 - xo long and short a = x1 + xo diagonals, the intersecting ab = (x1 + xo) (x1 - xo) in it.

On the other hand, it is equal to the difference between the squares of the horizontal numbers (for all horizontal cells this square x1 2 is the same) and the vertical xo 2 , which also intersect in this intermediate cell, i.e.
N (x1, xo) = x1 2 - xo 2 .

In addition, all values ​​in the horizontal cells x1 (by property 1) are equal to the sum of the values ​​N (x1, xo) = N (x1 - 1, xo) + 77 of the corresponding horizontal cells with the number x1 - 1, i.e. from the upper one above it and a constant equal to N = 77.

Suppose that for the numbers of the diagonals the value x1 + xo = I1 = 56 is chosen for the short and for the long one the value x1 is xo = I2 = 22, that is, values ​​of nontrivial idempotents of the residue ring modulo N.

When we multiply nontrivial idempotents as the diagonals of the G 2 - - model, we get in some horizontal cell (with the number x1 = 39) as their product the number multiple of the residue ring modulus (77), which is located in the last cell of this horizontal, i.e. I1 · I2 = 56 · 22 = kN = 16 · 77 = 1232.

It is also known from the theory of rings that the sum of non-trivial idempotents is equal to 1 + 2 = N + 1. Thus, with respect to unknown idempotents, we obtain an algebraic system of equations, which, in addition to two unknown idempotents, also contains a third unknown - multiplicity coefficient k> 1.



Fortunately, the coefficient k can be determined outside the system of algebraic equations. Suppose that the coefficient k is already determined by us k = 16. Then we solve the system of equations.



The last term in the quadratic equation must be made the square of 39. To do this, add the number 289 = 17 2 to the left and right sides of the equation . Then we get
(I2 - 39) 2 = 17 2 or I2 - 39 = ± 17 and finally, I2 = 17 + 39 = 56 or I2 = 39 - 17 = 22.
Answer: Idempotents are equal to I2 = 22; I1 = 56 or vice versa: I2 = 56 and I1 = 22.

Now we return to the question of determining the value of the coefficient of multiplicity k.
Consider the following algorithm for determining the coefficient of multiplicity of module N.

Algorithm

1. A composite number N = 77 is given — the module of the residue ring;

2. Determine by N the value of the horizontal number x1 = ½ (77+ 1) = 39, in the first cell
which we put a square 39 2 = 1521, and in its last cell we put N = 77;

3. The product of idempotents appears in the intermediate horizontal cell x1 = 39; for this cell, the condition is satisfied that the number in it is equal to kN, and it is representable by the difference of the squares of the natural numbers.

4. Therefore, subtracting repeatedly from the square of the number of the first horizontal cell 39 2 = 1521 the values ​​x0 = 1,2,3, ... successively, each time we determine the value of k, and is it an integer? As soon as the difference becomes a multiple of N, the problem is solved: kN is found.

Let us also consider another algorithm for determining the coefficient of multiplicity of the module N.

1. A composite number N = 77 — the module of the residue ring;

2. Determine by N the value of the horizontal number x1 = ½ (77+ 1) = 39, in the first cell of
which we put the square 39 2 = 1521, and in its last cell we put N = 77;

3. The product of idempotents appears in the intermediate cell of the horizontal x1; for this cell, the condition is satisfied that the number in it is equal to kN, and it is representable by the difference of the squares of the natural numbers.

Using property 2, the number kN can be found by the path indicated there, namely, by summing monotonously decreasing odd numbers from a fragment of the diagonal D1 starting with d1max = 77 and ending with d1min, the value of which is a priori unknown, d1min, d1max ∊ D1.

4. To establish the last term after each step of summing, the divisibility of the sum obtained is checked by N = 77. The solution is the sum divisible by 77.

Table 3 - N numbers are multiples of 3 on the center line (the forecast is highlighted by filling)



In this table are composite numbers (multiples three) follow with alternating gaps of 6 and 12. Indeed, in line N we have 21 - 15 = 6, and 33 - 21 = 12 and further in the same order. Presumably the gaps between the tabular values ​​of N are due to the fact that in the six adjacent numbers there are twin primes, for example, 16, 17, 18, 19, 20.

The next multiple of three 21 is just the sixth in a row after 15. Either in 12 consecutive numbers, pairs of twin primes are possible, for example, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, or squares 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 are mixed with simple twins. In general, the choice is made with the guarantee not to run into a non-composite number in a position corresponding to a multiple of three.

Namely, such a condition ensures the reliability of the forecast far ahead. The missing numbers turn out to be multiples of not only three, but also large prime numbers, which allows them to be considered from other positions.

List of publications

1.Stechkin B.S., Matiyasevich Yu.V. Sieve of Eratosthenes // Proceedings of the international school of S.B. Stechkina on the theory of functions. - Yekaterinburg, 1999. - p. 148.

More articles:


All Articles