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.
    341341341341341341341341341341341341341341341341341
    3342716329th12eleventhirteen91713342716329th12eleventhirteen91713342716329th12eleventhirteen9
    3298eleven229th18162242313298eleven229th18162242313298eleven229th1816224
    31166eleven26131166eleven26131166eleven26131166eleven26131166eleven26131166eleven
    thirty25fifteenthirty25fifteenthirty25fifteenthirty25fifteenthirty25fifteenthirty25fifteenthirty25fifteenthirty25fifteenthirty25fifteenthirty25fifteenthirty25fifteenthirty
    29th129th129th129th129th129th129th129th129th129th129th129th129th129th129th129th129th1
    281472128147212814721281472128147212814721281472128147212814
    2729ththirteen12729ththirteen12729ththirteen12729ththirteen12729ththirteen12729ththirteen12729ththirteen12729ththirteen12729th
    26eleven61631126eleven61631126eleven61631126eleven61631126eleven61631126eleven616
    25thirtyfifteen25thirtyfifteen25thirtyfifteen25thirtyfifteen25thirtyfifteen25thirtyfifteen25thirtyfifteen25thirtyfifteen25thirtyfifteen25thirtyfifteen25thirtyfifteen25
    241634eleven191241634eleven191241634eleven191241634eleven191241634eleven191241634eleven
    23422161829th2eleven8932123422161829th2eleven8932123422161829th2eleven89
    2229th812229th812229th812229th812229th812229th812229th812229th812229th
    21212121212121212121212121212121212121212121212121212121212121212121
    20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen20fifteen
    19eleven341624119eleven341624119eleven341624119eleven341624119eleven341624119eleven3416
    18922eleven2329th3216842118922eleven2329th3216842118922eleven2329th321684
    179thirteeneleven1229th316274331179thirteeneleven1229th316274331179thirteeneleven1229th316274
    16eleven116eleven116eleven116eleven116eleven116eleven116eleven116eleven116eleven116eleven116eleven116
    fifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteenfifteen
    14211421142114211421142114211421142114211421142114211421142114211421
    thirteen29th271thirteen29th271thirteen29th271thirteen29th271thirteen29th271thirteen29th271thirteen29th271thirteen29th271thirteen29th
    124thirteen161729th33eleven27931124thirteen161729th33eleven27931124thirteen161729th33eleven279
    eleven161eleven161eleven161eleven161eleven161eleven161eleven161eleven161eleven161eleven161eleven161eleven
    10thirty20255fifteen10thirty20255fifteen10thirty20255fifteen10thirty20255fifteen10thirty20255fifteen10thirty2025
    9eleven29th16419eleven29th16419eleven29th16419eleven29th16419eleven29th16419eleven29th16
    829th221829th221829th221829th221829th221829th221829th221829th221829th
    71428217142821714282171428217142821714282171428217142821714
    6161616161616161616161616161616161
    52520thirty10fifteen52520thirty10fifteen52520thirty10fifteen52520thirty10fifteen52520thirty10fifteen52520thirty
    41629theleven9141629theleven9141629theleven9141629theleven9141629theleven9141629theleven
    3927eleven3329th1716thirteen41213927eleven3329th1716thirteen41213927eleven3329th1716thirteen4
    248163229th23eleven229181248163229th23eleven229181248163229th23eleven229
    1111111111111111111111111111111111

    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

    Also popular now: