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

Для упрощения рассмотрим матрицу остатков составного числа 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).

y² – (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, вычисленного с точностью до целого. Полученный результат обозначим ?₁.

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

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

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

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

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

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

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

В этом случае ?₁ = ?(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. y₁ = 7, y₂ = 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)
y² – (2047 – 1936 + 1)y + 2047 = 0
y² – 112y + 2047 = 0
y₁ = 89
y₂ = 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