Содержание текста статьи у некоторых читателей Хабра вызвало определенный интерес (судя по комментариям). Что в общем-то не удивительно, так как тема статьи весьма актуальная для современного общества – информационная безопасность. Специалисты проявляют интерес и активно разрабатывают тему с момента открытия двухключевой криптографии и односторонних функций (около 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 .
Заключение
В работе показано направление моделирования числа, отличное от известных, и его возможности решать задачу факторизации составного числа, рассматриваемого как модуль приведения кольца.
Основу модели образуют алгебраическая структура - конечное числовое кольцо вычетов по составному модулю, представляемое фрагментом натурального ряда чисел, дополненного квадратичными вычетами элементов кольца. в котором существенными являются полные квадраты.
Такие квадраты становятся центрами решающих интервалов, с границами кратными делителям модуля приведения кольца.
