Factor numbers
I would like to bring to your attention one of the variants of the factorization algorithm for a composite number.
As already noted [1], there are regularities in the distribution of quadratic residue values, both for primes and for composite numbers.
A known dependence should be given [2]. If the integer A , positive integer, is equal to the product of the primes a and b , then there are always two numbers c and d such that c 2 - d 2 = A or c 2 - d 2 = nA , where n is an integer from 1 to (A - 1). Moreover,
c 2 - d 2 = (c + d) (c - d) , i.e. (c + d) and (c - d) are multiples of the divisors a and b .
To simplify, we consider the matrix of residuals of the composite number A = 35 , as in [1], presented in Fig. 1.
Fig. 1 matrix composite residues of A = 35.
squares difference Properties of composite A lead to the fact that some of e , quadratic residues of A , the second column (Fig. 1) are equal to the total number of the smaller square of A . The numbers in the first column (Fig. 1), equally spaced on the number of e by the value of the square root of the e , a multiple number of divisors A .
For example, for the number 17 , the first column (Fig. 1), the quadratic remainder, column 2, is 9 . You need to extract the square root from 9 , add it to 17 and take it away from 17. We get, (17 + 3 = 20) , 20 divided by 4 is 5 , (17 - 3 = 14) , 14 divided by 2 is 7 . The resulting numbers 20 and 14 are multiples of the divisors of A , of which you can always find the divisors of A using the Euclidean algorithm [3] . Similar results will be obtained for other values of numbers, with quadratic residuals equal to the full square. For 24 , the quadratic remainder is 16 , and the multiples of the divisors are (24 +4 = 28) and (24 - 4 = 20).
It should be noted that the quadratic residuals (Fig. 1), column 2, are grouped symmetrically with respect to 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 repeating values on the entire numerical 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 laws. If we add and subtract from each other numbers with equal quadratic residues, we obtain numbers divisible by the divisors of A , i.e. a andb .
For numbers 16 and 9 (Fig. 1), the quadratic remainder is 11 . Add 16 and 9 , get 25 , divide 25 by 5 , get 5 . Subtract 9 from 16 , we get 7 . The found values are multiples of divisors A . In order to find numbers with identical quadratic residuals, we consider one more property of the table (Fig. 1). Relative to the middle of the numerical interval A , i.e. numbers (A + 1) / 2 and (A - 1) / 2
, quadratic residuals (Fig. 1), column 2, increase by the value of the arithmetic progression. The remainder of 17 , squared, divided by 35 , is 9 . For 16, remainder 11 , for 15, remainder 15 , for 14, remainder 21 , for 13, remainder 29 , for 12, remainder 4 . It turns out 9 + 2 = 11 , 11 + 4 = 15 , 15 + 6 = 21 , 21 + 8 = 29 , 29 + 10 = 39 , divided by 35 , the remainder is4 . This is a characteristic characteristic of arithmetic progression.
The numbers in column 1 having the same quadratic residues are separated from each other by the sum of the members of the arithmetic progression equal to the number A times 2n , where n takes values in the range from 1 to (A - 1) . The sum of the members of the arithmetic progression equal to 2nA does not have to occupy the entire range of the number A for the numbers of the 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, we 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 times 2 , i.e. from 70 it differs by 2 units. Number 2 , this is the first position of the progression. It is necessary to subtract 8 from (A - 1) / 2 = 17 , we get 9 and from 1 subtract 1 from 17 , we get 16 . For 9and 16 , the quadratic remainder (Fig. 1) is 11 . Further, 16 + 9 = 25 , 16 - 9 = 7 . Two multiples of the divisors of A = 35 are obtained .
More examples,
Example 1.
2 to the 11th degree, minus 1 is 2047.
2047 = 23 * 89
The first attempt.
2047 * 2 = 4094,
Square root of 4094 = 63, remainder 125,
63 * 64 = 4032, less than 4094,
64 * 65 = 4160,
4160 - 4094 = 66, does not fall into the sum of the terms of the progression.
Second attempt.
2047 * 4 = 8188,
Square root of 8188 = 90, 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 attempt.
216527 * 2 = 433054, the
square root of 433054 = 658, the remainder 90,
658 * 659 = 433622,
433622 - 433054 = 568, does not fall into the sum of the terms of the progression.
Skip the description of failed attempts.
Fifth attempt.
216527 * 10 = 2165270,
Square root of 2165270 = 1471, 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. "Fermat's factorization method." en.wikipedia.org/wiki/Factorization Method_Farm
3. “Euclidean Algorithm”, en.wikipedia.org/wiki/Euclidean Algorithm
As already noted [1], there are regularities in the distribution of quadratic residue values, both for primes and for composite numbers.
A known dependence should be given [2]. If the integer A , positive integer, is equal to the product of the primes a and b , then there are always two numbers c and d such that c 2 - d 2 = A or c 2 - d 2 = nA , where n is an integer from 1 to (A - 1). Moreover,
c 2 - d 2 = (c + d) (c - d) , i.e. (c + d) and (c - d) are multiples of the divisors a and b .
To simplify, we consider the matrix of residuals of the composite number A = 35 , as in [1], presented in Fig. 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 | 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 matrix composite residues of A = 35.
squares difference Properties of composite A lead to the fact that some of e , quadratic residues of A , the second column (Fig. 1) are equal to the total number of the smaller square of A . The numbers in the first column (Fig. 1), equally spaced on the number of e by the value of the square root of the e , a multiple number of divisors A .
For example, for the number 17 , the first column (Fig. 1), the quadratic remainder, column 2, is 9 . You need to extract the square root from 9 , add it to 17 and take it away from 17. We get, (17 + 3 = 20) , 20 divided by 4 is 5 , (17 - 3 = 14) , 14 divided by 2 is 7 . The resulting numbers 20 and 14 are multiples of the divisors of A , of which you can always find the divisors of A using the Euclidean algorithm [3] . Similar results will be obtained for other values of numbers, with quadratic residuals equal to the full square. For 24 , the quadratic remainder is 16 , and the multiples of the divisors are (24 +4 = 28) and (24 - 4 = 20).
It should be noted that the quadratic residuals (Fig. 1), column 2, are grouped symmetrically with respect to 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 repeating values on the entire numerical 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 laws. If we add and subtract from each other numbers with equal quadratic residues, we obtain numbers divisible by the divisors of A , i.e. a andb .
For numbers 16 and 9 (Fig. 1), the quadratic remainder is 11 . Add 16 and 9 , get 25 , divide 25 by 5 , get 5 . Subtract 9 from 16 , we get 7 . The found values are multiples of divisors A . In order to find numbers with identical quadratic residuals, we consider one more property of the table (Fig. 1). Relative to the middle of the numerical interval A , i.e. numbers (A + 1) / 2 and (A - 1) / 2
, quadratic residuals (Fig. 1), column 2, increase by the value of the arithmetic progression. The remainder of 17 , squared, divided by 35 , is 9 . For 16, remainder 11 , for 15, remainder 15 , for 14, remainder 21 , for 13, remainder 29 , for 12, remainder 4 . It turns out 9 + 2 = 11 , 11 + 4 = 15 , 15 + 6 = 21 , 21 + 8 = 29 , 29 + 10 = 39 , divided by 35 , the remainder is4 . This is a characteristic characteristic of arithmetic progression.
The numbers in column 1 having the same quadratic residues are separated from each other by the sum of the members of the arithmetic progression equal to the number A times 2n , where n takes values in the range from 1 to (A - 1) . The sum of the members of the arithmetic progression equal to 2nA does not have to occupy the entire range of the number A for the numbers of the 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, we 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 times 2 , i.e. from 70 it differs by 2 units. Number 2 , this is the first position of the progression. It is necessary to subtract 8 from (A - 1) / 2 = 17 , we get 9 and from 1 subtract 1 from 17 , we get 16 . For 9and 16 , the quadratic remainder (Fig. 1) is 11 . Further, 16 + 9 = 25 , 16 - 9 = 7 . Two multiples of the divisors of A = 35 are obtained .
More examples,
Example 1.
2 to the 11th degree, minus 1 is 2047.
2047 = 23 * 89
The first attempt.
2047 * 2 = 4094,
Square root of 4094 = 63, remainder 125,
63 * 64 = 4032, less than 4094,
64 * 65 = 4160,
4160 - 4094 = 66, does not fall into the sum of the terms of the progression.
Second attempt.
2047 * 4 = 8188,
Square root of 8188 = 90, 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 attempt.
216527 * 2 = 433054, the
square root of 433054 = 658, the remainder 90,
658 * 659 = 433622,
433622 - 433054 = 568, does not fall into the sum of the terms of the progression.
Skip the description of failed attempts.
Fifth attempt.
216527 * 10 = 2165270,
Square root of 2165270 = 1471, 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. "Fermat's factorization method." en.wikipedia.org/wiki/Factorization Method_Farm
3. “Euclidean Algorithm”, en.wikipedia.org/wiki/Euclidean Algorithm