Factorization of numbers (option 2)

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

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

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

34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1
33	4	27	16	3	29th	12	eleven	thirteen	9	17	1	33	4	27	16	3	29th	12	eleven	thirteen	9	17	1	33	4	27	16	3	29th	12	eleven	thirteen	9
32	9	8	eleven	2	29th	18	16	22	4	23	1	32	9	8	eleven	2	29th	18	16	22	4	23	1	32	9	8	eleven	2	29th	18	16	22	4
31	16	6	eleven	26	1	31	16	6	eleven	26	1	31	16	6	eleven	26	1	31	16	6	eleven	26	1	31	16	6	eleven	26	1	31	16	6	eleven
thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty	25	fifteen	thirty
29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1	29th	1
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	29th	thirteen	1	27	29th	thirteen	1	27	29th	thirteen	1	27	29th	thirteen	1	27	29th	thirteen	1	27	29th	thirteen	1	27	29th	thirteen	1	27	29th	thirteen	1	27	29th
26	eleven	6	16	31	1	26	eleven	6	16	31	1	26	eleven	6	16	31	1	26	eleven	6	16	31	1	26	eleven	6	16	31	1	26	eleven	6	16
25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25	thirty	fifteen	25
24	16	34	eleven	19	1	24	16	34	eleven	19	1	24	16	34	eleven	19	1	24	16	34	eleven	19	1	24	16	34	eleven	19	1	24	16	34	eleven
23	4	22	16	18	29th	2	eleven	8	9	32	1	23	4	22	16	18	29th	2	eleven	8	9	32	1	23	4	22	16	18	29th	2	eleven	8	9
22	29th	8	1	22	29th	8	1	22	29th	8	1	22	29th	8	1	22	29th	8	1	22	29th	8	1	22	29th	8	1	22	29th	8	1	22	29th
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	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen	20	fifteen
19	eleven	34	16	24	1	19	eleven	34	16	24	1	19	eleven	34	16	24	1	19	eleven	34	16	24	1	19	eleven	34	16	24	1	19	eleven	34	16
18	9	22	eleven	23	29th	32	16	8	4	2	1	18	9	22	eleven	23	29th	32	16	8	4	2	1	18	9	22	eleven	23	29th	32	16	8	4
17	9	thirteen	eleven	12	29th	3	16	27	4	33	1	17	9	thirteen	eleven	12	29th	3	16	27	4	33	1	17	9	thirteen	eleven	12	29th	3	16	27	4
16	eleven	1	16	eleven	1	16	eleven	1	16	eleven	1	16	eleven	1	16	eleven	1	16	eleven	1	16	eleven	1	16	eleven	1	16	eleven	1	16	eleven	1	16
fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen	fifteen
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
thirteen	29th	27	1	thirteen	29th	27	1	thirteen	29th	27	1	thirteen	29th	27	1	thirteen	29th	27	1	thirteen	29th	27	1	thirteen	29th	27	1	thirteen	29th	27	1	thirteen	29th
12	4	thirteen	16	17	29th	33	eleven	27	9	3	1	12	4	thirteen	16	17	29th	33	eleven	27	9	3	1	12	4	thirteen	16	17	29th	33	eleven	27	9
eleven	16	1	eleven	16	1	eleven	16	1	eleven	16	1	eleven	16	1	eleven	16	1	eleven	16	1	eleven	16	1	eleven	16	1	eleven	16	1	eleven	16	1	eleven
10	thirty	20	25	5	fifteen	10	thirty	20	25	5	fifteen	10	thirty	20	25	5	fifteen	10	thirty	20	25	5	fifteen	10	thirty	20	25	5	fifteen	10	thirty	20	25
9	eleven	29th	16	4	1	9	eleven	29th	16	4	1	9	eleven	29th	16	4	1	9	eleven	29th	16	4	1	9	eleven	29th	16	4	1	9	eleven	29th	16
8	29th	22	1	8	29th	22	1	8	29th	22	1	8	29th	22	1	8	29th	22	1	8	29th	22	1	8	29th	22	1	8	29th	22	1	8	29th
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	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1
5	25	20	thirty	10	fifteen	5	25	20	thirty	10	fifteen	5	25	20	thirty	10	fifteen	5	25	20	thirty	10	fifteen	5	25	20	thirty	10	fifteen	5	25	20	thirty
4	16	29th	eleven	9	1	4	16	29th	eleven	9	1	4	16	29th	eleven	9	1	4	16	29th	eleven	9	1	4	16	29th	eleven	9	1	4	16	29th	eleven
3	9	27	eleven	33	29th	17	16	thirteen	4	12	1	3	9	27	eleven	33	29th	17	16	thirteen	4	12	1	3	9	27	eleven	33	29th	17	16	thirteen	4
2	4	8	16	32	29th	23	eleven	22	9	18	1	2	4	8	16	32	29th	23	eleven	22	9	18	1	2	4	8	16	32	29th	23	eleven	22	9
1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

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 are sure to be two columns in which the remaining values ​​are 1 . In fig. 1 are columns with numbers 12 , 24 .

From these two columns, the highest column number is equal to the product of (x - 1) to (y - 1) , where x and y divisors of 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) .

The indicated regularities make it possible to compose 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 the quadratic equation (2) .

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

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

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

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

i.e. 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 the reciprocal of c . For a composite number A equal to the product of the prime 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 relative to the column with the number ѱ (n ) .

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

Consider the sequence of actions for finding ѱ (n) .

1. Reduce the search range. From (A - 1), we take the value of the square root of A calculated to the nearest integer. Denote the result obtained by ѱ ₁ .

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

3. Find the number d = inv (s) . You can find using the extended Euclidean algorithm [4].

4. Let us power balances for d , since the exponent 1 and ending with some number m , less than or equal to the square root of A .

5. Found power balances put in an array denoted by M . Array Msort by ascending and index by degree.

6. Compute the residue from c in degrees ѱ ₁ divided by A and to compare the values of M .

7. If there are no matches, subtract m from ѱ ₁ and assign the resulting value to ѱ ₁ . Next, repeat paragraphs 6 and 7 until matches occur. 8. If there are matches, we subtract from ѱ _{1 the} magnitude of the degree index, which coincides with the value of the array M , assign the resulting value

ѱ ₁ .

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

Here's how it works. From (A - 1) = 34 (Fig. 1) we subtract the square root of 35 , i.e. 5 , we get 29 . For c, choose 18 . We 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 . From29 need to be taken away 5 . The resulting value of 24 is ѱ (n) . Next, substitute A and ѱ (n) in formula (2) and find y . y ₁ = 7 , y ₂ = 5 .

Another example.

2 to the 11th degree, minus 1 is 2047.
2047 = 23 * 89
2047/3 = 682 and the remainder is 1
s = 682, inv (s) = 3
The square root of 2047 = 45, the remainder is 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 in the degree of 2002 is divided by 2047, the remainder is 1013. inv (1013) = 1657, there are no matches in the array,
2002 - 20 = 1982
682 in the degree of 1982 is divided by 2047, the remainder is 524. inv (524) = 1504, there are no matches in the array ,
1982 - 20 = 1962
682 in the degree of 1962 we divide by 2047, the remainder 71. inv (71) = 173, there are no matches in the array,
1962 - 20 = 1942
682 in the degree of 1942 we divide by 2047, the remainder 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 Function”, en.wikipedia.org/wiki/Euler_Function .
3. “Return number”, ru.wikipedia.org/wiki/Return_number
4. “Public key cryptography”, ikit.edu.sfu-kras.ru/files/15/l5.pdf