Factorization of numbers (option 2)

I would like to bring to your attention one of the variants of the composite number factorization algorithm.

To simplify, we consider the matrix of residuals of the composite number A = 35 , as well as in [1], presented in Fig. 1.

As already mentioned [1], the table of power residues of the composite number A (Fig. 1) has certain features.
')

34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one	34	one
33	four	27	sixteen	3	29	12	eleven	13	9	17	one	33	four	27	sixteen	3	29	12	eleven	13	9	17	one	33	four	27	sixteen	3	29	12	eleven	13	9
32	9	eight	eleven	2	29	18	sixteen	22	four	23	one	32	9	eight	eleven	2	29	18	sixteen	22	four	23	one	32	9	eight	eleven	2	29	18	sixteen	22	four
31	sixteen	6	eleven	26	one	31	sixteen	6	eleven	26	one	31	sixteen	6	eleven	26	one	31	sixteen	6	eleven	26	one	31	sixteen	6	eleven	26	one	31	sixteen	6	eleven
thirty	25	15	thirty	25	15	thirty	25	15	thirty	25	15	thirty	25	15	thirty	25	15	thirty	25	15	thirty	25	15	thirty	25	15	thirty	25	15	thirty	25	15	thirty
29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one	29	one
28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14
27	29	13	one	27	29	13	one	27	29	13	one	27	29	13	one	27	29	13	one	27	29	13	one	27	29	13	one	27	29	13	one	27	29
26	eleven	6	sixteen	31	one	26	eleven	6	sixteen	31	one	26	eleven	6	sixteen	31	one	26	eleven	6	sixteen	31	one	26	eleven	6	sixteen	31	one	26	eleven	6	sixteen
25	thirty	15	25	thirty	15	25	thirty	15	25	thirty	15	25	thirty	15	25	thirty	15	25	thirty	15	25	thirty	15	25	thirty	15	25	thirty	15	25	thirty	15	25
24	sixteen	34	eleven	nineteen	one	24	sixteen	34	eleven	nineteen	one	24	sixteen	34	eleven	nineteen	one	24	sixteen	34	eleven	nineteen	one	24	sixteen	34	eleven	nineteen	one	24	sixteen	34	eleven
23	four	22	sixteen	18	29	2	eleven	eight	9	32	one	23	four	22	sixteen	18	29	2	eleven	eight	9	32	one	23	four	22	sixteen	18	29	2	eleven	eight	9
22	29	eight	one	22	29	eight	one	22	29	eight	one	22	29	eight	one	22	29	eight	one	22	29	eight	one	22	29	eight	one	22	29	eight	one	22	29
21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21
20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15
nineteen	eleven	34	sixteen	24	one	nineteen	eleven	34	sixteen	24	one	nineteen	eleven	34	sixteen	24	one	nineteen	eleven	34	sixteen	24	one	nineteen	eleven	34	sixteen	24	one	nineteen	eleven	34	sixteen
18	9	22	eleven	23	29	32	sixteen	eight	four	2	one	18	9	22	eleven	23	29	32	sixteen	eight	four	2	one	18	9	22	eleven	23	29	32	sixteen	eight	four
17	9	13	eleven	12	29	3	sixteen	27	four	33	one	17	9	13	eleven	12	29	3	sixteen	27	four	33	one	17	9	13	eleven	12	29	3	sixteen	27	four
sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen	eleven	one	sixteen
15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15
14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21
13	29	27	one	13	29	27	one	13	29	27	one	13	29	27	one	13	29	27	one	13	29	27	one	13	29	27	one	13	29	27	one	13	29
12	four	13	sixteen	17	29	33	eleven	27	9	3	one	12	four	13	sixteen	17	29	33	eleven	27	9	3	one	12	four	13	sixteen	17	29	33	eleven	27	9
eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven	sixteen	one	eleven
ten	thirty	20	25	five	15	ten	thirty	20	25	five	15	ten	thirty	20	25	five	15	ten	thirty	20	25	five	15	ten	thirty	20	25	five	15	ten	thirty	20	25
9	eleven	29	sixteen	four	one	9	eleven	29	sixteen	four	one	9	eleven	29	sixteen	four	one	9	eleven	29	sixteen	four	one	9	eleven	29	sixteen	four	one	9	eleven	29	sixteen
eight	29	22	one	eight	29	22	one	eight	29	22	one	eight	29	22	one	eight	29	22	one	eight	29	22	one	eight	29	22	one	eight	29	22	one	eight	29
7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14
6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one	6	one
five	25	20	thirty	ten	15	five	25	20	thirty	ten	15	five	25	20	thirty	ten	15	five	25	20	thirty	ten	15	five	25	20	thirty	ten	15	five	25	20	thirty
four	sixteen	29	eleven	9	one	four	sixteen	29	eleven	9	one	four	sixteen	29	eleven	9	one	four	sixteen	29	eleven	9	one	four	sixteen	29	eleven	9	one	four	sixteen	29	eleven
3	9	27	eleven	33	29	17	sixteen	13	four	12	one	3	9	27	eleven	33	29	17	sixteen	13	four	12	one	3	9	27	eleven	33	29	17	sixteen	13	four
2	four	eight	sixteen	32	29	23	eleven	22	9	18	one	2	four	eight	sixteen	32	29	23	eleven	22	9	18	one	2	four	eight	sixteen	32	29	23	eleven	22	9
one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one	one

