Факторизация чисел (вариант 2)

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

    Для упрощения рассмотрим матрицу остатков составного числа A = 35, так же как в [1], представленную на рис.1.

    Как уже упоминалось [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, то обязательно найдутся два столбца, в которых остальные значения равны 1. На рис. 1 это столбцы с номерами 12, 24.

    Из этих двух столбцов, наибольший номер столбца, равен произведению (x – 1) на (y – 1), где x и y делители числа A. Следует отметить, что в данном случае, номер столбца 24 равен значению функции Эйлера [2], значение которой равно
    (x – 1) * (y – 1) = ѱ(n).

    Разность между числом A и функцией Эйлера ѱ(n) равна (x + y – 1).

    Указанные закономерности позволяют составить систему уравнений.

    Ѱ(n) = (x – 1) * (y – 1)
    A – ѱ(n) = (x + y – 1)
    Формула (1)

    Используя подстановки, систему уравнений (1) можно свести к квадратному уравнению (2).

    y2 – (A – ѱ(n) + 1)y + A = 0
    Формула (2)

    Для успешного решения этого уравнения не хватает только ѱ(n).

    Рассмотрим дополнительно, свойства степенных остатков числа A таблицы (рис 1). Введем понятие обратного значения [3]. Если выбрать значение с из диапазона чисел (1, A – 1), так чтобы с не было кратным делителям x и y, то всегда найдется значение d, из этого же диапазона (1, A – 1), такое что

    c * d ≡ 1(mod A)
    Формула (3)

    т.е. c * d = nA + 1, где n может принимать значения от 1 до (A – 2).

    Введем обозначение d = inv(с), т.е. d равно обратному значению c. Для составного числа А, равного произведению простых сомножителей x и y, количество пар обратных значений, составляет

    (A – (x – 1) – (y – 1) – 1)/2
    Формула (4)

    Обратные значения, в строках таблицы (рис 1), расположены симметрично относительно столбца с номером ѱ(n).

    Обратные значения, в столбцах таблицы (рис 1), расположены симметрично относительно пар обратных значений в первом столбце.

    Рассмотрим последовательность действий для нахождения ѱ(n).

    1. Уменьшим диапазон поиска. Из (A – 1) отнимем значение корня квадратного из A, вычисленного с точностью до целого. Полученный результат обозначим ѱ1.

    2. Выберем число c, не кратное делителям x, y числа A. Желательно чтобы степенные остатки числа c имели минимальное количество повторяющихся значений.

    3. Найдем число d = inv(с). Найти можно с помощью расширенного алгоритма Евклида [4].

    4. Найдем степенные остатки для d, начиная с показателя степени 1 и заканчивая некоторым числом m, меньшим или равным корню квадратному из A.

    5. Найденные степенные остатки поместим в массив, обозначим его M. Массив M рассортируем по возрастанию и проиндексируем по показателю степени.

    6. Вычисляем остаток от c в степени ѱ1, деленное на A и сравниваем с величинами M.

    7. При отсутствии совпадений, от ѱ1 отнимаем m и полученное значение присваиваем ѱ1. Далее повторяем пункт 6 и 7 до появления совпадений.

    8. При наличии совпадений, от ѱ1 отнимаем величину индекса степени, совпавшего значения массива M, полученное значение присваиваем ѱ1.

    В этом случае ѱ1 = ѱ(n).

    Вот как это работает. От (A – 1) = 34 (рис 1)отнимаем корень квадратный из 35, т.е. 5, получим 29. В качестве c выбираем 18. Находим inv(18) = 2. Если m =5, тогда массив M = { 2, 4, 8, 16, 32 }. Остаток от 18, в степени 29, деленное на 35, равен 23. inv(23) = 32. Это значение есть в массиве и индекс равен 5. От 29 нужно отнять 5. Полученное значение 24 равно ѱ(n). Далее подставляем A и ѱ(n) в формулу (2) и находим y. y1 = 7, y2 = 5.

    Еще пример.

    2 в 11 степени, минус 1 равно 2047.
    2047 = 23 * 89
    2047/3 = 682 и остаток 1
    с = 682, inv(с) = 3
    Корень квадратный из 2047 = 45, остаток 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 в степени 2002 делим на 2047, остаток 1013. inv(1013) = 1657, нет совпадений в массиве,
    2002 — 20 = 1982
    682 в степени 1982 делим на 2047, остаток 524. inv(524) = 1504, нет совпадений в массиве,
    1982 – 20 = 1962
    682 в степени 1962 делим на 2047, остаток 71. inv(71) = 173, нет совпадений в массиве,
    1962 – 20 = 1942
    682 в степени 1942 делим на 2047, остаток 1623. inv(1623) = 729, есть совпадения в массиве, индекс равен 6
    1942 – 6 = 1936 = ѱ(n)
    y2 – (2047 – 1936 + 1)y + 2047 = 0
    y2 – 112y + 2047 = 0
    y1 = 89
    y2 = 23

    Литература.
    1. “Симметрия чисел”, habrahabr.ru/post/218053.
    2. “ Функция Эйлера “, ru.wikipedia.org/wiki/Функция_Эйлера.
    3. “Обратное число”, ru.wikipedia.org/wiki/Обратное_число
    4. “Криптография с открытым ключом”, ikit.edu.sfu-kras.ru/files/15/l5.pdf
    • –6
    • 2,1k
    • 1
    Поделиться публикацией

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

      +1
      Как уже упоминалось [1]
      Мы тут вообще-то в интернете, существует такая вещь как «ссылка». Да-да, вот то самое, которое у вас внизу.
      1. “Симметрия чисел”, habrahabr.ru/post/218053.
      Ссылка на ссылку, ну надо же.

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

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