Факторизация чисел -6


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

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

Следует привести известную зависимость[2]. Если число A, целое, положительное, равно произведению простых чисел a и b, то всегда найдутся такие два числа c и d, что c2 – d2 = A или c2 – d2 = nA , где n целое число от 1 до ( A – 1 ). При этом,
c2 – d2 = (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/Алгоритм_Евклида




К сожалению, не доступен сервер mySQL