Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Комбинаторный метод факторизации чисел
СообщениеДобавлено: 04 янв 2017, 14:57 
Не в сети
Начинающий
Зарегистрирован:
04 янв 2017, 14:16
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Уважаемые участники форума, выношу на обсуждение свою статью Бредихин Б.А. Комбинаторный метод факторизации чисел. Алгоритм метода приводит непосредственно к отысканию всех факторизаций и установлению всех простых чисел на любом интервале натурального ряда. Статья размещена в электронном журнале: http://ej.kubagro.ru/2016/09/pdf/122.pdf
Комбинаторный метод факторизации чисел изложен в монографии:
Бредихин Б.А. Факторизация чисел. Комбинаторный метод/Б.А. Бредихин.-Краснодар:Издательский Дом-Юг, 2016.-184 с.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторный метод факторизации чисел
СообщениеДобавлено: 25 янв 2018, 16:00 
Не в сети
Начинающий
Зарегистрирован:
12 окт 2017, 13:53
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

PS Или этот вопрос среди других и предлагается на форуме?
Конечно, те, кому тема интересна будут читать детально, чтобы получить
хотя бы какие-то оценки такого типа.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторный метод факторизации чисел
СообщениеДобавлено: 31 май 2018, 21:21 
Не в сети
Начинающий
Зарегистрирован:
04 янв 2017, 14:16
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Уважаемые участники форума, выношу на обсуждение статью Бредихин Б.А. "Оценка вычислительной сложности комбинаторного метода факторизации чисел", размещенную в электронном журнале Куб ГАУ. http://ej.kubagro.ru/2017/10/pdf/06.pdf Эта статья содержит ответы на замечания по статье Бредихин Б.А. " Комбинаторный метод факторизации чисел", размещенной в том же журнале http://ej.kubagro.ru/2016/09/pdf/122.pdf . К сожалению, разместить эти статьи на форуме не представляется возможным из-за их объема. Заранее благодарен за конструктивные замечания по этим статьям. С уважением Бредихин Б.А.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторный метод факторизации чисел
СообщениеДобавлено: 14 июн 2018, 22:57 
Не в сети
Начинающий
Зарегистрирован:
04 янв 2017, 14:16
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Отвечаю на вопрос из сообщения combilogic,благодарю за внимание к моему труду.Буду признателен за все замечания и рекомендации к статье Бредихин Б.А. "Оценка вычислительной сложности комбинаторного метода факторизации чисел", размещенную в электронном журнале Куб ГАУ. http://ej.kubagro.ru/2017/10/pdf/06.pdf

При факторизации любого числа х можно установить максимально возможное число его простых делителей sm по условию р_1^Sm≤ х и максимально возможный делитель р_m по условию 〖 р〗_m≤ р_1^(Sm-1) . Последнее позволяет установить спектр возможных простых делителей
р_1≤р_i≤р_(m )в разложении числа. Здесь р_1− минимальное простое число.
Проблему любого метода факторизации составляет отбор делителей из данного спектра в каноническое разложение числа. Однако число делителей в спектре растёт до бесконечности вместе с факторизуемым числом ,и для любого метода существует потолок применения по числу х, обусловленный прежде всего возможностями вычислительной техники, а не природой алгоритма.
Есть смысл повышать потолок метода для решения реальных практических задач, имеющих свой потолок. Повышение потолка таких задач происходит по мере снижения вычислительной беспомощности.
Однако в экзотических задачах типа взлома ключей такого потолка нет. Проблема решения таких задач обусловлена обстоятельством непреодолимой силы − неограниченностью числа х и числа его факторов. Эта проблема имеет сомнительное отношение к теории чисел. Теория алгоритмов занимается разрешимостью задач, а не преодолением их вычислительной сложности.
Таким образом определяющим фактором при оценке научной значимости любого метода факторизации является не вычислительная сложность, а его новизна, позволяющая объяснить (если не открыть) какие-либо свойства натурального ряда.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Комбинаторный метод факторизации чисел
СообщениеДобавлено: 05 авг 2018, 22:30 
Не в сети
Начинающий
Зарегистрирован:
04 янв 2017, 14:16
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
ОЦЕНКА СЛОЖНОСТИ КОМБИНАТОРНОГО
МЕТОДА ФАКТОРИЗАЦИИ ЧИСЕЛ

