Детерминированный метод факторизации чисел, основанный на на использовании mod 6 и mod 4

О! Сколько нам открытий чудных
Готовит просвещение дух,
И опыт, сын ошибок трудных,
И гений, парадоксов друг,

И случай, бог изобретатель…
А.С. Пушкин

Вместо вступления

Надеюсь представить решение проблемы факторизации чисел, основанного на использовании mod 6 и mod 4, что позволило найти закономерности перевода квадратичных зависимостей в линейные.

На основании найденной закономерности была написана методика, которая, по мнению автора, при написании программы, открывает возможность значительно снижать временные затраты при факторизации чисел при использовании не вероятностных детерминированных методов математики.

По данной методике была написана программа программистом — самоучкой Белых Сергеем Алексеевичем, которая показала её эффективность. К сожалению, она не адаптирована к большим числам. Методика написана как алгоритм для составления программы, с разъяснениями. Алгоритм представлен в табличном варианте.

Каждая таблица составлена для одного из 16 возможных вариантов. Почему из 16? Для ответа на данный вопрос и получения дополнительные объяснения по методике проследуйте под кат.

Обратимся к таблице, содержащей числа первого числового ряда, номера которых принимают вид: N= 6*xy+x+y:

Таблица 1 (А)

yx	1	2	3	4
1	8	15	22	29
2	15	22	41	54
3	22	41	54	79
4	29	54	79	104

Таким образом можем заполнить любые клетки таблицы. Итак, число L ₁, номер которого N₁ находится в таблице 1(А), можно представить в виде:

L₁ = 6 ( 6xy + x + y) + 1,

где N₁ = 6 xy + ( x + y ).

При этом обе координаты числа данной таблицы положительные, но могут быть как чётные, так и нечётные. Обращаем на это внимание, так как чётнось координат, как и знак перед ними, влияет на алгоритм расчёта корреляционных зависимостей между координатами системы координат, составленной по mod 6, и координатами системы координат, составленной по mod 4. А в следствии этого и на расчёт корреляционной зависимости между номера чисел, рассчитанных по этим модулям. Это и является главными признаками, вызывающими различия при факторизации рассматриваемых вариантов.

Итак, номера строк таблицы – координаты, знак которых зависит от номера рассматриваемой таблицы, как и номера столбцов. Разность между номерами соседних чисел по строкам константа. Разность между приращениями по строкам также. Для таблиц, составленных по mod 6, эта величина равна 6. Для таблиц, составленных по mod 4, эта величина равна 4.

Если при составлении таблицы 1(А) значения первых величин для расчёта: 1,2, 3,4, 5,6…, то при составлении таблицы для чисел первого вспомогательного числового ряда, номер которого выражается как: N sub>3=6xy-x-y: -1,-2,-3,-4,-5,-6…

Таблица 3 ©

yx	1	2	3	4
-1	4	9	14	19
-2	9	20	31	42
-3	14	31	48	65
-4	19	42	65	88

Для чисел второго вспомогательного ряда получаем:

Таблица 2 (B)

yx	1	2	3	4
1	6	11	16	21
2	13	24	35	46
3	20	37	54	71
4	27	50	73	96

Таблица 4 (D)

yx	1	2	3	4
-1	6	13	20	27
-2	11	24	37	50
-3	16	35	54	73
-4	21	46	71	96

По аналогии рассчитываются и таблицы для второго числового вспомогательного ряда по mod 4.

Переходим к рассмотрению конкретного примера.

Номера числа, рассчитанные по используемым модулям, могут принадлежать как одному и тому же квадранту с используемой системе координат, так и к различным квадрантам. Но при этом всегда находятся в строгой корреляционно зависимостью между собой.

Также в строгой корреляционной зависимости находится и произведение координат, их суммы, и их разности, рассчитанные по данным модулям.

Рассмотрим закономерности методики на примере L=10525. Определяем, к какому вспомогательному числовому ряду относится данное число. Условием, определяющим принадлежность числа к первому или второму числовому вспомогательному ряду, является принадлежность к +1 классу вычетов данного числа по mod 6, или к -1 классу вычетов по mod 6.

N₆ = (10525-1)/6=1754;

Число относится к первому вспомогательному классу чисел, значить может принадлежать либо первой (А), либо третьей (С) таблицам.

