Pull to refresh

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

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

Для упрощения рассмотрим матрицу остатков составного числа 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
Tags:
Hubs:
-6
Comments 1
Comments Comments 1

Articles