Введение
Бог создал натуральные числа, всё
остальное – дело рук человеческих.
Леопольд Кронекер.
Комбинаторный метод допускает параллельные вычисления и в поставленной задаче и в её фрагментах. Граф любого порядка является обособленной структурой с независимыми от других графов входными данными. Вычислительная сложность построения графа адекватна его структуре, которая определяет и сложность вычисления делителей, ограничивающих кроны, и их число на каждом уровне. Таким образом, сложность решения задачи о факторизации чисел х≤х_m определяется сложностью наиболее трудоёмкого графа.
Сравнительный анализ структуры графов позволяет считать наиболее трудоёмким граф s=3 при любом х_(m ).Снижение трудоёмкости графа с ростом его порядка обусловлено снижением длины входа по закону
k_1= (s√(s&x_m ))/(ln⁡〖x_m 〗 ). Влияние этого фактора на сложность построения графа не компенсируется ростом числа уровней в графе. Этот вывод следует из анализа структуры графа.
Структура графа любого порядка имеет следующую особенность. Две ветви графа, выбранные на первом уровне, порождают обособленные структуры – частичные графы первого уровня с независимыми входными данными. Это даёт возможность параллельного построения этих графов. Следовательно, вычислительная сложность построения полного графа определяется максимальной сложностью частичного графа первого уровня.
Две ветви графа, произвольно выбранные на уровне n, порождают на уровне n+1 обособленные структуры – частичные графы уровня n со

стволами р_(i_1 ), р_(i_2 ), …, р_(i_n ).
Входные данные для каждого частичного графа устанавливаются в процессе построения крон на предыдущих уровнях, однако это не исключает применение параллельных вычислений.
После построения кроны уровня n и оформления стволов р_(i_1 ), р_(i_2 ), …, р_(i_n ) все части кроны уровня n+1 могут быть построены параллельно. Например, граф со стволом р_(i_1 )после построения кроны второго уровня можно разложить на графы второго уровня со стволами вида р_(i_1 ) р_(i_2 ), где
р_(i_1 )=const ,р_(i_1 )≤р_(i_2 )≤р_(k_2 )(〖 р〗_(i_1 )). Эти графы можно построить параллельно.
При изменении левой границы интервала чисел х вычислительная сложность графа остаётся неизменной, если последовательно рассматриваются смежные интервалы. В этом случае ограничения крон слева известны из предыдущего расчёта.
Всё изложенное выше в равной мере относится к алгоритмам графов обеих версий. Кроме того алгоритм графа второй версии даёт возможность выделить на каждом уровне интервалы стволов, несущих одинаковые кроны, и , следовательно, уменьшить число потребных операций для построения графа.


1. Пошаговая процедура построения графов
Оценка сложности построения графа любого порядка выполняется обо-собленно, то есть по независимым входным данным и адекватно его структуре, которая определяет и сложность вычисления 〖 р〗_(k_n )и их число на каж-
дом уровне. В связи с этим сложность решения задачи о факторизации
чисел х≤х_(m ) определяется сложностью наиболее трудоёмкого графа.
Для оценки трудоёмкости любого графа целесообразно представить его алгоритм в виде пошаговой процедуры построения графа.
Рассматривается ряд нечётных чисел х. Задаётся последовательность простых делителей :〖 р〗_1≤р_i≤р_m , i = 1, 2,.., m, р_1= 3.
Устанавливается множество нечётных чисел х≤х_m, в которых простые делители не превышают р_m, если принять х_m=р_1 р_m,
Множество х≤х_m разбивается по определённому алгоритму на под-множества сочетаний: C ̅_m^2 ,C ̅_m^3… , C ̅_m^S… , C ̅_m^Sm , 2≤s〖≤s〗_m. Здесь s-число простых делителей в факторизациях, а s_m = |1+ ln⁡〖р_m 〗/ln⁡〖р_1 〗 | - их максимально возможное число, определяемое по условию 〖 р〗_1Sm ≤х_m.
Каждое подмножество C ̅_m^S представляется древовидной структурой – гра-фом порядка s. Крона графа порядка s имеет уровни 1 ≤ n ≤s. На каждом уровне n+1 крона состоит из отдельных частей по числу ветвей в кроне предыдущего уровня.
Построение графа порядка s требует вычисления только всех делителей, ограничивающих части крон. Кроны графов первой версии построены по условию р_(i_n ) ≥ р_(i_1 ), а их ограничивающие делители вычисляются по формуле 〖 р〗_(k_n ) ≤√(s-(n-1)& x_m/(р_(i_1 ) 〖р_(i_2 )…… р〗_(i_(n-1) ) ) ), 1 ≤ n ≤s. Кроны графов второй
версии построены по условию р_(i_n ) ≤ р_(i_1 ), а их ограничивающие делители вычисляются по формуле〖 р〗_(k_n )≤ x_m/(р_(i_1 ) 〖…р〗_(i_(n-1) ) 〖р_1〗^(s-n) ) , 1 ≤ n ≤s. Эти формулы дают оценку параметра р_(k_n ),по которой он выбирается из

