Содержание текста статьи у некоторых читателей Хабра вызвало определенный интерес (судя по комментариям). Что в общем-то не удивительно, так как тема статьи весьма актуальная для современного общества – информационная безопасность. Специалисты проявляют интерес и активно разрабатывают тему с момента открытия двухключевой криптографии и односторонних функций (около 50 лет).
На самом деле проблема гораздо шире границ предметной области – информационная безопасность, что можно понять уже из рассмотрения частной задачи – факторизации числа. Математики в разных частях и странах мира на протяжении многих тысячелетий пытаются решить задачу разложения большого числа (ЗРБЧ) на множители – найти операцию обратную умножению, но до сих пор без особого успеха. Числа с разрядностью нескольких сотен пока разложить на множители не удается.
Известно несколько подходов к решению проблемы (алгоритм Ферма, числовое решето, эллиптические кривые, CFRAC, CLASNO, SQUFOF, Вильямса, Шенкса и др.), которые критикуются и не кажутся перспективными и которые даже не претендуют на универсальность. Автором публикации предлагается оригинальный подход к решению проблемы с претензией на универсальность, т.е. без каких либо ограничений на факторизуемые числа, в частности, ограничений на разрядность чисел.
Появилась уверенность, что по крайней мере читатели domix 32; wataru; Naf2000 понимают, что в моих статьях идет речь о модели, так как вопросы задаются осмысленные.
Здесь важно понимать в рамках какой модели числа разрабатывается алгоритм поиска делителей (сомножителей) заданного составного числа, допущения, ограничения, требования и другие условия модели. Понимать какое влияние они оказывают на характеристики, в частности, на длительность процесса поиска решения. Известные в настоящее время подходы и алгоритмы не обеспечивают с приемлемыми временными характеристиками получение решения.
В настоящее время ситуация с моделированием чисел и факторизацией как пишут Манин и Панчишкин близка к тупику или уже в тупике.
Введение
По мере изложения текста используются аббревиатуры (сокращения), которые я собрал в одном месте для удобства читателя. Эти сокращения мной используются во всех статьях.
Аi — аттрактор, значение кратное большему делителю;
СММ — списочная многострочная модель числа;
ЗРД — закон распределения делителей (dm – меньший, dб – больший делители);
ЗФБЧ – задача факторизации больших чисел;
НОД – наибольший общий делитель;
НРЧ — натуральный ряд чисел;
ПНЧ — последовательность нечетных натуральных чисел;
РЦЧ – ряд целых чисел;
ИБ — информационная безопасность;
КВВ — квадратичный вычет элемента КЧКВ по модулю N;
КВК — квадратичный вычет элемента равный полному квадрату;
КЧКВ— конечное числовое кольцо вычетов по модулю N;
СННЧ — составное нечетное натуральное число;
ТКВК — тривиальная непрерывная область строк модели, содержащая все КВК;
ТССС — тривиальная область строк модели, содержащая все средние вычеты, сохраняющие смежность сомножителей;
РИ — решающий интервал, замкнутый числовой интервал нечетной длины, центр (ЦРИ х) которого характеризуется КВК, а границы кратны делителям модуля N;
НИ — накрывающий интервал, интервал нечетной длины (равен dm), содержащий кратное
х = idб;
ДЦ, ДIn, Д0, — дубли строк центральной, первой (инволюций), последней (нулевой).
Несколько фактов. Теорема факторизации (здесь), модель полного и усеченного НРЧ (здесь). Вопрос о КВВ рассматривался академиком РАН в работе УДК 511. статья В. И. Арнольда (2010 года) «Случайны ли квадратичные вычеты?» Редакцией получено 28 декабря 2009 г. Именно эта статья стимулировала мою работу над Законом распределения делителей завершенную и опубликованную мной в 2014. Я был удивлен, что академик предполагал КВВ случайными. Сам факт появления статьи Арнольда говорил о слабой изученности КВВ конечного кольца. На самом деле именно КВВ=КВК кольца несут в себе информацию о делителях составного модуля.
Левые вычеты полные квадраты КВВ = КВК являются детекторами решающих интервалов для факторизации N. Для установления является ли число полным квадратом определяется его флексия: две последних цифры. Все квадраты заканчиваются одной из 25 пар цифр, но не только квадраты. Поэтому, если нужная пара обнаружена, то завершается проверка извлечением корня.
Аналогично устанавливается у числа свойство разложимости на смежные сомножители, т. е число
rc или rccc. Для этого средний вычет rс представляют приближенно разложимым. Из первого в списке rc извлекают корень в =√rc округляют в меньшую сторону, а другой сомножитель получают как сумму первого в+1 с единицей. после чего их перемножают rccc = в∙(в+1). Следующий просто больший rccc = (в+1)(в +2) и т. д.
В предлагаемой вниманию читателей статье рассматриваю модель составного полупростого бесквадратного числа. В основание модели кладется конечное числовое кольцо вычетов (КЧКВ) по составному модулю N, представленное начальным фрагментом натурального ряда чисел (НРЧ), закон распределения делителей (ЗРД здесь) натурального числа и принцип погружения аддитивной модели N = х1 + хо в множество подобных.
Подробно излагается устройство модели, описываются в деталях ее отдельные элементы и крупные части – тривиальные области строк модели. Но поскольку материал достаточно обширный то описания части свойств модели предполагается разнести на несколько статей, в которых будут рассматриваться вопросы о свойствах модели. В статьях. о симметрияx и о разложении модели на подмодели сами эти явления.
Так, например, двухключевой шифр RSA и ему подобные, задается и реализуется над конечным числовым кольцом вычетов (КЧКВ) по составному модулю N = p∙q. Центральной идеей атаки на шифр рассматривается задача факторизации (разложение на множители) модуля кольца.
В моих публикациях в рамках нового направления (не решета, не эллиптических кривых) предложена оригинальная модель, обеспечивающая разложение составного натурального числа N на множители. Направление основано на использовании понятия решающего интервала (РИ) и Закона распределения делителей (ЗРД) натурального числа N = p∙q, где p и q – простые числа (публикация 2014 года).
Действительно, для любого составного натурального числа N (33, 65, 91 и др.) можно построить табличную модель (СММ, СМ-модель)..При допущении, что делители N известны элементы строк модели можно разметить заливкой (цветом). Строки, содержащие элементы кратные делителям N, назовем кратными строками. Такие строки регулярно распределены по списку с шагом (dm меньшего делителя) и с шагом (dб большего делителя).
Между строками, кратными разным делителям возникают интервалы строк некратных. Такие интервалы строк (без заливки) могут быть двух типов: с четным числом строк и с нечетным.
Пример. Пусть N = 77. Зафиксируем строку с хо = 1∙dб = 11 и вычислим интервалы, которым принадлежит строка. Для этого найдем меньший номер малого интервала с границей превышающей хо =1∙dб. Это будет второй (2∙dm) интервал (его левая граница Гл = 8, а правая граница Гп = 2∙7 = 14> 11). Разность 14 –11 = 3 включает элементы (12,13,14) нечетное число и среди них нет кратного dб. Достроим этот интервал до замкнутого [11,12,13,14].
Теперь его границы стали кратными разным делителям, но изменилась длина – стала четной. Интервал не может быть решающим. Слева от dб = 11 разность 11 – 8 = 3 формируем замкнутый интервал [7, 8, 9, 10, 11]. Его длина нечетна, есть центр (ЦРИ = 9), КВВ в этом центре полный квадрат 92 (mod 77) = 4. Границы РИ обе кратны разным делителям – простые числа, Гл=7, Гп=11 следовательно, они и реализуют разложение N = 77 = 7∙11.
Такие четные интервалы будем дополнять на левой и правой границах кратными разным делителям строками и рассматривать замкнутые интервалы, которые будут содержать нечетное число строк. В таблице 77 это интервалы [7, 8, 9, 10, 11]; [22, 23,24, 25, 26, 27, 28]; [33, 34, 35]. Их центральные строки имеют номера хо = 9, 25, 34, а квадратичные вычеты всегда – полные квадраты: 92(mod 77) = 4; 252(mod 77) = 9; 342(mod 77) = 1. Могу указать не выделенный цветом интервал, например, с центром хо = 18, т.е. [14, 15, 16, 17, 18, 19, 20, 21, 22] его границы: левая Гл =14 =2∙7, правая Гп =22 =2∙11 кратны разным делителям, а в центре КВВ (182(mod 77) = 16 ) полный квадрат. Все такие интервалы названы решающими интервалами (РИ) так как они обеспечивают факторизацию модуля N..
Вначале рассмотрим небольшой пример N = p∙q = 77. СМ-модель из 3-х колонок (строк)
Таблица 77. Фрагмент НРЧ и квадратичных вычетов по модулю N = 77
Тривиальная область строк ТКВК (слева в табл.77желт.) в факторизации не участвует. Синий цвет числа кратные большему делителю (dб) - зеленый кратные меньшему (dm)
Её квадраты дублируются в строках – центрах решающих интервалов (ЦРИ = 9,16,18,25,27,34 нижняя строка) им соответствуют полные квадраты (КВК = rл = 4, 25, 16, 9, 36, 1 верхняя строка чисел). Все эти квадраты в центральных строках замкнутых интервалов нечетной длины. Натуральный ряд (фрагмент представляющий кольцо) сам разместил квадраты таким удивительным образом. Границами замкнутых интервалов являются значения кратные делителям модуля. Рекомендую для полного понимания внимательно перечитать этот абзац – он главный в ЗРД.
Для экспериментов и решения ЗФБЧ зададим значение модуля КЧКВ равным произведению двух простых чисел N = p∙q = 629. Кроме этого значения нам в общем случае больше ничего неизвестно.
В табл. А приведены характеристики (координаты х центров РИ и квадраты в них) 24-х решающих интервалов, возникающих в СММ для модуля N = 629 кольца (из табл. Б).
Пример А. Для модуля кольца N = 629 найти делители (разложение на простые сомножители).
Решение можно получить в любом решающем интервале. Выбираем РИ, например, с центром в
х = 44. В этой точке числовой оси квадратичный вычет по модулю N равен 442(mod N) = 49. Границы решающего интервала: левая хол = 44 – √49 = 44 – 7 = 37 = dб; – правая хоп = 44 + √49 = 44 + 7 = 51= 3∙17. Левая граница РИ простое число 37 – есть уже делитель модуля, правая – утроенное простое число 17 = dm – меньший делитель модуля. Разложение N = 17∙37 = 629.
Если поменять точку ЦРИ на х = 61, то в ней КВК = 576 = 242. хол = 61 – √576 = 61 – 24 = 37 = dб; хоп = 61 + √576 = 61 + 24 = 85= 5∙17 делители те же самые и N = 17∙37 = 629.
Этот пример иллюстрирует возможность факторизации любого составного числа (и 33, и 65, и пр.) с использованием закона распределения делителей натурального числа. За областью ТКВК (непрерывная желтая область строк) возможно формировать строки таблицы и проверять левую позицию строки: квадрат или нет? Как только получили квадрат – ЦРИ, фиксируем (∙) х, в которой квадрат получен (дальше см. пример А).
Здесь мы используем перебор строк, но не тотальный, так как квадратов в модели √N. Это самая простая схема факторизации без использования частных случаев. Но и такого перебора можно избежать, используя свойства модели, построив зависимости переменных модели (частные случаи). В МА все интегралы и производные – частные случаи (см. Рыжик и Градштейн).
Вся математика вообще и ее модели – частные случаи.
Модель числа строится на простой концепции: представления числа N = х1 + хо суммой двух слагаемых. Список всех возможных таких сумм включаем в таблицу модели, которую назовем списочная многострочная модель (СММ) числа. При таком подходе любое (N =629) составное число (бесквадратное) представимо конечным числом хомах = ½(N –1)=314 строк моделей (способов, линейных форм) из двух слагаемых х1 + хо = N, х1> хо, среди которых будут регулярно встречаться представления со слагаемыми кратными разным делителям N.
Таблица Б - Списочная многострочная модель составного числа N=629
Каждая реализация суммы N = х1 + хо погружается в множество подобных моделей (метод погружения). Начальный фрагмент натурального ряда чисел (НРЧ) из N элементов преобразуется в такое кольцо (КЧКВ), а затем в множество таких сумм (моделей числа) с постоянным значением N. Суммы выписываются построчно в таблицу (список) и значения хо пробегают диапазон хо = 1(1) хомах. С другой стороны, для построения модели делаем временное допущение, что делители р и q известны. После этого удобно сделать разметку элементов модели заливкой, например, (синий цвет) все элементы модели кратные делителям. Такие строки будем называть кратными.
Предложенная модель числа открытая (допускает введение новых переменных – столбцов), изначально это многострочная таблица (всего из двух столбцов х1 и хо) может и будет дополняться другими столбцами. Первым (левый) столбец таблицы заполним значениями квадратичных вычетов (КВВ) по модулю N элементов х1 и хо. КВВ обоих слагаемых займут один столбец, так как квадратичные вычеты х1 и хо в каждой строке всегда совпадают
rл = х12 (mod N) = хо2 (mod N).
Анализ СММ и ее областей
Анализ списка СММ начнем с локализации, (с уточнения положения) строк, содержащих ключевые элементы КЧКВ, и характерных линий.
Существует область из четырех смежных строк («четверка» хо = 127,128,129, 130), в которой нижняя пара строк кратна одному делителю (dб), а верхняя – другому (dm) делителю. Между этими парами отсутствуют некратные строки. Средняя линия четверки, разделяющая ее пары, соответствует (симметрична относительно центра СММ) строке с нетривиальными инволюциями. Она размещена симметрично строке нетривиальных инволюций относительно центральной строки (хо = ½ 314 = 157) СММ.
Идемпотенты кольца – элементы кратные разным делителям, в СММ размещены в смежных строках. Пара строк с идемпотентами (хо (ID) = 221, хо (Id) = 222) разделяется линией, симметрично расположенной относительно строки центра СММ строке-дублю нулевой строки с номером (хо = 93). Строка-дубль нулевой строки всегда имеет номер равный половине четной нетривиальной инволюции.
Из анализа положения строк КЧКВ, содержащих ключевые элементы следует, что эти строки занимают не произвольные (случайные) положения в кольце вычетов по модулю N, но их положение связано между собой самым тесным образом.
Тривиальная область ТКВК
Все КВВ, начала левой колонки, следующие подряд и равные полным квадратам (КВК), выделяем (желтым цветом). Наибольший квадрат хо2 < N называется порогом тривиальной области квадратов. Эти квадраты образуют ТКВК – тривиальную область квадратов с границей (порогом) хо = 25 = √ N. Такие квадраты ниже порога ТКВК встречаются повторно (дублируются) в других строках списка модели и в другом порядке. Порядок следования квадратов в списке модели определяется ЗРД.
Второй столбец отводим переменной х1, а третий – хо. В четвертый столбец таблицы будем вписывать разности t = х1 – хо слагаемых строки. Уже эта упрощенная модель числа N богата свойствами. Но продолжим.
Столбец разностей t = х1 – хо представляет собой фрагмент другой числовой последовательности – последовательности нечетных чисел (ПНЧ). В модели СММ элементы этого фрагмента монотонно возрастают от 1 до N – 2 при движении снизу списка в верх по строкам. В каждой строке таблицы значение числа t представляется суммой 2-х смежных слагаемых t = t1 + tо, t1 = tо +1. Слагаемые этой суммы перемножаются р(t) = t1 × tо и произведения р(t) помещаются в 5-ю колонку таблицы.
При превышении произведением р(t) модуля N выполняется приведение по модулю, а результат приведения помещается в 6-ю колонку таблицы rс = t1 × tо(mod N), за которой следует 7-я, содержащая фрагмент ПНЧ, но направленный уже сверху вниз. Отметим, что фрагменты ПНЧ также регулярно включают кратные делителей N, но только с нечетными коэффициентами. Для колонок 5, 6 и 7 выполняем разметку элементов кратных делителям (синий цвет). Последние две колонки 8-я и 9-я связаны с произведениями элементов КЧКВ 8-я колонка это р(х) = х1 × хо, а приведенное значение этого произведения по модулю N – это 9-я колонка rп = х 1× хо (mod N) – правый вычет.
В теории чисел при решении квадратичных сравнений х2 = rл (mod N) возникают четыре решения (корня), т.е. х1 и хо в двух строках модели. Квадратичный вычет в обеих строках один (общий), а х1 и хо разные (4 значения). Такие строки дублируют вычеты и называются дублирующимися.
Значения rл, rс, rп – это значения трех вычетов (левого, среднего и правого) каждой строки. При дублировании строк значения этих вычетов сохраняются неизменными.
Рассмотрим подробно заполнение 6-й колонки средними вычетами.
Тривиальная область ТССС
Средние вычеты (6-я колонка) бывают двух сортов: либо образованы смежными сомножителями (rссс), либо нет. Значения 5-й колонки всегда произведения смежных, но они часто превышают модуль N и их приводят по модулю. После редукции (приведения по модулю) малая часть средних вычетов сохраняет сомножители (уже уменьшенные) смежными (это свойство =ССС) они помечаются (зеленый цвет заливки) и обозначаются
rс = rссс, а большая часть rс не раскладывается в смежные сомножители..
Средние вычеты со свойством (ССС) дублируются независимо и оказываются рассыпанными (как-то распределены) по списку модели. Но в нижней части столбца (6) средних вычетов те, что обозначены как rссс собираются вместе и упорядочиваются по возрастанию. Это множество строк – образует другую тривиальную область строк обозначаемую ТССС, элементы rccc которой включается в колонку (Rс). Колонка (6) возникает при разложении разности (х1 – хо = t = t1 + tо) в сумму смежных слагаемых (t1 = 1+ tо) и последующего перемножения этих слагаемых rc = t1 ˖ tо.
Эти же значения можно получить другими путями. Рекуррентно, суммируя rci = rci-1 + tпi
предшествующий вычет, с i-м элементом колонки Тп. Например, (для N = 629) верхний rccc при tпi = 9, хоi = (9 + 1):2 = 5, t = N – 10 = 619 =309 + 310; 309˖310(mod N = 629) = 182 .
Для нижнего rccc имеем t = N – 44 = 585 =292 + 293 ; или 292˖293(mod N = 629) = 12 .
Заключение
В работе показано направление моделирования числа, отличное от известных, и его возможности решать задачу факторизации составного числа, рассматриваемого как модуль приведения кольца.
Основу модели образуют алгебраическая структура - конечное числовое кольцо вычетов по составному модулю, представляемое фрагментом натурального ряда чисел, дополненного квадратичными вычетами элементов кольца. в котором существенными являются полные квадраты.
Такие квадраты становятся центрами решающих интервалов, с границами кратными делителям модуля приведения кольца.
Комментарии (21)
domix32
14.05.2025 13:24В работе показано направление моделирования числа, отличное от известных, и его возможности решать задачу факторизации составного числа, рассматриваемого как модуль приведения кольца.
решать задачу факторизации с предположением о том что мы знаем это разложение как-то странно.
Пусть A1 будет предположением, что мы не знаем факторов.
Следствием С1 будет то, что мы не можем раскрашивать что-то, кроме квадратов и смежных сомножителей, которые имеют тривиальную проверку.
Алгоритма нахождения любого из центров решающих интервалов за пределами тривиальной области при истинности A1 не описано.
Алгоритма нахождение секции "четверки" при истинности A1 не описано.
Доказательств, что область четверок всегда существует нет.
Как помогают инволюции и индепотенты искать факторы не описано. Форма инволюции никогда не была представлена в явном виде.
Алгоритма нахождения индепотентов при истинности A1 не описано.
Алгоритма нахождения секвенций, которые суммируются в N при истинности A1 не описано.
Попытка найти любое из этих значений при помощи таблицы пока что сводится к брутфорсу значений до меньшего из факторов, либо использование вышеупомянутых способов продвинутой факторизации.
domix32
14.05.2025 13:24Ну и было бы неплохо взять пример побольше. Как например факторизовать 1000175531675759323?
VAE Автор
14.05.2025 13:24Для примера решение: р=1000082623; q =1000092901 (за доли секунды).
Предположение о факторах нужно не для поиска факторов, а для построения модели поиска (вывода) формул, по которым эти факторы вычисляются.
1. Модель не используется, если формулы получены.
2. Моделью без раскраски кратных строк можно воспользоваться (факторы мы не знаем) для поиска полных квадратов (левых вычетов, т.е. КВВ). Можно строить не всю строку, а только левую колонку и даже глазами легко обнаружить 1, 4, 9 , и др. малые квадраты, но можно и автоматизировать этот процесс.
3. Я рассматриваю только формульный алгоритм (перебор отвергается), хотя при наличии СММ используются простые делители не до корня из N , а до ближайшего полного квадрата. Используется ЗРД.domix32
14.05.2025 13:24Вопрос был как пользоваться тем что вы описываете, а не какой ответ. Мы можем взять произвольное число до корня из N и получить полный квадрат из тривиальной области, только как это помогает находить факторы? Вы буквально четвёртым шагом дорисовываете остатки совы.
Рисуем круг: Берём x1 * x1 mod N == k * k Рисуем второй круг: Смотрим в столбец 5 ??? Дорисовываем остатки совы: Фактор p = число1, q = число2, в строке число3 - индепотент, инволюция PROFITКонечно может вы савант и как-то из рукава все эти числа спавните, но нам-то калькуляторам как это обходить?
wataru
14.05.2025 13:24(за доли секунды)
Простенькая переборная программа по самому наивному, известному сотни лет методу, тоже работает за доли секунды.
Можно строить не всю строку, а только левую колонку и даже глазами легко обнаружить 1, 4, 9 , и др. малые квадраты, но можно и автоматизировать этот процесс.
Вы просто описали полный перебор для поиска КВК. Это тривиальная идея. На практике обычно не используемая, потому что она не быстрее самого наивного перебора выше в общем случае.
Тут вся ваша таблица, раскраски и определения не нужны вообще. 99.99% текста из ваших статей можно взять и выкинуть, ибо они для этого не нужны вообще.
Все это одна формула:
нашли такой x - можем разделить. Как искать такой x вы не придумали.
domix32
14.05.2025 13:24это все по mod N?
wataru
14.05.2025 13:24Нет. x дает квадртаичный вычет - полный квадрат. Т.е. x^2 - дает полный квадрат по модулю N. т.е. x^2 = k^2 (mod N), k^2 < N.
Отсюда уже следует, что x^2 = mN+k^2 для какого-то m. Просто по определению остатка от деления. Если x - не тривиальный (КВК как его называет автор), то m>0.
VAE Автор
14.05.2025 13:24Согласен, что в последних статьях описания не приводятся. Моей задачей являлось довести смысл Закона распределения делителей (ЗРД). Хочу чтобы он вам всем был понятен. Кстати он доказывается по индукции, но если вы предложите другое доказательство буду рад познакомиться с ним.
ЗРД числа - основа и модели и концепции и направления поиска факторов.
VAE Автор
14.05.2025 13:24>Как помогают инволюции и индепотенты искать факторы не описано. Форма инволюции никогда не была представлена в явном виде
В математике задача вычисления инволюции и идемпотентов кольца не решена. В моей статье "Разложение модели на подмодели. Ч1" показано явно, что нетривиальная инволюция попадает в строку с тривиальной инволюцией. Программа сама ее нашла, что не планировалось и не ожидалось (там см табл.2 и табл.3) Что дало такой результат я не знаю, пока обдумываю.
Номера строк идемпотентов (они смежные, для N = 629, это хо=221 и хо =222) в СММ в сумме всегда дают нечетную нетривиальную инволюцию (IN = 221 +222 = 443). Для N =407, хо = 110 и xо = 111, IN = 110+ 111 = 221 Её окаймляющие строки (х1 и хо) кратны разным делителям
>Алгоритма нахождение секции "четверки" при истинности A1 не описано
Для N =629 нетр. инволюция лежит в строке 29-го слоя окаймления (снизу) центральной строки (хо = 157). Строка четверки хо =128 в строке окаймления (сверху), её КВВ =30, а разность КВВ =КВК =1 инволюции и КВВ 128 строки равна номеру слоя: окаймления центра КВВ(128) - КВВ (186) = 30 - 1 = 29. Об этом я писал в статье о симметриях.
Для N = 407 нетр. инволюция лежит в строке 186 - 102 = 84 слоя окаймления (снизу) номер центральной строки (хо = 102). Строка четверки хо=102 - 84 =18 в строке окаймления (сверху), её КВВ =324, а разность КВВ =КВК =1 инволюции и КВВ 18 строки равна номеру слоя: КВВ(186) - КВВ (18) = 1 - 324 = -323 = 84. Об этом в статье о симметриях.domix32
14.05.2025 13:24В математике задача вычисления инволюции и идемпотентов кольца не решена
Если она не решена, то откуда вам известно, что это именно инволюция/индепотент без скармливания её в некоторую функцию?
Номера строк идемпотентов
откуда они появились?
Для N =629 нетр. инволюция лежит в строке 29-го слоя окаймления (снизу) центральной строки (хо = 157).
Меня абсолютно не интересует где они лежат, меня интересует как вы получили значение 157 или 29, 186, 102 и тп. Почему 102 подошла, а 177 нет? Половина этих строки находят дальше N/2 и для больших чисел и если у нас число в тысячах бит, то мы не можем ожидать, что мы пробежим эту половину с каким-то фильтром как вы их выбрали для произвольного N?
VAE Автор
14.05.2025 13:24>Если она не решена, то откуда вам известно, что это именно инволюция/индепотент без скармливания её в некоторую функцию?
Это известно по определению инволюции (я их обозначаю меньшую (In) и большую (IN)) и идемпотентов (не индепотентов, они обозначены (Id) - меньший и (ID) -больший)
> Номера строк идемпотентов откуда они появились?
В списке СММ строки идемпотентов смежные. Для меньшего Id = хо^2 (modN) =xо, для большего ID =хо -1
>Для N =629 нетр. инволюция лежит в строке 29-го слоя окаймления (снизу) центральной строки (хо = 157).
Центральная строка - это центр списка в ней для N =407, t = tп = 203 или могут различаться на 2 для N = 629, t=315 и tп =313. Можно найти иначе хц = rпо=157.
хц = 102 = rло для N =407 потому и подошла. Для N = 629 xц =157= rпо. Для центральной строки окаймляющие строки расположены в слоях 1-ом, 2-ом и т. д. симметрично. Для инволюции имеем номер хо(In) =186 т.к. ее левый вычет (rл = 1) и она лежит в 186 - 157 = 29 слое. Номер слоя всегда равен разности левых вычетов окаймляющих строк слоя. Одна из строк (четверки кратных) имеет хо =157- 29 =128 и её левый вычет rл = 30. Эта строка симметрична инволюции относительно центра. Разность rл -rл = 30 -1 =29 показывает, что это именно так.
> мы не можем ожидать, что мы пробежим эту половину с каким-то фильтром как вы их выбрали для произвольного N?
Пока выбирал визуально, формулы надо искать для инволюции, о чем уже говорилось.Ответить domix32
domix32
14.05.2025 13:24Это известно по определению инволюции
по определению инволюции вы можете скормить некоторых x в функцию f(x), положить полученный результат в ту же функцию и получить x обратно. Вы не можете коронвать конкретные числа инволюциями "по определению" не имея функции.
Для меньшего Id = хо^2 (modN) =xо, для большего ID =хо -1
Есть контакт.
это центр списка в ней для N =407, t = tп = 203 или могут различаться на 2 для N = 629, t=315 и tп =313. Можно найти иначе хц = rпо=157.хц = 102 = rло для N =407 потому и подошла.
То бишь
Пока выбирал визуально
и для 1000175531675759323?
wataru
14.05.2025 13:24Этот пример иллюстрирует возможность факторизации любого составного числа (и 33, и 65, и пр.)
И как же раскладывается 33? Без постройки таблицы. Как вы эти интервалы решающие-то ищите?
Для модуля кольца N = 629 найти делители (разложение на простые сомножители).Решение можно получить в любом решающем интервале. Выбираем РИ, например, с центром в х = 44.
Вот как мы выибираем РИ - это и есть основной вопрос. Если вам выдать КВК, то факторизация понятно как делается. Вы тут перебором же ищите? До корня из N вариантов, похоже:
Здесь мы используем перебор строк, но не тотальный, так как квадратов в модели √N.
Так ведь тривиальный метод факторизации такой и есть: перебираем все числа до √N, смотритм, делится ли на них N. Все. Ваша модель тут вообще не нужна, ничего не ускоряет и не помогает и смысла не несет.
такого перебора можно избежать, используя свойства модели, построив зависимости переменных модели (частные случаи)
Ага, вот уже и не "модель позволяет решать проблему факторизации", а некоторые частные случаи можно по каким-то зависимостям, выведенным на частных случаях таблицы, решить.
Скажите, а вот случай, что если число заканчивается на цифру 5, то можно поделить на 5 - он достоин звания Модели? Он вообще полезен?
Что бы показать ценность вашей модели, вы не подбирайте примеры, на которых они работают, а формализуйте их, выпишите критерии в виде формул и оцените, как часто они встречаются. Например ваш пример с rccc+1 раскладывающимся на множители работает для N, т.ч. √(3N+4) - целое.
VAE Автор
14.05.2025 13:24Не могли бы Вы сменить тональность комментариев (получается, что я что-то вам должен. Не смените общение прекратим. Научитесь уважать собеседника )
Вы с таблицей 77 можете разобраться? Если нет, то я не знаю как помочь.
В таблице модели на РИ указывают КВВ=КВК, т.е. полные квадраты.(их шесть для N = 77).
Первый КВК = 4 примыкает к ТКВК.. Её получаем без построения таблиц. Вычисляем порог (=8) и продолжаем получать КВВ (в (.) 9) КВВ =КВК =4) пока не встретится КВК. Для 33 ответ уже был (признаки делимости используются в любой атаке)
Как только поймете ЗРД, дойдет, что даже перебор не требует числа корня из N, а существенно меньше.Вы просто описали полный перебор для поиска КВК. Нет не полный, а до 1-го РИ
wataru
14.05.2025 13:24Для 33 ответ уже был (признаки делимости используются в любой атаке)
Но ведь 33 - это лишь пример, в котором ваши частные случаи не сработали. Если вы эти частные случаи опишите, я вам могу и 15-значное число найти, которое под них не подходит, где признаки делимости не сработают.
В прошлых статьях вы не указывали, что в общем случае у вас будет перебор для поиска КВК, а лишь фокусировались на удачных примерах. Для 33 методы из ваших примеров не работали и это должно было или заставить вас описать другой частный случай, или признать перебор. Тут вы уже перебор признали, так что 33 уже не так важно.
Как только поймете ЗРД, дойдет, что даже перебор не требует числа корня из N, а существенно меньше.
Тривиальный перебор тоже не всегда требует корня из N. Он идет до минимального из двух делителей p и q. В худшем случае это может быть примерно до конрня из N.
ЗРД - это про то что КВК в центре с двумя числами, кратными делителям N? Это очевидный факт, показанный в формулах в моем комментарии выше: https://habr.com/ru/articles/908714/comments/#comment_28306208. Да, если у вас есть КВК, ясно как его использовать для получения делителей. ЗРД у вас нигде не говорит о распределении КВК, как далеко они друг от друга расположенны и как долго их искать.
Для 77, вы пишите:
Первый КВК = 4 примыкает к ТКВК.
За ТКВК идет 9. Вот мы уже знаем, что 9^2 = 4 (mod 77), или 9^2 = N+4. Отсюда сразу можно найти N=9^2 - 2^2= (9-2)(9+2) = 7*11. Вы в тексте что-то вычисляете в ваших терминах, но это излишне запутанные терминами вычисления, которые проще, понятнее и логичнее заменить простой арифметикой выше.
Тут нам очень повезло, что КВК оказался сразу за ТКВК (иными словами, ceil(sqrt(N)) оказался КВК). Это редкий частный случай. Для чисел до миллиона из двух простых делителей таких чисел 1409 из 288533. Всего 0.4%. Для чисел до 100 миллионов этот процент снижается до 0.1%. Чем больше числа, тем реже такие удачные встречаются.
В общем случае, где за ТКВК не стоит КВК, вам придется перебирать строки вашей таблицы, чтобы найти КВК.
Вы просто описали полный перебор для поиска КВК. Нет не полный, а до 1-го РИ
Вы утверждаете, что это быстрый перебор короче корня из N в общем случае? Я этого не вижу. Могли бы вы, пожалуйста, формализовать как именно вы перебираете строки таблицы в поисках КВК в общем случае, и как-то оценить, сколько строк он переберет? Может, вы вывели какое-то ограничение на то, как далеко от начала таблицы лежит первый РИ? Пока кажется, что они встречаются раз в min(p,q) строк, поэтому поиск РИ нисколько не быстрее тривиального перебора, потому что в худшем случае min(p,q) ~ sqrt(N).
VAE Автор
14.05.2025 13:24Любая атака начинается с проверки N на признаки делимости и деления на известные простые, когда они заканчиваются можно переходить на псевдопростые, но на практике это не делают. Ищут более короткие пути. Отсюда и множество разных подходов.
Я предложил очередной подход (модель), в котором имеется обоснование для успешной факторизации. Модель - фрагмент НРЧ, содержащий кратные делителей модуля кольца.
Задача как извлечь, "вытащить" хотя бы один делитель. Что удалось сделать - это найти как распределены кратные делителей по фрагменту. КВВ полные квадраты указывают на положение таких кратных, ЗРД. Вы утверждаете о его тривиальности, но пруфов этого я пока не вижу. Все законы, например, Ома для кого-то тривиальны, но не перестают быть законами.
> вы не указывали, что в общем случае у вас будет перебор для поиска КВК.
Это самое простое. Вы все время настаивали, что кроме перебора других возможностей я не демонстрирую. Мне пришлось найти "частные" случаи, когда факторизация возможна без тотального перебора.
>вычисления, которые проще, понятнее и логичнее заменить простой арифметикой выше
При N = 77, за 4 следует КВК 25 (в хо =16) и 77+25 =102 уже так не получится
> быстрый перебор короче корня из N в общем случае? Я этого не вижу.
Для N=629 в пределах ТКВК перебираем колонку tп, т.е. N:tп, на шаге 9, tп=17и 629:17=37
Другая возможность: в колонке rс генерируем (rс = rссс =182 = 13х14) и раскладываем в смежные сомножители. Находим хо =13+14 = 27.Получаем КВВ=КВК 27^2(mod 629) =100.
Доказательства у меня пока нет, но и примера, где это нарушено тоже нет (Быстро?).wataru
14.05.2025 13:24Вы утверждаете о его тривиальности, но пруфов этого я пока не вижу
Вы этот факт заметили в табличке, но даже не доказали. Вот вам все доказательство по шагам.
Пусть x - "КВК", т.е. x^2 = k^2 (mod N) для какого-то k^2 < N. По определению остатка от деления получаем x^2 = m*N + k^2. Перенесем известное k^2 и применим формулу разности квадратов: (x-k)(x+k) = m*N. Каждый простой делитель N должен встретиться или в x-k или в x+k. Если x-k > 0 и x+k < N (x не из тривиальной что-там у вас было), то делители N попадают в разные множетиели, а значит x-k и x+k делятся на делители N. Вот x - КВК - по середине между двумя делящимеся x-k и x+k. Вот ваш решающий интервал и его середина.Вся суть и основная идея в школьной формуле a^2-b^2 = (a-b)(a+b). Это тривиальная идея. Все ее доказательство - одна-две строчки школькой математики. Это не может быть сложным не очевидным профессианальному математику факт.
Я предложил очередной подход (модель), в котором имеется обоснование для успешной факторизации
Вы его даже не формализовали, чтобы говорить о том, что вы что-то предложили. Вы научились раскрашивать таблицу, нашли какие-то закономерности, которые на самом деле описываются тривиальными школьными формулами и все.
Ваша работа имела бы ценность, если бы вы все ваши закономерности, вроде ЗРД (он же формула разности квадратов), или случая, когда rccc+1 раскладывается на смежные сомножители, или чисел близнецов, формализовали и доказали, записали в виде четкого и понятного метода (вроде - если А, то применяем формулу B, если C, то формулу D, и т.д.) После чего доказали какие-то факты о применимости вашего метода. Скажем, rccc+1 применим ко всем числам вида (k^2-4)/3 (Это ваши излюбленные примеры N=407 и N=55).Потом уже вашу охапку критериев надо будет систематизировать и обобщить. Например все ваши частные случаи фактически применимы к числам, у которых фиксированна разность делителей. Вот уже вы решили задачу, когда разность делителей относительно небольшая, что хорошо дополняет тривиальный метод, при котором маленькие делители быстро находятся (ведь, если они большие, то их разность мала). Как-то их оба скрестив вы, может быть, могли бы вывести переборный метод с N^0.(3) в худшем случае. Пришлось бы какие-нибудь суммы рядов или интегралы и теорию чисел с теорией вероятности применить наверняка. Хотя это вряд ли. Но вот это был бы результат и сложный материал, а не вот эти ваши таблицы без единой формулы и доказательства. И фактически без математики.
Для N=629 в пределах ТКВК перебираем колонку tп, т.е. N:tп, на шаге 9, tп=17и
Это не доказательство общего случая. Так-то для 33 тупой перебор найдет делитель 3 уже на третьем шаге. Это значит, что этот наивный, известный сотни лет алгоритм - работает быстро? Все, ваш метод не нужен, ибо вот уже метод, который аж за 3 шага находит делители?
Для какого-нибудь числа из 20 знаков вашему методу понадобится условных 5 миллиардов строк перебрать, что фактически и есть sqrt(N). Если вы опишите мне ваш метод перебора (хоть раз его опишите уже, наконец-то! Часть про КВК мне очевидна, вопрос, как этот КВК найти), я вам смогу нагенерировать на компьютере сколько угодно чисел, где ваш перебор почти корень из N строк посмотрит.
Cairn
Статья непонятна даже для продвинутого читателя без подготовки в авторской нотации, перегруженность аббривеатурами — даже при наличии их списка. Много интуитивных, но недоказанных утверждений, похоже на попытку на частных примерах построить алгоритм факторизации "любого" числа. Скриншоты низкого качества в середине статьи не помогают, содержат неясные цветовые пометки без легенды. Очень похоже на работу энтузиаста, который не слышит окружающих и поэтому не может донести свою идею (очень редко на хабре вижу статьи с негативным рейтингом). Видно что проблема автором разрабатывается по меньшей мере с 2015 года. Есть ли псевдокод? Есть ли демонстрация выигрыша по сложности предлагаемого метода по сравнению, например, с методом квадратичного решета?
VAE Автор
Спасибо. Вы не первый, кто об этом пишет, но обо всех претензиях мною уже написано ранее и о раскрасках и о сокращениях. Если вам интересно откройте предыдущую статью. Там комментаторы друг другу помогают из того кто чего уже разобрал. Если есть желание и время ...