Хотелось бы представить Вашему вниманию один из вариантов алгоритма факторизации составного числа.
Для упрощения рассмотрим матрицу остатков составного числа A = 35, так же как в [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
Для упрощения рассмотрим матрицу остатков составного числа 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