Search
Write a publication
Pull to refresh

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

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

Для упрощения рассмотрим матрицу остатков составного числа 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:
Total votes 16: ↑5 and ↓11-6
Comments1

Articles