Следующим этапом является определение: какую чётность могут иметь координаты рассматриваемого числа? Раз номер числа чётный, то в этом варианте обе координаты могут иметь одинаковую чётность. Предполагаем, что обе координаты – чётные. В этом варианте коэффициент перевода величины (x+y) (корректирующая величина), рассчитанной по mod 6 в значение корректирующей величины, рассчитанной по mod 4 равен 3/2 (k₆). Этот коэффициент запоминаем для сопоставления числовых рядов корректирующих величин, рассчитанных по mod 6 и mod 4. На основании номера числа по mod 6, рассчитывается числовой ряд корректирующих величин по mod 6, с интервалом, равным 6-ти. Первым значением числового ряда является класс вычетов, к которому принадлежит номер рассматриваемого числа по mod 6:

1754:6=292*6+2.

На основании полученного остатка, с учётом знака, составляем числовой ряд корректирующих величин по mod 6, с интервалом 6:

2 8 14 20 26 32 38 44 … (1)

Теперь определяем номер числа по mod 4 (аналогично определению номера числа по mod 6):

N₄=(10525-1)/4=2631;

На основании номера числа по mod 4, рассчитываем числовой ряд корректирующих величин по mod 4 с интервалом, равным 4. Первым значением числового ряда является класс вычетов, к которому принадлежит номер рассматриваемого числа по mod 4:

2631:4 =657*4+3.

На основании полученного остатка, с учётом знака, составляем числовой ряд корректирующих величин по mod 4, с интервалом 4:

3 11 15 19 23 27 31 35 39 43…

На основании коэффициента корреляции 1/k₆, переводим значения числового ряда корректирующих величин, рассчитанных по mod 4, в корректирующие величины по mod 6:

2 4,666 7,333 10 12,666 15,333 18 20,666 26 … (2)

На основании сопоставления числовых рядов (1) и (2), строим числовой ряд корректирующих величин, рассчитанных по mod 6, с интервалом 24:

2 26 50 74 98 …

Теперь, мы имеем все необходимые данные для построения числового ряда Дискрименант, на основании числового ряда корректирующих величин, рассчитанных по модулю, уже 24. И, если мы угадали с вариантом, и рассматриваемое число не простое, использование одного из полученного числового ряда обязательно обеспечит определение целочисленных координат рассматриваемого числа.

Действительно, на основании номера числа и конкретной корректирующей величины можем определить предполагаемое произведение координат и дальше по формуле:

D=(x+y)^2/(2^2)-4*xy;

В результате, получаем:

-291 -119 341 1089 2125 3449 5061 6961

Анализ закономерностей привёл к результатам, для рассмотрения которых используем рассмотрение данных таблицы 10-1. Рассмотрим данные таблицы путём рассмотрения как столбцов и строк, так и результатов в ячейках.

В первом, втором и третьем столбцах находятся изменённые, пошагово, корректирующие величины (a_i), используемые для расчёта по конкретному Дискрименанту., для первого, второго и третьего.

Корректировка для первого столбца осуществляется пошагово, начиная с первой корректирующей величины на величину, равную -4;

Для второго столбца, величина шага корректировки увеличена на 24. По аналогии, и для третьего столбца. Четвёртый, пятый и шестой столбцы рассчитаны по формуле:

D_i-[(a_i)/2]²( В_i)

По каждой рассматриваемой строке.

Седьмой столбец – разность (Р) между двумя рассчитанными, с учётом корректировки корректирующих величин, соседними значениями по конкретной строке.

Восьмой столбец – частное от деления первого рассчитанного скорректированного значения Дискриминанта на разность (Р), по конкретной строке.
При этом, целочисленное частное на основании корректирующей величины, используемой при расчётах, и шагу, равного 24, позволяет определять и корректирующую величину, равную сумме координат, и величину y, соответствующих рассматриваемому числу. В приводимом примере 2 -3*24 = — y; 2 – (-3*24) = 74 = (x+y).

Не думайте, что я дам ответы на все вопросы. Согласимся, что ответом, в настоящий момент, являются существующие закономерности. Без дополнительных расчётов истинный ответ затруднён. А для расчетов нужна программа, позволяющая вносить изменение для ответа на возникающие вопросы

Таблица 10-1

yx	1	2	3	4	5	6	7	8
1	2	26	50	-292	-288	-284	4	-73
-2	22	46	-292	-240	-188	52	52	-5,615
3	-6	18	42	-300	-200	-100	100	3
4	-10	14	38	-316	-168	-20	148	-2,135

Аннотация к методике

На основании использования вспомогательных числовых рядов по mod 6 и по mod 4. из натурального ряда чисел, вычленены составные числа и разбиты на 16 групп (вариантов). Путем сопоставления параллельных расчетов, получена возможность определять: относится или нет рассматриваемое число к предполагаемой группе составных чисел (предполагаемому варианту).

При анализе числа для определения, простое оно или нет, максимальное количество расчетов равно 4-м. Вариант расчёта рассматривается ниже. Для каждой группы чисел составлены алгоритмы расчета, формализующие анализ чисел. Для нахождения сомножителей рассматриваемого числа, разработан альтернативный способ решения квадратного уравнения с двумя неизвестными. Методика основана на найденной закономерности перевода квадратичных зависимостей в линейные, что значительно снижает при расчёте временные затраты.

Альтернативный способ решения квадратного уравнения заключается в том, что в отличии от традиционного способа, где решение ищется посредством подбора Дискриминанта, и последовательного извлечение корней квадратных, в предлагаемом способе, решение ищется посредством целочисленной соизмеримости скорректированных Дискриминантов (D_i) и разности между ними (D_(i+1)-D_i), посредством нахождения целочисленного частного при делении первой величины на вторую.

Такой подход позволяет использовать, при анализе в значительном количестве расчетов начальные, незначительные по величине значения. По каждому из вариантов расчета составлена программа, использующая возможности таблиц Excel. По мнению автора, методика после написания программы позволит находить новые закономерности в теории чисел, что должно повлиять, дополнительно, на снижение временных затрат при факторизации чисел.

Состояние вопроса (вступление к методике)

Проблема действительного разложения данного числа на простые множители одна из труднейших задач математики. В третьем столетии до н.э. Эрастофен предложил метод нахождения всех простых чисел меньших данного предела А. После некоторого усовершенствования в начале 20 века Бруном, этот способ до сих пор является единственным способом решения данной задачи без использования вычислительных устройств. Другие попытки найти законы распределения простых чисел не дали значительных результатов.

Предлагаемая работа является изложением решения этой задачи, на основании законов распределения составных чисел. Работа заключается в поиске признаков отличия простых чисел от непростых, и использовании этих признаков для определения: простое рассматриваемое число или нет. Решение этой задачи сведено нами к решению квадратного уравнения с 2 – я неизвестными. Обычно такие уравнения решаются путем подбора одного из неизвестных, в нашем случае k, но этот способ, несмотря на то, что шаг просчета нами увеличен до 24 – х, достаточно трудоемок для больших чисел.

Недостаток метода

Затруднительность и трудоемкость без использования программного обеспечения и ПК.

Достоинство метода

Возможность использования ПК и программного обеспечения, независимо от количества знаков в рассматриваемом числе. В предлагаемой работе создана, по нашему мнению, хорошая лабораторная база, пригодная для решения различных задач из области теории чисел, например, выражения куба целого числа, как суммы слагаемых первой и второй степеней. Нам известно, что при перемножении чисел со значительным количеством разрядов посредством группы ПК, могут пропадать разряды. Разработанная методика не требует использования группы ПК, так как для вычислений используются числа с незначительным количеством разрядов. Единственное продолжительное вычисление, в котором остается необходимость – это деление числа.

Проблемы с написанием программы по рассматриваемой методике привели автора к мнению, что не плохо бы попробовать объяснить в более сокращённом изложении принципы, заложенные в методике. Ведь эта попытка, возможно, заинтересует не только программистов, но и математиков, не знакомых с найденной закономерностью.

Поэтому, попытка такого изложения основывается и на том, что рассмотрение одного из вариантов методики должно обеспечить объяснение всей работы, и, также, найденной закономерности, которая может пригодиться и не программистам. При уяснении смысла работы все части методики сопоставимы для понимания.

Цель написания методики

Основная задача предлагаемой работы сводится к тому, чтобы определить, простое ли данное число L, или оно является произведением хотя бы 2-х простых сомножителей, не равных 1. В дальнейшем под словом «число» всегда понимаем целое, неотрицательное число, если не оговорено противное. На первом этапе мы применили метод сравнения по модулю.*

Любое число L может быть представлено в форме:

L = m N + r,

где:
m — заданный модуль;
N — мы назвали номером числа;
r — остаток (может быть положительным, отрицательным и равным 0), r находится в пределах от — (m — 1) до (m — 1) (При m = 6 от — 5 до + 5).

Мы выбираем m = 6. Это дает нам возможность исключить из бесконечного ряда чисел, подлежащих нашему анализу, числа, в которых присутствуют сомножители 2, 3 и 6, так как наличие этих сомножителей в числе легко распознаваемое. Все числа, подлежащие анализу, нами именуются труднораспознаваемыми.

Относительно модуля 6 все натуральные числа распределяются на 6 классов, в зависимости от остатка:

1) r = 0. L = 6 N (то есть все числа этого класса и составляют самый модуль M)
2) r = 1; L = 6 N + 1, что равнозначно r = -5; L = 6N – 5.
3) r = 2; L = 6 N + 2, что равнозначно r = -4; L = 6N – 4.
4) r = 3; L = 6 N + 3, что равнозначно r = -3; L = 6N – 3.
5) r = 4; L = 6 N + 4, что равнозначно r = -2; L = 6N – 2.
6) r = 5; L = 6 N + 5, что равнозначно r = -1; L = 6N – 1.
— * Модулем М называется система всех чисел, кратных данному числу m. Число m — наименьшее число данного модуля М. Если числа a и b при делении на m дают одинаковые остатки, то они называются сравнимыми по модулю m. Это записывается так:

a Ξ b .( mod m)

Такое соотношение между a и b называется сравнением по модулю m. Всякое число сравнимо по модулю m со своим остатком от деления этого числа на m. Например: если a при делении на m дает остаток 1, значит:

a Ξ 1; ( mod m )

если к a необходимо прибавить 1, чтобы сумма делилась на m, то

a Ξ -1; ( mod m )

В этом случае –1 называем “отрицательным остатком”. Для нас представляют интерес числа двух классов:

L(+1) = 6N + 1; L(+1) Ξ 1 ( mod 6) [ 1 ],

мы назвали их числами ветви (+1); и

L(-1) = 6N – 1; L(-1) Ξ -1 ( mod 6) [ 2],.

мы назвали их числами ветви ( — 1).

Эти числа нечетные, не делятся ни на 3, ни на 6; то есть это труднораспознаваемые числа. По аналогии рассматривается число и при использовании mod 4.

Составление таблиц, включающих номера всех непростых чисел 1-го вспомогательного числового ряда

Чтобы систематизировать все непростые числа натурального числового ряда, составлены 4 таблицы. Для компактности в таблицы мы вносим не сами числа L, а их номера N. При необходимости, зная N, можем по формулам [1], [ 2] вычислить L. И наоборот: по заданному L можем вычислить его номер N. Все таблицы составлены по принципу таблиц Пифагора.

Рассмотрим характеристики, общие для всех таблиц. В нулевой строке каждой таблицы нумеруем столбцы: 1, 2, 3, 4,… В столбце каждой таблицы нумеруем строки: 1, 2, 3, 4…

Образец таблицы:

yx	1	2	3	4		yi
1	x
2		x
3			x
4				x
…					x
xi						Ni

Нулевые строку и столбец каждой таблицы примем за оси координат, обозначив их y и x. Это утверждение основано на том, что все составные числа располагаются в четырёх таблицах (квадрантах заданной системы координат). Номера строк и столбцов, расположенные на осях координат, являются координатами чисел рассматриваемого числового ряда с соответствующим знаком (координаты номеров N являются и координатами чисел L).

Возьмем в любой клетке таблицы номер N_i числа L _i. Координатами номера N _i (и числа L _i) являются x_i, y _i. Число L_i является произведением X _i и Y _i. Запишем это в формализованном виде:

L_i = X _i У_i, где Х_i = 6 x_i ± 1; У _i = 6 у_i ± 1 [ 3 ]
L_i = 6 N_i ± 1.

N_i i внесен в таблицу (см. образец таблицы).

* в таблице выделены клетки, для которых x = y. Эти клетки составляют главную нисходящую диагональ каждой таблицы. Она берет начало от x = y = 1 и длится до бесконечности.

Автор: Iosif1

Источник