Factorization of numbers

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

As already noted [1], there are regularities in the distribution of values ​​of quadratic residues, both for simple and for composite numbers.

It is necessary to bring the known dependence [2]. If the number A , integer, positive, is equal to the product of the primes a and b , then there are always two numbers c and d such that c ² - d ² = A or c ² - d ² = nA , where n is an integer from 1 to (A - 1) . Wherein,
c ² - d ² = (c + d) (c - d) , i.e. (c + d) and (c - d) are multiples of divisors a and b .
')

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

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 Residual matrix of composite number A = 35.

The properties of the difference of the squares of the composite number A lead to the fact that some numbers e , quadratic residues of the number A , the second column (Fig. 1), are equal to the full square of the number less than A. The numbers in the first column (Fig. 1), equidistant from e to the square root of e , are multiples of the divisors of A.

For example, for the number 17 , the first column (Fig. 1), the quadratic remainder, column 2, is 9 . It is necessary to extract the square root from 9 , add it to 17 and take it away from 17 . We obtain, (17 + 3 = 20) , 20 divided by 4 equals 5 , (17 - 3 = 14) , 14 divided by 2 equals 7 . The obtained numbers 20 and 14 are divisors of the divisors of the number A , of which with the help of the Euclidean Algorithm [3] one can always find the divisors of the number A. Similar results will be obtained for other values ​​of numbers, with quadratic residues equal to a full square. For 24 , the quadratic remainder is 16 , and multiples are divisors (24 +4 = 28) and (24 - 4 = 20) .

It should be noted that the quadratic residues (Fig. 1), column 2, are grouped symmetrically about the middle of the numerical interval of the number A , i.e. relative to the numbers (A + 1) / 2 and (A - 1) / 2 , and always have four duplicate values ​​over the entire numeric interval of the first column. For the number A = 35 (Fig. 1), these are the values 1, 4, 9, 11, 16, 29 . The numbers for which, in each half of the numerical interval of the number A , the values ​​of the quadratic residues coincide, support the following regularities. If we add and subtract from each other numbers with equal quadratic residues, we obtain multiples of the divisors of A , i.e. a and b .

For numbers 16 and 9 (Fig. 1), the quadratic remainder is 11 . Add 16 and 9 , get 25 , divide 25 by 5 , get 5 . From 16 subtract 9 , we get 7 . The values ​​found are multiples of the divisors of A.

In order to find numbers with identical quadratic residues, consider another property of the table (Fig. 1). Regarding the middle of the numeric interval A , i.e. The numbers (A + 1) / 2 and (A - 1) / 2 , quadratic residues (Fig. 1), column 2, increase by the value of the arithmetic progression. The remainder of 17 , squared, divided by 35 , is equal to 9 . For 16, the balance is 11 , for 15 there is a balance of 15 , for 14 a balance of 21 , for 13 a balance of 29 , for 12 a balance of 4 . It turns out 9 + 2 = 11 , 11 + 4 = 15 , 15 + 6 = 21 , 21 + 8 = 29 , 29 + 10 = 39 , divided by 35 , the remainder is 4 . This is characteristic of arithmetic progression dependence.

Numbers in column 1, having the same quadratic residues, are separated from each other by the sum of the terms of the arithmetic progression equal to the number A multiplied by 2n , where n takes values ​​in the range from 1 to (A - 1) . The sum of the members of an arithmetic progression equal to 2nA does not necessarily have to occupy the entire range of the number A for the numbers of members of the arithmetic progression and use the first or last of its members.

It works as follows. Number A = 35 , multiply by 2 , 35 * 2 = 70 , extract the square root of 70 , we get 8 and 6 in the remainder. To the number 8 we add 1 and multiply by 8 , we get 72 . The number 72 is the eighth position of the progression and from A multiplied by 2 , i.e. from 70 it differs by 2 units. The number 2 is the first position of the progression. It is necessary to subtract 8 from (A - 1) / 2 = 17 , we get 9 and subtract 1 from 17 , we get 16 . For 9 and 16 , the quadratic remainder (Fig. 1) is 11 . Further, 16 + 9 = 25 , 16 - 9 = 7 . Received two values ​​multiple to divisors of the number A = 35 .

More examples
Example 1
2 to the 11th degree, minus 1 equals 2047.
2047 = 23 * 89
First try.
2047 * 2 = 4094,
The square root of 4094 = 63, the remainder 125,
63 * 64 = 4032, less than 4094,
64 * 65 = 4160,
4160 - 4094 = 66, does not fall into the values ​​of the sum of the members of the progression.
The second attempt.
2047 * 4 = 8188,
The square root of 8188 = 90, the remainder 88,
90 * 91 = 8190,
8190 - 8188 = 2, this is the first member of the progression,
2047 - 1 = 2046,
2046/2 = 1023,
1023 - 90 = 933,
1023 - 1 = 1022,
1022 + 933 = 1955,
1955/85 = 23, the first divisor,
1022 - 933 = 89, the second divider.

Example 2
216527 = 293 * 739,
First try.
216527 * 2 = 433054,
The square root of 433054 = 658, the remainder is 90,
658 * 659 = 433622,
433622 - 433054 = 568, does not fall into the values ​​of the sum of the members of the progression.
Skip the description of failed attempts.
Fifth attempt.
216527 * 10 = 2165270,
The square root of 2165270 = 1471, the remainder 1429,
1471 * 1472 = 2165312,
2165312 - 2165270 = 42, this is the sixth member of the progression.
216527 - 1 = 216526,
216526/2 = 108263,
108263 - 1471 = 106792,
108263 - 6 = 108257,
108257 - 106792 = 1465,
1465/5 = 293, the first divider.
108257 + 106792 = 215049,
215049/291 = 739, the second divider.

Literature.
1. “Symmetry of numbers”, habrahabr.ru/post/218053 .
2. "Method of factorization Farm". ru.wikipedia.org/wiki/Factorization Method_Farm
3. “Euclidean Algorithm”, en.wikipedia.org/wiki/Euclide's Algorithm