последовательности р_1≤р_i≤р_m.
Таким образом, вычислительная сложность построения графа
определяется сложностью отыскания параметров 〖 р〗_(k_n ) и их числом. Следует иметь в виду, что эта задача решается отдельно для графа любого порядка адекватно его структуре. Кроме того, эта задача решается для частичных графов со стволами р_(i_1 ) поочерёдно.
Ниже показаны графы s = 4 и s = 5 для интервала х_m=3981. Делители
〖 р〗_(k_n ), ограничивающие кроны, представлены на графах своими индексами.
Кроны графа s = 4 построены по условию р_(i_n ) ≥ р_(i_1 ). Граф содержит 150 факторизаций. Для его построения требуется 29 операций по вычислению
〖 р〗_(k_n ).
Кроны графа s = 5 построены по условию р_(i_n ) ≤ р_(i_1 ). Граф содержит 41 фак-торизацию. Для его построения требуется 12 операций по вычислению〖 р〗_(k_n ).

Рис. 1. Граф s = 4 , р_(i_n ) ≥ р_(i_1 ).

Рис. 2. Граф s = 5 , р_(i_n ) ≤ р_(i_1 ).
    2. Оценка сложности алгоритма построения графов первой версии
    Задано: р_1≤р_i≤р_m , i = 1, 2,.., m, р_1= 3. Установлено〖 х〗_m=р_1 р_m,
    2 ≤s≤s_m 〖,S〗_(m )= | ln⁡〖x_m 〗/ln⁡〖р_1 〗 |. Кроны графов построены по условию р_(i_n ) ≥ р_(i_1 ).
    Граф s = 2.
    Уровень n =1.
    Применяется формула р_(k_1 )≤√(x_m ), с последующим отбором р_(k_1 )из последо-вательности р_1≤р_i≤р_m. Эта операция выполняется однократно.
    Уровень n = 2.
    Применяется формула р_(k_2 ) (р_(i_1 )) ≤ x_m/р_(i_1 ) для каждого 〖 р〗_1≤р_(i_1 )≤р_(k_1 )с после-
    дующим отбором р_(k_2 ) по его оценке р_(k_2 )(р_(i_1 )) из последовательности
    р_1≤р_i≤р_m . Число таких операций равно индексу k_1. При достаточно больших значениях 〖 х〗_m можно принимать k_1=р_(k_1 )/ln⁡〖р_(k_1 ) 〗 = (2√(x_m ))/ln⁡〖x_m 〗 .
    Операция по отысканию р_(k_2 )(р_(i_1 )) имеет вычислительную сложность T(n) = O(log^2 n). Сложность построения кроны графа s = 2 в стандартных обозначениях будет равна: T(n) =O(n^(1⁄2) log n) . Под n понимается размер параметра входа х_m в бинарном представлении .
    В частичном графе s = 2 со стволом р_(i_1 )для построения его кроны
    р_(i_1 )≤р_(i_2 )≤р_(k_2 )(〖 р〗_(i_1 )) операция р_(k_2 )(〖 р〗_(i_1 )) выполняется однократно.
    Граф s = 3.
    Уровень n = 1.
    Применяется формула р_(k_1 )≤ ∛(x_m ) , с последующим отбором р_(k_1 )из последовательности р_1≤р_i≤р_m по его оценке.Эта операция является единственной.
    Уровень n = 2.
    Применяется формула р_(k_2 )(р_(i_1 )) ≤√( x_m/р_(i_1 ) ) , для каждого р_1≤р_(i_1 )≤р_(k_1 )
    с последующим отбором р_(k_2 ) из последовательности р_1≤р_i≤р_m по его оценке .Число операций по отысканию р_(k_2 )(р_(i_1 )) равно индексу〖 k〗_1 .При достаточно больших значениях х_m можно принимать k_1=р_(k_1 )/ln⁡〖р_(k_1 ) 〗 = (3∛(x_m ))/ln⁡〖x_m 〗 .
    Операция по отысканию р_(k_2 )(р_(i_1 )) имеет вычислительную сложность
    T(n) =O(log^2 n) . Сложность построения кроны второго уровня
    в стандартных обозначениях будет равна: T(n) =O(n^(1⁄3) log n).
    Уровень n = 3.
    Применяется формула р_(k_3 )(р_(i_1 ) р_(i_2 )) ≤ x_m/(р_(i_1 ) р_(i_2 ) ) с последующим отбором р_(k_3 ) из
    последовательности р_1≤р_i≤р_m. Значения делителей в сочетаниях〖 р〗_(i_1 ) р_(i_2 ) лежат в пределах : р_1≤р_(i_1 )≤∛(x_m ) , 〖 р〗_1≤р_(i_2 )≤√(р_m ), то есть не превышают √(р_m )и, следовательно, выполняется р_(i_1 ) р_(i_2 )< х_m. В итоге операция по отысканию р_(k_3 )(р_(i_1 ), р_(i_2 )) имеет вычислительную сложность T(n) = O(log^2 n) .
    Согласно структуре графа число делителей р_(k_3 ) равно ω_(2 )– числу ветвей на втором уровне:
    〖λ_3=ω〗_2=∑_(i_1=1)^(k_1)▒〖[k_2 (i_1 )-(i_1-"1" ) ].〗
    Сумма∑_(i_1=1)^(k_1)▒〖(i_1-"1" )〗=k_1/2(k_1-"1")
    как сумма k_1 членов арифметической прогрессии.
    Сумма∑_(i_1=1)^(k_1)▒〖k_2 (i_1 ) 〗=k_1/2 (k_2 ("1" )+k_1 ),
    если считать её суммой k_1 членов арифметической прогрессии с первым
    членом k_2 ("1" ) и последним k_1. В итоге
    ω_2=k_1/2 (k_2 ("1" )+"1" ).
    Такой подход , как показывают расчёты, даёт небольшую ошибку даже при малых 〖 х〗_m , не занижая при этом оценку сложности алгоритма.
    Для достаточно больших х_m можно принимать
    k_1 = (3∛(x_m ))/ln⁡〖x_m 〗 , k_2 ("1" ) = ( 2 √(x_m ) )/〖√(3 ) ln〗⁡〖x_m 〗 .
    Тогда число операций по отысканию р_(k_3 )(р_(i_1 ), р_(i_2 )) определяется формулой
    λ_3=(√(3 ) √(x_m ) ∛(x_m ))/(ln^2 x_m )+(3∛(x_m ))/(2 ln⁡〖x_m 〗 ) .
    После исключения постоянных коэффициентов и слагаемых меньшего порядка λ_3=( √(x_m ) ∛(x_m ))/(ln^2 x_m ) =(〖x_m〗^(5⁄6) )/ln⁡〖x_m 〗 .
    В итоге вычислительная сложность построения кроны третьего уровня графа s = 3 обусловлена применением формулы р_(k_3 )(р_(i_1 ), р_(i_2 )) , выполняемой λ_3 раз с последующим отбором р_(k_3 ) из последовательности р_1≤р_i≤р_m. Сложность построения кроны третьего уровня и графа s = 3 в стандартных обозначениях будет равна: T(n) = O(n^(5⁄6)) .
    В частичном графе s = 3 со стволом р_(i_1 )для построения кроны второго уровня р_(i_1 )≤р_(i_2 )≤р_(k_2 )(〖 р〗_(i_1 )) выполняется однократно операция р_(k_2 )(р_(i_1 )) .
    Для построения кроны третьего уровня для каждого р_(i_1 )≤р_(i_2 )≤р_(k_2 ) выполняется операция〖 р〗_(k_3 )(р_(i_1 ) р_(i_2 )) ≤ x_m/(р_(i_1 ) р_(i_2 ) ) . Сложность этой операции: T(n) = O(log^2 n). Число операций равно: k_2 (〖 i〗_1 ) = ( 2 √(x_m ) )/〖√(р_(i_1 ) ) ln〗⁡〖x_m 〗 .
    Сложность построения кроны третьего уровня и графа s = 3 со стволом р_(i_1 ) равна: T(n) =O(n^(1⁄2) log n).
    4. Оценка сложности алгоритма построения графов второй версии
    Задано: 〖 р〗_1≤р_i≤р_m , i = 1, 2,.., m, р_1=3. Установлено∶ х_m=р_1 р_m,
    2 ≤s≤s_m 〖,S〗_(m )= | ln⁡〖x_m 〗/ln⁡〖р_1 〗 |. Кроны графов построены по условию 〖 р〗_(i_n ) ≤ р_(i_1 ).
    Граф s = 2.
    Уровень n = 1.
    Применяется формула р_(k_1 )≤ x_m/р_1 , с последующим отбором р_(k_1 )из
    последовательности〖 р〗_1≤р_i≤р_m по его оценке. Эта операция является единственной.
    Уровень n =2.
    Применяется формула р_(i_1 )(р_(k_2 )) ≤ x_m/〖 р〗_(k_2 ) для каждого〖 р〗_1≤р_(k_2 )≤〖 р〗_(i_1)^(* ) (2)
    с последующим отбором р_(i_1 ) из последовательности р_1≤р_i≤р_m по его оценке р_(i_1 )(р_(k_2 )). Сложность операции 〖 р〗_(i_1 )(р_(k_2 )) равна: T(n) = O(log^2 n). Здесь〖 р〗_(i_1)^(* ) (2)≤√(x_m ) - максимальное значение р_(k_2 ), допускаемое структурой графа. При достаточно больших 〖 х〗_m можно принимать 〖 i〗_1^* (2).=〖 i〗_2^m= (2√(x_m ))/ln⁡〖x_m 〗 . Число операций 〖 р〗_(i_1 )(р_(k_2 )) равно индексу 〖 i〗_2^m.
    В итоге вычислительная сложность построения графа s = 2 обусловлена применением формулы р_(i_1 )(р_(k_2 )) ,выполняемой 〖 i〗_2^m раз с последующим отбо-ром р_(i_1 ) из последовательности р_1≤р_i≤р_m. Операция по отысканию р_(i_1 )(р_(k_2 )) имеет вычислительную сложность T(n) = O(log^2 n). Сложность построения графа s = 2 будет равна: T(n) =O(n^(1⁄2) log n).

    Граф s =3.
    Уровень n = 1.
    Применяется формула р_(k_1 )≤ x_m/( р_1^2 ) , с последующим отбором р_(k_1 )из последовательности〖 р〗_1≤р_i≤р_m по его оценке. Эта операция является единственной.
    Уровень n = 2.
    Применяется формула р_(i_1 )(р_(k_2 )) ≤ x_m/(〖 р〗_(k_2 ) р_1 ) для каждого р_(k_2 )из интервала 〖 р〗_2≤ р_(k_2 )≤〖 р〗_(i_1)^(* ) (2) с последующим отбором р_(i_1 ) из последовательности р_1≤р_i≤р_m по его оценке р_(i_1 )(р_(k_2 )). Здесь〖 р〗_(i_1)^(* ) (2) ≤ √(x_m/р_1 ) = √(р_m ) – макси-мальное значение р_(k_2,) допускаемое структурой графа. При достаточно бо-льши〖 х〗_m можно принимать 〖 i〗_1^* (2).=〖 i〗_2^m=2/√(3 ) √(x_m )/ln⁡〖x_m 〗 .Число операций р_(i_1 )(р_(k_2 )) равно индексу 〖 i〗_2^m.
    В итоге вычислительная сложность построения кроны второго уровня графа s = 3 обусловлена применением формулы р_(i_1 )(р_(k_2 )) , выполняемой 〖 i〗_2^m раз с последующим отбором р_(i_1 )из интервала 〖 р〗_1≤р_i≤р_m.
    Операция по отысканию р_(i_1 )(р_(k_2 )) имеет вычислительную сложность T(n) = O(log^2 n). Сложность построения кроны второго уровня в стандарт-ных обозначениях будет равна: T(n) =O(n^(1⁄2) log n).
    Уровень n = 3.
    Применяется формула р_(i_1 )(р_(k_3 )) ≤ x_m/(р_(k_3 ) р_(i_2 ) ) с последующим отбором р_(i_1 )(р_(k_3 ))
    из последовательности р_1≤р_i≤р_m по его оценке. Число операций равно числу допускаемых структурой графа сочетаний 〖 р〗_(i_2 ) р_(k_3 ).Значения сочетающихся делителей лежат в пределах
    〖 р〗_2≤ р_(i_2 )≤〖 р〗_(i_1)^(* ) (2) 〖,р〗_2≤р_(k_3 ) ≤〖 р〗_(i_1)^(* ) (3).
    Здесь р_(i_1)^(* ) (3) ≤ ∛(x_m ) – максимальное значение р_(k_3 ), допускаемое структурой графа. Для достаточно больших 〖 х〗_mможно принимать: 〖 i〗_1^* (3).=i_3^m= (3∛(x_m ))/ln⁡〖x_m 〗 .
    Число сочетаний вида р_(i_2 ) р_(k_3 ) для значений 2 ≤ i_2 ≤ i_3^m можно представить суммой арифметической прогрессии:
    ∑_(〖 i〗_2=2)^(i_3^m)▒〖〖(i〗_2-1)〗=(1+ i_3^m-1)/2 (i_3^m-1)=1/2 〖〖(( i〗_3^m)〗^2-i_3^m).

    В интервале i_3^m < i_2 ≤ i_2^m число сочетаний зависит от условия х≤х_m
    и в обозримом виде не выражается. Однако ему можно дать оценку, не снижающую сложность алгоритма. Для этого достаточно считать число сочетаний следующей суммой арифметической прогрессии:
    S= ( i_3^m+1)/2 (i_2^m-i_3^m )=1/2 (i_2^m i_3^m+i_2^m-i_3^m-〖〖( i〗_3^m)〗^2 ).
    Опуская постоянные множители и члены меньшего порядка в суммах прогрессий , можно оценку числа сочетаний выразить формулой
    λ_3 = 〖 i〗_2^m∙ i_3^m = ( √(x_m ) ∛(x_m ))/(ln^2 x_m ).
    В итоге вычислительная сложность построения кроны третьего уровня графа s =3 обусловлена применением формулы р_(i_1 )(р_(k_3 )) , выполняемой λ_3 раз с последующим отбором р_(i_1 ) из последовательности р_1≤р_i≤р_m.
    Операция по отысканию р_(i_1 )(р_(k_3 )) имеет сложность T(n) = O(log^2 n). Слож-ность построения кроны n = 3 и графа s = 3 будет равна: T(n) = O(n^(5⁄6)) .

    Заключение
    Алгоритмы факторизации в зависимости от сложности делятся на экспоненциальные и субэкспоненциальные. Вычислительная сложность первых экспоненциально зависит от длины входного параметра, то есть от длины числа в бинарном представлении. Вторые работают за сверх полиномиальное время, но менее чем за экспоненциальное.
    Наиболее быстрыми алгоритмами факторизации являются:
    метод Ленстры – метод эллиптических кривых со сложностью L_n [1⁄2 ,1], метод Померанца – метод квадратичного решета со сложностью L_n [1⁄2 ,1], метод Полларда – общий метод решета числового поля со сложностью
    L_n [1⁄3 , с] , с =〖(64⁄9 ) 〗^(1⁄3) ,
    метод Шенкса – метод квадратичных форм со сложностью O (n^(1⁄4)).
    Алгоритмы, время работы которых определяется функциями n,log n ,
    n^2,и n log n, имеющими невысокую скорость роста, также можно считать быстро действующими.
    Комбинаторный метод согласно приведенной выше оценке его сложности является экспоненциальным. Его можно отнести к группе алгоритмов , работающих за квазилинейное время T(n) =O(n〖 log〗^k n). Одним из близких к нему по сложности можно считать алгоритм сортировки слиянием, работающий за время T(n) =O(n〖 log〗^2 n). Как известно, алгоритмы квазилинейного времени работают быстрее любого полинома от n со степенью строго большей единицы.
    Однако сравнение комбинаторного метода с существующими будет не корректным , если не иметь в ввиду , что он факторизует не число х_(m ), а интервал х≤х_(m ) или любой другой , как угодно малый.
    В классической теории алгоритмов рассматриваются проблемы разрешимости различных задач. Вычислительная сложность полученных при этом алгоритмов не исследуется. Она является предметом исследования в теории сложности вычислений. Вычислительная сложность является характеристикой не только(и не столько) природы алгоритма. Её оценка не всегда является однозначной, ибо существенно зависит от реально существующих вычислительных машин и возможностей программирования. В связи с этим её роль в оценке научной значимости алгоритма постепенно снижается по мере снижения вычислительной беспомощности. Речь идёт о внедрении параллельных и распределённых вычислений и суперкомпьютеров с производительностью, измеряемой в пентафлопсах.
    Определяющим фактором при оценке научной значимости алгоритма является не вычислительная сложность, а его новизна, позволяющая объяснить (если не открыть) какие-либо свойства натурального ряда. Ниже приведены преимущества комбинаторного метода, позволяющие оценить степень его научной новизны.

    Вернуться к началу
     Профиль  
    Cпасибо сказано 
    Показать сообщения за:  Поле сортировки  
    Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 5 ]

     Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
    Комбинаторный метод факторизации чисел

    в форуме Теория чисел

    borisaba

    0

    231

    04 янв 2021, 22:02

    Детерминированный метод факторизации чисел

    в форуме Численные методы

    Iosif1

    3

    563

    21 июл 2016, 20:23

    Задача на комбинаторный анализ

    в форуме Комбинаторика и Теория вероятностей

    133516

    4

    475

    08 мар 2015, 14:56

    Есть ли у гамма-функции комбинаторный смысл?

    в форуме Теория вероятностей

    ivashenko

    3

    486

    03 авг 2014, 00:37

    Изоморфизм при факторизации

    в форуме Дискретная математика, Теория множеств и Логика

    dab15

    1

    290

    27 июн 2015, 15:38

    Нахождение экстремума. Метод Фибоначчи и метод Хука-Дживса

    в форуме Исследование операций и Задачи оптимизации

    Hero525

    0

    764

    01 апр 2014, 20:39

    Метод последовательного исключения неизвестных, метод Гаусса

    в форуме Линейная и Абстрактная алгебра

    Viktoriya9977

    0

    363

    18 дек 2018, 17:14

    Выбор разных чисел из общего массива чисел

    в форуме Начала анализа и Другие разделы школьной математики

    RomanMatax

    0

    343

    12 янв 2019, 01:36

    размещение К чисел при трёхзначной сумме этих чисел

    в форуме Дискретная математика, Теория множеств и Логика

    vanvita

    0

    277

    01 ноя 2018, 13:57

    Плотность целых чисел чисел

    в форуме Теория чисел

    Kosta

    6

    687

    31 окт 2015, 13:49


    Часовой пояс: UTC + 3 часа [ Летнее время ]



    Кто сейчас на конференции

    Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


    Вы не можете начинать темы
    Вы не можете отвечать на сообщения
    Вы не можете редактировать свои сообщения
    Вы не можете удалять свои сообщения
    Вы не можете добавлять вложения

    Найти:
    Перейти:  

    Яндекс.Метрика

    Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved