Оценка сложности комбинаторного метода факторизации чисел

Размещено на http://www.allbest.ru/

Оценка сложности комбинаторного метода факторизации чисел

Бредихин Борис Андреевич

кандидат технических наук, профессор

РИНЦ SPIN-код: 9984-6650

Аннотация

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

Таким образом, вычислительная сложность задачи о факторизации чисел на заданном интервале натурального ряда определяется сложностью наиболее трудоёмкого графа. Анализ структуры графов позволяет утверждать, что таким является граф третьего порядка. В любом графе две ветви первого уровня порождают обособленные структуры - частичные графы первого уровня с независимыми входными данными.

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

Ключевые слова: КОМБИНАТОРНЫЙ МЕТОД, ФАКТОРИЗАЦИЯ ЧИСЕЛ, СЛОЖНОСТЬ АЛГОРИТМА

Annotation

Phys - Math. Sciences

THE assessment of complexity of combinatory method of numbers' factorization

Bredikhin Boris Andreevich

Candidate of Engineering sciences, professor

RSCI SPIN - code: 9984-665

This article is devoted to the assessment of the calculating complexity of combinatory method of numbers' factorization. The content of combinatory method is explained in the article of the same name published in the journal issued in November 2016. The author supposes that the reader has learnt its content and knows the basic notions of theory of calculating complexity of the algorithms. The following results of the learning of the given task are expounded in this article. The algorithm of combinatory method permits to accomplish the parallel calculations. Graph of any order is the separate structure, because its initial data are determined independently from the other graphs. So, the calculating complexity of the task about the factorization of numbers in the predetermined interval of the positive integers is defined by the complexity of the most laborious graph. The analysis of the graphs' structure allows to state that it's the graph of the third order. In any graph both branches of the first level give the separate structures- partitive graphs of the first level with independent input data. So, the calculating complexity of the graph complete is determined by the maximal complexity of the graph of the first level. The givenat random interval of positive integers stays without changes, if we observe the sequence of the adjacent intervals. In the results it's stated that the assessment of complexity of combinatory method as well other present methods of numbers'factorization is exponential. In this aspect the combinatory method doesn't compete with other actual methods. However, evaluating the scientific significance of the algorithm, the decisive factor is not the calculating complexity, but its originality, which permits to explain (if not to discover) any properties of the positive integers. In the conclusion of the article the author describes the advantages of combinatory method, permitting to appreciate the degree of its scientific novelty

Keywords: COMBINATORY METHOD, FACTORIZATION OF NUMBERS, COMPLEXITY OF ALGORITHM

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

Сравнительный анализ структуры графов позволяет считать наиболее трудоёмким граф Снижение трудоёмкости графа с ростом его порядка обусловлено снижением длины входа по закону . Влияние этого фактора на сложность построения графа не компенсируется ростом числа уровней в графе. Этот вывод следует из анализа структуры графа.

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

Две ветви графа, произвольно выбранные на уровне n, порождают на уровне n + 1 обособленные структуры - частичные графы уровня n со стволами, , …, . Входные данные для каждого частичного графа устанавливаются в процессе построения крон на предыдущих уровнях, однако это не исключает применение параллельных вычислений.

После построения кроны уровня n и оформления стволов , , …, все части кроны уровня n + 1 могут быть построены параллельно. Например, граф со стволом после построения кроны второго уровня можно разложить на графы второго уровня со стволами вида , где(). Эти графы можно построить параллельно.

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

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

1. Пошаговая процедура построения графов

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

Рассматривается ряд нечётных чисел . Задаётся последовательность простых делителей:, 1, 2,.., , = 3.

Устанавливается множество нечётных чисел , в которых простые делители не превышают , если принять ,

Множество разбивается по определённому алгоритму на под-множества сочетаний: ,,…,,.Здесь число простых делителей в факторизациях, а = их максимально возможное число, определяемое ^Sm

Каждое подмножество представляется древовидной структурой - гра-фом порядка . Крона графа порядка имеет уровни 1 n . На каждом уровне n 1 крона состоит из отдельных частей по числу ветвей в кроне предыдущего уровня.

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

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

Ниже показаны графы = 4 и = 5 для интервала Делители , ограничивающие кроны, представлены на графах своими индексами.



Рис. 1. Граф 4,

Кроны графа построены по условию Граф содержит 150 факто-ризаций.Для его построения требуется 29 операций по вычислению.

Рис. 2. Граф 5,

Кроны графа построены по условию Граф содержит 41 фактори-зацию. Для его построения требуется 12 операций по вычислению.

2. Оценка сложности алгоритма построения графов первой версии

Задано: , 1, 2,.., , 3. Установлено, 2 . Кроны графов построены по условию

Граф 2.

Уровень n .

Применяется формула , с последующим отбором из интервала . Эта операция выполняется однократно.

Уровень n = 2.

Применяется формула ) для каждого из интервала

с последующим отбором () из интервала Число таких операций равно индексу . При достаточно больших значениях можно принимть .

Операция по отысканию() имеет вычислительную сложность T(n) O(. Сложность построения кроны графа = 2 в стандартных обозначениях будет равна: T(n). Под n понимается длина входного параметра

В частичном графе = 2 со стволом для построения его кроны

() операция () выполняется однократно.

Граф = 3.

Уровень n = 1.

Применяется формула , с последующим отбором из инте-рвала по его оценке. Эта операция является единственной.

Уровень n = 2.

Применяется формула () , для каждого из интервала

последующим отбором из интервала по его оценке.Число операций по отысканию() равно индексу При достаточно больших значениях можно принимать .

Операция по отысканию() имеет вычислительную сложность T(n)O(. Сложность построения кроны второго уровня в стандарт-ных обозначениях будет равна: T(n).

Уровень n = 3.

Применяется формула () с последующим отбором из интервала . Значения делителей в сочетаниях лежат в пределах: , , то есть не превышают и, следовательно, выполняется . В итоге операция по отысканию(, ) имеет вычислительную сложность T(n)O(.

Согласно структуре графа число делителей равно числу ветвей на втором уровне:



как сумма членов арифметической прогрессии.

если считать её суммой членов арифметической прогрессии с первым членом и последним В итоге

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

Для достаточно больших можно принимать

, .

Тогда число операций по отысканию (, ) определяется формулой

.

После исключения постоянных коэффициентов и слагаемых меньшего порядка .

В итоге вычислительная сложность построения кроны третьего уровня графа = 3 обусловлена применением формулы (, ), выполняемой раз последующим отбором из интервала. Сложность построения кроны третьего уровня и графа = 3 в стандартных обозначениях будет равна: T(n)O(.

В частичном графе = 3 со стволом для построения кроны второго уровня (выполняется однократно операция () . Для построения кроны третьего уровня для каждого из интервала (выполняется операция () . Сложность операции: T(n) O(. Число операций равно . Сложность построения кроны третьего уровня и графа со стволом равна: T(n).

3. Оценка сложности алгоритма построения графов первой версии в произвольном интервале чисел

Заданы последовательности простых чисел , . Установлено: , ,

Граф любого порядка для интервала строится, начиная с первого уровня. Во всех частях кроны каждого уровня устанавливаются делители и , определяемые по формуле

Оба расчёта выполняются одновременно для одного и того же ствола вида, их результаты связаны следующим соотношением:

= .

В этой формуле корень есть величина постоянная для каждого уровня в графе порядкана данном интервале ?x.

Граф = 2.

Уровень n = 1.

Вычисляются () и () с последующим отбором из интервала . Эти операции выполняются однократно

Уровень = 2.

Применяются формулы

с последующим отбором делителей из интервала .

Если рассматриваются смежные интервалы ?x, то делители из-вестны из предыдущего расчета, в котором они были правой границей кроны и обозначались . В этом случае оценки вычислительной сло-жности построения графа = 2 на интервалах ?x и совпадают.

При рассмотрении интервала ?x впервые в частичных графах интервала () вычисляются делители

с последующим их отбором из интервала по их оценкам. Кроны второго уровня в этих графах имеют вид.

В частичных графах интервала () выполняются операции только по отысканию с последующим их отбором из интервала по их оценкам. Кроны второго уровня в этих графах имеют вид.

В итоге вычислительная сложность построения графа будет обусловлена сложностью T(n) O(операций по вычислению и, повторенных где . В стандартных обозначениях она будет равна: T(n).

Граф = 3.

Уровень n = 1.

Вычисляются и с последующим отбором из интервала . Эти операции выполняются однократно.

Уровень = 2.

Применяются формулы

и

для всех из интервала с последующим отбором из интервала по их оценкам. Сложность операций равна:

T(n) O(. Если рассматриваются смежные интервалы ?x, то делители известны из предыдущего расчёта. При рассмотрении интервала ?x впервые вычислительная сложность построения кроны второго уро-вня будет обусловлена сложностью операций по вычислению и повторенных раз, где . В стандартных обозначениях она будет равна: T(n).

Уровень = 3.

Применяются формулы и с после-дующим отбором из интервала по их оценкам. В этой формуле ,то есть делители не превышают корня из и, следовательно, выполняется .

Если рассматриваются смежные интервалы ?x, то делители и известны из предыдущего расчета. В этом случае оценки вычислительной сложности построения графа = 3 на интервалах ?x и совпадают.

При рассмотрении интервала ?x впервые вычислительная сложность построения кроны третьего уровня графа = 3 будет обусловлена сложностью T(n) O(операций по вычислению и, повторенных числу ветвей на втором уровне графа.

.

После исключения постоянных коэффициентов и слагаемых меньшего порядка сложность построения кроны третьего уровня и графа = 3 в стандартных обозначениях будет равна T(n)O(. Таким образом, произвольное изменение левой границы интервала ?x не усложняет задачу.

4. Оценка сложности алгоритма построения графов второй версии

Задано: , = 1, 2,.., , = 3. Установлено, 2 . Кроны графов построены по условию

Граф = 2.

Уровень = 1.

Применяется формула , с последующим отбором из интервала по его оценке. Эта операция является единственной.

Уровень = 2.

Применяется формула () для каждого из интервала последующим отбором из интервала по его оценке (). Сложность операции () равна: T(n)O( Здесь - максимальное значение , допускаемое структурой графа. При достаточно больших можно принимать . Число операций () равно индексу.

В итоге вычислительная сложность построения графа = обусловлена применением формулы (),выполняемой раз последующим отбо-ром из интервала . Операция по отысканию() имеет вычислительную сложность T(n)O(. Сложность построения графа = в стандартных обозначениях будет равна: T(n).

Граф =3. Уровень = 1.

Применяется формула , с последующим отбором из интер-вала по его оценке. Эта операция является единственной.

Уровень = 2.

Применяется формула () для каждого из интервала последующим отбором из интервала по его оценке (). Здесь - максмальное значение допускаемое структурой графа. При достаточно больши. Число операций () равно индексу.

В итоге вычислительная сложность построения кроны второго уровня графа = 3 обусловлена применением формулы (),выполняемой раз последующим отбором из интервала .

Операция по отысканию() имеет вычислительную сложность T(n)O(. Сложность построения кроны второго уровня в стандарных обозначениях будет равна: T(n).

Уровень = 3.

Применяется формула () с последующим отбором () из интервала по его оценке. Число операций равно числу допускаемых структурой графа сочетаний .Значения сочетающихся делителей лежат в пределахЗдесь - максимальное значение допускаемое структурой графа. Для достаточно больших можно принимать: .

Число сочетаний вида в интервале можно представить суммой арифметической прогрессии:

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



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

= = .

В итоге вычислительная сложность построения кроны третьего уровня графа = 3 обусловлена применением формулы (),выполняемой раз последующим отбором из интервала .

Операция по отысканию() имеет сложность T(n)O( Сложность построения кроны третьего уровня и графа = 3 в стандартных обозначениях будет равна: T(n)O(.

Оценка сложности алгоритма построения графов второй версии в произвольном интервале чисел

Заданы последовательности простых чисел:, , где Установлено: , ,

,

Граф 2.

Уровень = 1.

Применяются формулы и с последующим отбором из интервала. Эти операции выполняются однократно. Уровень = 2.

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

В итоге сложность построения графа на интервале Д складывается из сложности операции () , повторенной раз и операции () , повторенной раз. Сложность операций () равна: T(n)O( При достаточно малом Д оба интервала допускаемых структурой, можно считать совпадающими, а числа операций равными.

Если рассматриваются смежные интервалы Д, то делители и известны из предыдущего расчёта, в котором они были правой границей кроны и обозначались. В итоге оценка вычислительной сложности построения графа = 2 на интервале Д равна: T(n) и совпадает с оценкой на интервале . Граф = 3. Уровень = 1.

Применяются формулы и с последующим отбором из интервала по их оценкам. Эти операции выполняются однократно. Уровень = 2. Применяется формула () для каждого из интервала и формула для каждого из интервала с последующим отбором из интервалапо их оценкам ().Здесь , - максимальные значения допускаемые структурой графа на соответствующем интервале чисел. Их индексы равны:

.

Таким образом, вычислительная сложность построения кроны второго уровня графа = 3 на интервале Д складывается из сложности операции () , выполняемойраз и операции () , выполняемой раз. Сложность операций () равна: T(n)O( При достаточно малом Д оба интервала делителей допускаемых структурой, можно считать совпадающими, а числа операций равными.

Если рассматриваются смежные интервалы Д, то делители известны из предыдущего расчёта, в котором они были правой границей кроны и обозначались. В итоге оценка вычислительной сложности построения кроны второго уровня графа = 3 на интервале Д равна: T(n) и совпадает с оценкой на интервале .

Уровень = 3.

Применяется формула () . Число операций следует считать равным числу возможных сочетаний на интервале :

= .

Применяется формула () . Число операций следует считать равным числу возможных сочетаний на интервале :

= .

При достаточно малом Д числа операций и совпадают.

Таким образом, вычислительная сложность построения кроны третьего уровня графа = 3 на интервале Д складывается из сложности операции () , выполняемойраз и операции () , выполняемой раз. Сложность операций () равна: T(n)O(

Если рассматриваются смежные интервалы ?x, то делители и известны из предыдущего расчёта. В этом случае оценки вычислительной сложности построения графа = 3 на интервалах ?x и совпадают.

При рассмотрении интервала ?x впервые вычислительная сложность построения кроны третьего уровня графа = 3 будет обусловлена сложностью обеих операций (), повторенных числу ветвей на втором уровне графа.

После исключения постоянных коэффициентов и слагаемых меньшего порядка сложность построения кроны третьего уровня и графа = 3 в стандартных обозначениях будет равна: T(n)O(.Таким образом, произвольное изменение левой границы интервала ?x не усложняет задачу.

Оценка сложности алгоритма составления таблиц факторизаций

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

Рассматривается ряд нечётных чисел .Задаётся последовательность простых делителей: , = 1, 2,.., , = 3. Устанавливается интервал чисел , в которых простые делители не превышают и интервал порядка графов 2 , где .

В левой колонке таблицы на уровнях 1 n s-1 записывается делитель На уровне n=s записывается делитель, отобранный из интервала

В очередной колонке на уровне n= s-1 записывается делитель, а на нижележащих уровнях сохраняется делитель На уровне n = s записывается делительотобранный из интервала по его оценке

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

Индекс делителя следует повышать после каждого события = до наступления события Это означает, что последнее повышение индекса на уровне n = s-1 недопустимо из-за нарушения условия Предыдущие индекс и делитель сохраняются.

В очередной колонке на уровне n=s-2 и выше устанавливается дели-тель, то есть . На нижележащих уровнях сохраняется делитель Описанный выше цикл по отысканию для возрастающих значений выполняется вплоть до наступления события . Последнее влечёт за собой установку делителей и выполнение очередного цикла. Индекс делителя следует повышать до наступления события , что означает недопустимость последнего повышения из-за нарушения условия . Это повышение отменяется, сохраняется предыдущее и соответствующий ему делитель .

Следующим этапом построения таблицы будет выполнение всего цикла отыскания для ствола, в котором . Понижение уровня вариаций делителями ствола заканчивается наступлением события при очередной замене делителя на уровне n= 2.

Далее, согласно алгоритму, необходимо варьировать делители на уровне n=1. Это означает переход к следующему частичному графу со стволом . Его таблица может быть построена по тому же алгоритму.

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

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

2. Событие наступившее при очередном повышении делителя на любом уровне n, означает неприемлемость данного значения по условию и необходимость ввести в ствол очередное значение делителя на уровне n-1. Это значение устанавливается на всех вышележащих уровнях данного ствола.

Таблица для интервала строится по алгоритму для , но для каждого ствола вида вычисляются одновременно делители ( и ().

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

Событие () означает наличие у данного ствола кроны (), которая содержит только числа интервала Эта крона существует в стволах с ().

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

Таким образом, таблица на уровне n=s в стволах с опорным делителем () наряду с () содержит левую границу кроны ().

В остальных стволах левой границей кроны согласно структуре графа служит опорный делитель .

Изложенная выше пошаговая процедура составления таблицы графа произвольного порядка позволяет оценить вычислительную сложность её реализации. В процессе составления таблицы применяется только одна формула . Опорные делители в стволе замещаются последовательно при переходе к очередному уровню. Это обстоятельство вместе с фактом позволяет считать оценкой сложности этой операции T(n)Число таких операций равно числу параметров плюс число переходов на нижележащий уровень, когда расчёт приводит к событию . Ясно, что число переходов равно числу параметров на уровнях 2 n .

Таким образом, число параметров , определяемых при построении графа, сохраняется при составлении таблицы. Однако в алгоритме составления таблицы нет операций по извлечению корней степени до включительно. Этот факт вместе с фактом сохранения числа операций позволяет считать сложность алгоритма составления таблицы равной в первой приближении сложности построения графа: T(n)O(.

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

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

Наиболее быстрыми алгоритмами факторизации являются: метод Ленстры - метод эллиптических кривых со сложностью [,1], метод Померанца - метод квадратичного решета со сложностью [,1], метод Полларда - общий метод решета числового поля со сложностью [, с], с = , метод Шенкса - метод квадратичных форм со сложностью O (.

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

Комбинаторный метод согласно приведенной выше оценке его сложности является экспоненциальным. Его можно отнести к группе алгоритмов, работающих за квазилинейное время T(n). Одним из близких к нему по сложности можно считать алгоритм сортировки слиянием, работающий за время T(n)O( Как известно, алгоритмы квазилинейного времени работают быстрее любого полинома от со степенью строго большей единицы.

Однако сравнение комбинаторного метода с существующими будет не корректным, если не иметь в ввиду, что он факторизует не число , а интервал или любой другой, как угодно малый.

В классической теории алгоритмов рассматриваются проблемы разрешимости различных задач. Вычислительная сложность полученных при этом алгоритмов не исследуется. Она является предметом исследования в теории сложности вычислений. Вычислительная сложность является характеристикой не только (и не столько) природы алгоритма. Её оценка не всегда является однозначной, ибо существенно зависит от реально существующих вычислительных машин и возможностей программирования. В связи с этим её роль в оценке научной значимости алгоритма постепенно снижается по мере снижения вычислительной беспомощности. Речь идёт о внедрении параллельных и распределённых вычислений и суперкомпьютеров с производительностью, измеряемой в пентафлопсах.

Определяющим фактором при оценке научной значимости алгоритма является не вычислительная сложность, а его новизна, позволяющая объяснить (если не открыть) какие-либо свойства натурального ряда. Ниже приведены преимущества комбинаторного метода, позволяющие оценить степень его научной новизны.

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

Алгоритм факторизации комбинаторного метода в определённом смысле слова является универсальным, так как время его выполнения зависит только от размера факторизуемого числа и не зависит от особенностей структуры и свойств числа.

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

Число графов, связанное логарифмической зависимостью с границей интервала факторизуемых чисел, с повышением границы растёт медленно, а скорость его роста стремится к нулю

Число операций по построению графа с повышением его порядка быстро уменьшается и стремится к единице.

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

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

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

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

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

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

Комбинаторный метод не конкурирует с существующими методами в решении других проблем, в том числе экзотических типа взлома ключей, имеющих сомнительное отношение к теории чисел. Однако не исключено, что его алгоритм будет востребован при дальнейшей разработке существующих методов.

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

алгоритм таблица факторизация математический

Литература

1. Бредихин Б. А. Факторизация чисел. Комбинаторный метод/ Б. А. Бредихин. - Краснодар: Издательский Дом - Юг, 2016. -184 с.

2. Бондаренко П.С. Теория вероятностей и математическая статистика: учебное пособие/ П.С. Бондаренко, Г.В. Горелова, И.А. Кацко; под ред. И.А. Кацко, А.И. Трубилина. Москва: КНОРУС, 2017. - 390 с. - (Бакалавриат).

3. Прикладная комбинаторная математика. Сборник статей/под редакцией Э. Беккенбаха. - М.: Мир, 1968. -365 с.

4. Гельфонд А. О. Элементарные методы в теории чисел / А. О. Гельфонд, Ю. В. Линник. - М.: Физматгиз, 1962. - 272 с.

5. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие/ Ш. Т. Ишмухаметов. - Казань: Казанский ун., 2011. - 190 с.

6. Сергеев Э. А. Элементы теории чисел/ Э. А. Сергеев. - Краснодар: КГУ, 1998. - 175 с.

1. Bredihin B. A. Faktorizacija chisel. Kombinatornyj metod/ B. A. Bredihin.

- Krasnodar: Izdatel'skij Dom - Jug, 2016. -184 s.

2. Bondarenko P.S. Teoryia veroyatnostey i matematicheskaya statistika: uchebnoe posobie/ P.S., Bondarenko, G.V.Gorelova, I.A. Katchko, pod redakciej I.A. Katchko, A.I. Troubilina. Moskva: KNORUS, 2017. - 390 с. - (Bakalavriat).

3. Prikladnaja kombinatornaja matematika. Sbornik statej/ pod redakciej Je. Bekkenbaha. - M.: Mir, 1968. -365 s.

4. Gel'fond A. O. Jelementarnye metody v teorii chisel / A. O. Gel'fond, Ju.V. Linnik. - M: Fizmatgiz, 1962. - 272 s.

5. Ishmuhametov Sh. T. Metody faktorizacii natural'nyh chisel: uchebnoe posobie/ Sh. T. Ishmuhametov. - Kazan': Kazanskij un., 2011. - 190 s.

6. Sergeev Je. A. Jelementy teorii chisel/ Je. A. Sergeev. - Krasnodar: KGU, 1998. - 175 s.

Размещено на Allbest.ru