Fig. 1 Table of power residues of the composite number A = 35 .

If we exclude rows whose values ​​are multiples of the divisors of the number A , then there will necessarily be two columns in which the remaining values ​​are 1 . In fig. 1 is the columns with numbers 12 , 24 .

Of these two columns, the largest column number is equal to the product (x - 1) by (y - 1) , where x and y are divisors of the number A. It should be noted that in this case, the column number 24 is equal to the value of the Euler function [2], the value of which is
(x - 1) * (y - 1) = ѱ (n) .

The difference between the number A and the Euler function ѱ (n) is (x + y - 1) .

These patterns allow us to make a system of equations.

Ѱ (n) = (x - 1) * (y - 1)
A - ѱ (n) = (x + y - 1)
Formula 1)

Using substitutions, the system of equations (1) can be reduced to a quadratic equation (2).

y ² - (A - ѱ (n) + 1) y + A = 0
Formula (2)

To successfully solve this equation, only (n) is missing.

We consider additionally the properties of the power residuals of the number A of the table (Fig. 1). We introduce the concept of inverse value [3]. If you choose the value of c from the range of numbers (1, A - 1) , so that c does not have multiple divisors of x and y , then there is always the value d , from the same range (1, A - 1) , such that

c * d ≡ 1 (mod A)
Formula (3)

those. c * d = nA + 1 , where n can take values ​​from 1 to (A - 2) .

We introduce the notation d = inv (c) , i.e. d is equal to the inverse of c . For a composite number A , equal to the product of simple factors x and y , the number of pairs of inverse values ​​is

(A - (x - 1) - (y - 1) - 1) / 2
Formula (4)

The inverse values, in the rows of the table (Fig. 1), are located symmetrically with respect to the column with the number ѱ (n) .

The inverse values, in the columns of the table (Fig. 1), are arranged symmetrically with respect to pairs of inverse values ​​in the first column.

Consider the sequence of actions to find ѱ (n) .

1. Reduce the search range. From (A - 1) we subtract the value of the square root of A , calculated up to integer. The result is denoted by ₁ .

2. Choose a number c , not a multiple of the divisors x , y of the number A. It is desirable that the power residues of c have the minimum number of duplicate values.

3. Find the number d = inv (c) . You can find it using the advanced Euclidean algorithm [4].

4. Find the power residues for d , starting with exponent 1 and ending with some number m , less than or equal to the square root of A.

5. We put the power residues found in the array; we denote it by M. The array M is sorted in ascending order and indexed by exponent.

6. Calculate the remainder of c to the power ѱ ₁ divided by A and compare with the values ​​of M.

7. In the absence of coincidence, from ₁ subtract m and assign the resulting value to ѱ ₁ . Next, repeat paragraph 6 and 7 until a match appears.

8. In the presence of coincidences, from ѱ _{1 we} subtract the value of the index of the degree that matched the values ​​of the array M , assign the resulting value to ₁ .

In this case, ѱ ₁ = ѱ (n) .

Here is how it works. From (A - 1) = 34 (Fig. 1) we take away the square root of 35 , i.e. 5 , we get 29 . As c, select 18 . Find inv (18) = 2 . If m = 5 , then the array M = {2, 4, 8, 16, 32} . The remainder of 18 , to the power of 29 , divided by 35 , is 23 . inv (23) = 32 . This value is in the array and the index is 5 . From 29 you need to subtract 5 . The resulting value of 24 is ѱ (n) . Next, we substitute A and ѱ (n) into formula (2) and find y . y ₁ = 7 , y ₂ = 5 .

Another example.

2 to the 11th degree, minus 1 equals 2047.
2047 = 23 * 89
2047/3 = 682 and the remainder 1
c = 682, inv (c) = 3
The square root of 2047 = 45, the remainder 22.
2047 - 45 = 2002
m = 20
M = {3, 9, 27, 81, 243, 729, 140, 420, 1260, 1733, 1105, 1268, 1757, 1177, 1484, 358, 1074, 1175, 1478, 340}
682 to the power of 2002 divided by 2047, the remainder 1013. inv (1013) = 1657, there are no matches in the array,
2002 - 20 = 1982
682 to the power of 1982 divided by 2047, the remainder 524. inv (524) = 1504, there are no matches in the array,
1982 - 20 = 1962
682 to the power of 1962 divided by 2047, the remainder 71. inv (71) = 173, there are no matches in the array,
1962 - 20 = 1942
682 to the power of 1942 is divided by 2047, the remainder is 1623. inv (1623) = 729, there are matches in the array, the index is 6
1942 - 6 = 1936 = ѱ (n)
y ² - (2047 - 1936 + 1) y + 2047 = 0
y ² - 112y + 2047 = 0
y ₁ = 89
y ₂ = 23

Literature.
1. “Symmetry of numbers”, habrahabr.ru/post/218053 .
2. “Euler's function“, ru.wikipedia.org/wiki/Eyler_Function .
3. “Inverse number”, ru.wikipedia.org/wiki/Final_number
4. “Public-key cryptography”, ikit.edu.sfu-kras.ru/files/15/l5.pdf