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

Как уже отмечалось[1], есть закономерности распределения значений квадратичных вычетов, как для простых, так и для составных чисел.

Следует привести известную зависимость[2]. Если число A, целое, положительное, равно произведению простых чисел a и b, то всегда найдутся такие два числа c и d, что c² – d² = A или c² – d² = nA , где n целое число от 1 до ( A – 1 ). При этом,
c² – d² = (c + d)(c – d), т.е. (c + d) и (c – d ) кратны делителям a и b.


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

Например, для числа 17, первый столбец (рис. 1), квадратичный остаток, столбец 2, равен 9. Нужно из 9 извлечь корень квадратный, прибавить его к 17 и отнять его от 17. Получим, (17 + 3 = 20), 20 деленное на 4 равно 5, (17 – 3 = 14), 14 деленное на 2 равно 7. Полученные числа 20 и 14 кратны делителям числа A, из них с помощью Алгоритма Евклида[3] всегда можно найти делители числа A. Аналогичные результаты будут получены для других значений чисел, с квадратичными остатками равными полному квадрату. Для 24, квадратичный остаток равен 16, а числа кратные делителям равны (24 +4 = 28) и (24 – 4 = 20).

Необходимо отметить, что квадратичные остатки (рис. 1), столбец 2, сгруппированы симметрично относительно середины числового интервала числа A, т.е. относительно чисел (A + 1)/2 и (A – 1)/2, и всегда имеют четыре повторяющихся значения на всем числовом интервале первого столбца. Для числа A = 35 (рис. 1), это значения 1, 4, 9, 11, 16, 29. Числа, у которых, в каждой половине числового интервала числа A, значения квадратичных остатков совпадают, поддерживают следующие закономерности. Если сложить и вычесть друг из друга числа с равными квадратичными остатками, получим числа кратные делителям числа A, т.е. a и b.

Для чисел 16 и 9 (рис. 1), квадратичный остаток равен 11. Сложим 16 и 9, получим 25, разделим 25 на 5, получим 5. Из 16 вычтем 9, получим 7. Найденные значения кратны делителям числа A.

Для того чтобы найти числа с одинаковыми квадратичными остатками, рассмотрим еще одно свойство таблицы (рис. 1). Относительно середины числового интервала A, т.е. чисел (A + 1)/2 и (A – 1)/2, квадратичные остатки (рис. 1), столбец 2, увеличиваются на величину арифметической прогрессии. Остаток от 17, в квадрате, деленное на 35, равен 9. Для 16 остаток 11, для 15 остаток 15, для 14 остаток 21, для 13 остаток 29, для 12 остаток 4. Получается 9 + 2 = 11, 11 + 4 = 15, 15 + 6 = 21, 21 + 8 = 29, 29 + 10 = 39, деленное на 35, остаток равен 4. Это характерная для арифметической прогрессии зависимость.

Числа в столбце 1, имеющие одинаковые квадратичные остатки, отстоят друг от друга на величины суммы членов арифметической прогрессии, равной числу A, умноженному на 2n, где n принимает значения в, диапазоне от1 до (A – 1). Сумма членов арифметической прогрессии, равная 2nA, не обязательно должна занимать весь диапазон числа A для номеров членов арифметической прогрессии и использовать первый или последний из ее членов.

Работает это следующим образом. Число A = 35, умножаем на 2, 35 * 2 = 70, извлекаем квадратный корень из 70, получаем 8 и 6 в остатке. К числу 8 прибавляем 1 и умножаем на 8, получаем 72. Число 72 это восьмая позиция прогрессии и от A умноженного на 2, т.е. от 70 оно отличается на 2 единицы. Число 2, это первая позиция прогрессии. Нужно от (A – 1)/2 =17 отнять 8, получим 9 и от 17 отнять 1, получим 16. Для 9 и 16, квадратичный остаток (рис. 1) равен 11. Далее, 16 + 9 = 25, 16 – 9 = 7. Получены два значения кратные делителям числа A = 35.

Еще примеры,
Пример 1.
2 в 11 степени, минус 1 равно 2047.
2047 = 23 * 89
Первая попытка.
2047 * 2 = 4094,
Корень квадратный из 4094 = 63, остаток 125,
63 * 64 = 4032, меньше 4094,
64 * 65 = 4160,
4160 – 4094 = 66, не попадает в значения суммы членов прогрессии.
Вторая попытка.
2047 * 4 = 8188,
Корень квадратный из 8188 = 90, остаток 88,
90 * 91 = 8190,
8190 – 8188 = 2, это первый член прогрессии,
2047 – 1 = 2046,
2046 / 2 = 1023,
1023 – 90 = 933,
1023 – 1 = 1022,
1022 + 933 = 1955,
1955 / 85 = 23, первый делитель,
1022 – 933 = 89, второй делитель.

Пример 2.
216527 = 293 * 739,
Первая попытка.
216527 * 2 = 433054,
Корень квадратный из 433054 = 658, остаток 90,
658 * 659 = 433622,
433622 – 433054 = 568, не попадает в значения суммы членов прогрессии.
Пропустим описание неудачных попыток.
Пятая попытка.
216527 * 10 = 2165270,
Корень квадратный из 2165270 = 1471, остаток 1429,
1471 * 1472 = 2165312,
2165312 – 2165270 = 42, это шестой член прогрессии.
216527 – 1 = 216526,
216526 / 2 = 108263,
108263 – 1471 = 106792,
108263 – 6 = 108257,
108257 – 106792 = 1465,
1465 / 5 = 293, первый делитель.
108257 + 106792 = 215049,
215049 / 291 = 739, второй делитель.

Литература.
1. “Симметрия чисел”, habrahabr.ru/post/218053.
2. «Метод факторизации Ферма». ru.wikipedia.org/wiki/Метод_факторизации_Ферма
3. “Алгоритм Евклида”, ru.wikipedia.org/wiki/Алгоритм_Евклида