Факторизация чисел

    Хотелось бы представить Вашему вниманию один из вариантов алгоритма факторизации составного числа.

    Как уже отмечалось[1], есть закономерности распределения значений квадратичных вычетов, как для простых, так и для составных чисел.

    Следует привести известную зависимость[2]. Если число A, целое, положительное, равно произведению простых чисел a и b, то всегда найдутся такие два числа c и d, что c2 – d2 = A или c2 – d2 = nA , где n целое число от 1 до ( A – 1 ). При этом,
    c2 – d2 = (c + d)(c – d), т.е. (c + d) и (c – d ) кратны делителям a и b.


    Для упрощения рассмотрим матрицу остатков составного числа A = 35, так же как в [1], представленную на рис.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 29 12 11 13 9 17 1 33 4 27 16 3 29 12 11 13 9 17 1 33 4 27 16 3 29 12 11 13 9
    32 9 8 11 2 29 18 16 22 4 23 1 32 9 8 11 2 29 18 16 22 4 23 1 32 9 8 11 2 29 18 16 22 4
    31 16 6 11 26 1 31 16 6 11 26 1 31 16 6 11 26 1 31 16 6 11 26 1 31 16 6 11 26 1 31 16 6 11
    30 25 15 30 25 15 30 25 15 30 25 15 30 25 15 30 25 15 30 25 15 30 25 15 30 25 15 30 25 15 30 25 15 30
    29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 1 29 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 29 13 1 27 29 13 1 27 29 13 1 27 29 13 1 27 29 13 1 27 29 13 1 27 29 13 1 27 29 13 1 27 29
    26 11 6 16 31 1 26 11 6 16 31 1 26 11 6 16 31 1 26 11 6 16 31 1 26 11 6 16 31 1 26 11 6 16
    25 30 15 25 30 15 25 30 15 25 30 15 25 30 15 25 30 15 25 30 15 25 30 15 25 30 15 25 30 15 25 30 15 25
    24 16 34 11 19 1 24 16 34 11 19 1 24 16 34 11 19 1 24 16 34 11 19 1 24 16 34 11 19 1 24 16 34 11
    23 4 22 16 18 29 2 11 8 9 32 1 23 4 22 16 18 29 2 11 8 9 32 1 23 4 22 16 18 29 2 11 8 9
    22 29 8 1 22 29 8 1 22 29 8 1 22 29 8 1 22 29 8 1 22 29 8 1 22 29 8 1 22 29 8 1 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
    19 11 34 16 24 1 19 11 34 16 24 1 19 11 34 16 24 1 19 11 34 16 24 1 19 11 34 16 24 1 19 11 34 16
    18 9 22 11 23 29 32 16 8 4 2 1 18 9 22 11 23 29 32 16 8 4 2 1 18 9 22 11 23 29 32 16 8 4
    17 9 13 11 12 29 3 16 27 4 33 1 17 9 13 11 12 29 3 16 27 4 33 1 17 9 13 11 12 29 3 16 27 4
    16 11 1 16 11 1 16 11 1 16 11 1 16 11 1 16 11 1 16 11 1 16 11 1 16 11 1 16 11 1 16 11 1 16
    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 1 13 29 27 1 13 29 27 1 13 29 27 1 13 29 27 1 13 29 27 1 13 29 27 1 13 29 27 1 13 29
    12 4 13 16 17 29 33 11 27 9 3 1 12 4 13 16 17 29 33 11 27 9 3 1 12 4 13 16 17 29 33 11 27 9
    11 16 1 11 16 1 11 16 1 11 16 1 11 16 1 11 16 1 11 16 1 11 16 1 11 16 1 11 16 1 11 16 1 11
    10 30 20 25 5 15 10 30 20 25 5 15 10 30 20 25 5 15 10 30 20 25 5 15 10 30 20 25 5 15 10 30 20 25
    9 11 29 16 4 1 9 11 29 16 4 1 9 11 29 16 4 1 9 11 29 16 4 1 9 11 29 16 4 1 9 11 29 16
    8 29 22 1 8 29 22 1 8 29 22 1 8 29 22 1 8 29 22 1 8 29 22 1 8 29 22 1 8 29 22 1 8 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 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 30 10 15 5 25 20 30 10 15 5 25 20 30 10 15 5 25 20 30 10 15 5 25 20 30 10 15 5 25 20 30
    4 16 29 11 9 1 4 16 29 11 9 1 4 16 29 11 9 1 4 16 29 11 9 1 4 16 29 11 9 1 4 16 29 11
    3 9 27 11 33 29 17 16 13 4 12 1 3 9 27 11 33 29 17 16 13 4 12 1 3 9 27 11 33 29 17 16 13 4
    2 4 8 16 32 29 23 11 22 9 18 1 2 4 8 16 32 29 23 11 22 9 18 1 2 4 8 16 32 29 23 11 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

    Рис. 1 Матрица остатков составного числа A = 35.

    Свойства разности квадратов составного числа A приводят к тому, что некоторые числа e, квадратичные остатки числа A, второй столбец (рис. 1), равны полному квадрату числа меньшего A. Числа в первом столбце (рис. 1), равноудаленные от числа e на величину корня квадратного из e, кратны делителям числа A.

    Например, для числа 17, первый столбец (рис. 1), квадратичный остаток, столбец 2, равен 9. Нужно из 9 извлечь корень квадратный, прибавить его к 17 и отнять его от 17. Получим, (17 + 3 = 20), 20 деленное на 4 равно 5, (17 – 3 = 14), 14 деленное на 2 равно 7. Полученные числа 20 и 14 кратны делителям числа A, из них с помощью Алгоритма Евклида[3] всегда можно найти делители числа A. Аналогичные результаты будут получены для других значений чисел, с квадратичными остатками равными полному квадрату. Для 24, квадратичный остаток равен 16, а числа кратные делителям равны (24 +4 = 28) и (24 – 4 = 20).

    Необходимо отметить, что квадратичные остатки (рис. 1), столбец 2, сгруппированы симметрично относительно середины числового интервала числа A, т.е. относительно чисел (A + 1)/2 и (A – 1)/2, и всегда имеют четыре повторяющихся значения на всем числовом интервале первого столбца. Для числа A = 35 (рис. 1), это значения 1, 4, 9, 11, 16, 29. Числа, у которых, в каждой половине числового интервала числа A, значения квадратичных остатков совпадают, поддерживают следующие закономерности. Если сложить и вычесть друг из друга числа с равными квадратичными остатками, получим числа кратные делителям числа A, т.е. a и b.

    Для чисел 16 и 9 (рис. 1), квадратичный остаток равен 11. Сложим 16 и 9, получим 25, разделим 25 на 5, получим 5. Из 16 вычтем 9, получим 7. Найденные значения кратны делителям числа A.

    Для того чтобы найти числа с одинаковыми квадратичными остатками, рассмотрим еще одно свойство таблицы (рис. 1). Относительно середины числового интервала A, т.е. чисел (A + 1)/2 и (A – 1)/2, квадратичные остатки (рис. 1), столбец 2, увеличиваются на величину арифметической прогрессии. Остаток от 17, в квадрате, деленное на 35, равен 9. Для 16 остаток 11, для 15 остаток 15, для 14 остаток 21, для 13 остаток 29, для 12 остаток 4. Получается 9 + 2 = 11, 11 + 4 = 15, 15 + 6 = 21, 21 + 8 = 29, 29 + 10 = 39, деленное на 35, остаток равен 4. Это характерная для арифметической прогрессии зависимость.

    Числа в столбце 1, имеющие одинаковые квадратичные остатки, отстоят друг от друга на величины суммы членов арифметической прогрессии, равной числу A, умноженному на 2n, где n принимает значения в, диапазоне от1 до (A – 1). Сумма членов арифметической прогрессии, равная 2nA, не обязательно должна занимать весь диапазон числа A для номеров членов арифметической прогрессии и использовать первый или последний из ее членов.

    Работает это следующим образом. Число A = 35, умножаем на 2, 35 * 2 = 70, извлекаем квадратный корень из 70, получаем 8 и 6 в остатке. К числу 8 прибавляем 1 и умножаем на 8, получаем 72. Число 72 это восьмая позиция прогрессии и от A умноженного на 2, т.е. от 70 оно отличается на 2 единицы. Число 2, это первая позиция прогрессии. Нужно от (A – 1)/2 =17 отнять 8, получим 9 и от 17 отнять 1, получим 16. Для 9 и 16, квадратичный остаток (рис. 1) равен 11. Далее, 16 + 9 = 25, 16 – 9 = 7. Получены два значения кратные делителям числа A = 35.

    Еще примеры,
    Пример 1.
    2 в 11 степени, минус 1 равно 2047.
    2047 = 23 * 89
    Первая попытка.
    2047 * 2 = 4094,
    Корень квадратный из 4094 = 63, остаток 125,
    63 * 64 = 4032, меньше 4094,
    64 * 65 = 4160,
    4160 – 4094 = 66, не попадает в значения суммы членов прогрессии.
    Вторая попытка.
    2047 * 4 = 8188,
    Корень квадратный из 8188 = 90, остаток 88,
    90 * 91 = 8190,
    8190 – 8188 = 2, это первый член прогрессии,
    2047 – 1 = 2046,
    2046 / 2 = 1023,
    1023 – 90 = 933,
    1023 – 1 = 1022,
    1022 + 933 = 1955,
    1955 / 85 = 23, первый делитель,
    1022 – 933 = 89, второй делитель.

    Пример 2.
    216527 = 293 * 739,
    Первая попытка.
    216527 * 2 = 433054,
    Корень квадратный из 433054 = 658, остаток 90,
    658 * 659 = 433622,
    433622 – 433054 = 568, не попадает в значения суммы членов прогрессии.
    Пропустим описание неудачных попыток.
    Пятая попытка.
    216527 * 10 = 2165270,
    Корень квадратный из 2165270 = 1471, остаток 1429,
    1471 * 1472 = 2165312,
    2165312 – 2165270 = 42, это шестой член прогрессии.
    216527 – 1 = 216526,
    216526 / 2 = 108263,
    108263 – 1471 = 106792,
    108263 – 6 = 108257,
    108257 – 106792 = 1465,
    1465 / 5 = 293, первый делитель.
    108257 + 106792 = 215049,
    215049 / 291 = 739, второй делитель.

    Литература.
    1. “Симметрия чисел”, habrahabr.ru/post/218053.
    2. «Метод факторизации Ферма». ru.wikipedia.org/wiki/Метод_факторизации_Ферма
    3. “Алгоритм Евклида”, ru.wikipedia.org/wiki/Алгоритм_Евклида
    • –6
    • 6,3k
    • 3
    Поделиться публикацией

    Комментарии 3

      +4
      А это вообще к чему?
        +1
        И как скорость на 200+ битных числах по сравнению с тем же msieve? Нет замеров? Тогда давай дасвиданья!
          0

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое