Модель составного полупростого числа

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

В предлагаемой вниманию читателей модели роль исследуемого числа отводится модулю N КЧКВ, т.е. N задан (может быть большим) и требуется в одной из задач отыскивать делители N. Для моделирования выбрана простая зависимость (линейная) N = х₁ + х_о. Очевидно, что список представлений такой модели конечен, и для чисел ограниченного размера может быть легко построен в форме таблицы, содержащей S =½ (N –1) строк. Модель названа списочной многострочной моделью и кратко обозначается (СММ, СМ-модель).

Введение

Те модели, которые рассматриваются в публикациях специалистов с мировой известностью имеют ограниченное использование и мной частично рассматривались с изложением критических замечаний в моих предшествующих работах. Взявшись за разработку и создание оригинальной модели мне пришлось руководствоваться ограничениями и требованиями, предъявляемыми к подобным числам в существующих системах двухключевого шифрования. Так, например, шифр RSA задается и функционирует над конечным числовым кольцом вычетов (КЧКВ) по составному модулю N=рq, к которому также предъявлены требования.

Списки строк легко получаются из фрагмента натурального ряда чисел (НРЧ) от 1 до N при складывании такого фрагмента пополам по принципу портновского метра с выравниванием делений в строках. Здесь следует отметить, что фрагмент НРЧ длиной N будет явно содержать делители р и q и их кратные значения. Задача моделирования числа и решения сводится, таким образом, к извлечению из списка модели хотя бы одного из делителей, а лучше обоих р и q. Как такое извлечение выполнить – главный вопрос?

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

Описание СМ-модели

Многострочная таблица из двух столбцов х₁ и х_о может и будет дополняться другими столбцами. Первым (левым) столбцом таблицы сделаем квадратичные вычеты (КВВ) х₁ и х_о. Они займут один столбец, так как r_л = х₁² (mod N) = х_о² (mod N) их квадраты по модулю N совпадают в каждой строке. Все КВВ равные полным квадратам (КВК) в этой колонке выделяем (желтым цветом).

Второй столбец отводим переменной х₁, а третий – х_о. Сумма элементов второго и третьего столбцов постоянна и равна х₁ + х_о = N. В четвертый столбец таблицы будем вписывать разности t = х₁ – х_о. Уже эта упрощенная модель числа N богата свойствами. Удобно сделать разметку ее элементов (заливкой). Для экспериментов зададим значение модуля равным произведению двух простых чисел N = рq = 407. Кроме этого значения нам в общем случае больше ничего неизвестно.

С другой стороны, для построения модели делаем допущение, что делители р и q известны. После этого отмечаем заливкой (синий цвет) все элементы модели кратные делителям. Такие строки будем называть кратными. Возникают вопросы.
Почему элементы 4-х столбцов в строке кратны одному делителю?
Как изменяются интервалы между строками кратными разным делителям?

Сколько таких разных интервалов наблюдается?
Чем обусловлено такое распределение интервалов?
Почему первые 20 строк содержат только монотонно возрастающие вычеты – квадраты?
Почему ниже 20 строк КВК перемешиваются по значениям (монотонность нарушается)? Почему не все КВК из верхнего списка повторяются?
Сколько и какие КВК не повторяются и почему?

Ответы на заданные вопросы и уточненные объяснения помогут понять и уяснить не только структуру модели, но и задачу о делителях числа. В частности, о том, что в НРЧ все связи между элементами (числами) детерминированы, но не менее сложные чем стохастические. Модель из 4-х колонок позволила автору продвинуться вперед в своих исследованиях, но не все трудности удалось преодолеть. Позднее модель подверглась усовершенствованию, число столбцов в таблице модели дополнилось.

Идея совершенствования модели как бы повторяла предыдущую: разложение числа на две части. Столбец разностей t = х₁ – х_о представляет собой фрагмент другой числовой последовательности – последовательности нечетных чисел (ПНЧ). В модели СММ элементы этого фрагмента монотонно возрастают от 1 до N – 2 при движении снизу в верх по строкам.

В каждой строке таблицы значения числа t представляется суммой 2-х смежных слагаемых
t = t₁ + t_о, t₁ = t_о +1. Слагаемые этой суммы перемножаются р(t) = t₁ × t_о и произведения р(t) помещаются в 5-ю колонку. При превышении произведением р(t) модуля N выполняется приведение по модулю, а результат помещается в 6-ю колонку таблицы, за которой следует 7-я, содержащая фрагмент ПНЧ, но направленный сверху вниз. Отметим, что фрагменты ПНЧ также включают кратные делителей N, но только с нечетными коэффициентами. Для колонок 5, 6 и 7 выполняем разметку элементов кратных делителям.

Опять возникают вопросы.
Почему в 5-й и 6-й колонке кратные делителям элементы следуют смежными парами?
Почему в 7-й колонке  паре кратных чисел из 6-колонки соответствует только одно (нижнее)?
Что определяет значения этих пар элементов?
Как меняются между парами кратных строк интервалы и что вызывает такие изменения?

Почему рассыпанные по всему списку средние вычеты вида r_ccc в конце 6-й колонки собираются вместе и дополняются некоторыми новыми?
Что определяет распределение средних вычетов вида r_ccc?
Последние две колонки 8-я и 9-я связаны с произведениями элементов КЧКВ р(х) = х₁ × х_о,
8-я колонка и приведением этого произведения по модулю N – 9-я колонка r_п=х₁×х_о(modN). 

Табличное представление модели составного числа

Особенности моделей некоторых полупростых чисел. Тривиальные области строк

Для удобства представления полной СМ-модели, в ней выделяются крупные части (области строк), которые описываются на достаточно подробном уровне. К таким частям относятся в начале списка от 1 до 20 строк (r_л) тривиальная область квадратичных вычетов - квадратов (ТКВК). В конце списка СММ строки от 184-й до 203-й строки – тривиальная (ТССС) область средних вычетов (r_ссс) в произведении сохраняющих смежность сомножителей; область строк от 21-й до 183 строки средняя между тривиальными, в которой каким-то образом распределены строки-дубли с маркерами (КВК, r_ссс) из тривиальных областей.

Ключевые строки с окаймлением строками 1-го и других слоев представляют интерес. Две крайние тривиальные области списка СММ для N = 407 представлены строками верхняя область с непрерывно следующими полными квадратами r_л = КВК (желтая заливка), нижняя – с непрерывно следующими средними вычетами вида r_ccc (зеленая заливка).

В этих тривиальных областях строки с названными элементами следуют непрерывно без пропуска номеров. В области ТКВК наблюдается пара строк, содержащих элементы из другой области (r_ссс = 306, r_ссс = 42). И наоборот, в области ТССС две строки содержат полные квадраты (r_л = 1, r_л =144), что характерно для ТКВК.

Этот факт свидетельствует о пересечении тривиальных областей по двум строкам. Значение
r_л = 169 лежит за пределами ТКВК и принадлежит строке-дублю с номером х_о= 24. Это ближайший к началу списка полный квадрат, соответствующий центру решающего интервала (РИ).
В таблице А колонка средних вычетов предшествует колонке t_п. Исторически модель создавалась поэтапно. Вначале были лишь три колонки R_л, Х₁ и Х_о. Результаты анализа такой упрощенной модели были довольно скромными. Информации для вывода формул получения делителей числа N явно не хватало.

Описание тривиальной области ТКВК

Эта тривиальная область начальных строк СММ, содержащая левые вычеты, включенные в колонку (Rл), которая возникает при возведении в квадрат элементов колонок (Х₁, Х_о). Колонка (Rл) левых вычетов СММ в верхней части содержит ТКВК– область строк с r_л, меньшими модуля N, следующими подряд и которые повторяются в строках-дублях, как-то распределенных по всему списку модели. Область ТКВК для N = 407 содержит возрастающие сверху вниз значения произведений чисел на себя (квадраты) от 1 до 407^½ (граница ТКВК). Объяснению такого распределения, начиная с верхних значений r_с = r_ссс в списке, посвящается этот пункт. 

Эта область строк  СМ-модели, содержащих непрерывно возрастающие КВВ = КВК от единицы до N^½ , размещается в начале списка СМ-модели. Для конкретного значения
N = 407 = 11∙37 = 203 +204 вычисляются значения (r_по) правого и (r_ло) левого вычетов последней (нулевой) строки списка r_по = 305, r_ло = 102. Все строки ТКВК содержат в позиции левого вычета непрерывно возрастающие значения КВВ = КВК – полные квадраты номеров строк.

Среди этих строк в области ТКВК встречаются строки с особыми свойствами:
Во-первых, это строка с номером равным х_о(d_m) = d_m меньшему делителю N (и строки с кратными d_m номерами, если они есть. Например, для N=1963 таких 3 строки х_о= 13, 26, 39).
Мы об этом можем не знать, но такие строки имеются всегда. Их распознавание - задача.

Во-вторых, в колонке Т_п найдутся строки со значениями номеров (х_о = 6) для меньшего
(d_m = х_о+ х_о – 1) и (х_о = 19) для большего делителей (d_б = х_о + х_о – 1), где х_о = ½ (d_i +1),
i = m, б.
К строкам с этими номерами примыкают (смежные) сверху строки со значениями r_с кратными тем же делителям, т.е. возникают пары смежных кратных строк (отмечены заливкой).

В-третьих, имеется пара строк, содержащая верхний и нижний средние вычеты со свойством сохранения смежности сомножителей (ССС) (r_сссв= 306, r_сссн = 42). Значения и положение (номера строк) этих средних вычетов представляют особый интерес в задачах факторизации числа N.

И наконец, в-четвертых, в колонке Т_п выделен заливкой большой фрагмент (замкнутый интервал [27, 47]) элементов – нечетное количество строк (выходит за пределы ТКВК), значения которых представляют непрерывный фрагмент последовательности нечетных чисел (ПНЧ) и являются слагаемыми в сумме, формирующей значение N. Количество таких строк равно d_m меньшему делителю, а среднее слагаемое равно d_б большему делителю.

Списки квадратов в СММ. Квадраты колонки Rл вне пределов ТКВК повторяются, но в другом порядке. В канонической СМ-модели такие строки с парами квадратов смежные. Суммы первых степеней таких пар квадратов образуют полусумму (иногда N = 1963 требуется полуразность) делителей N.

Для N = 407 = 11•37, такая полусумма равна 24, а полуразность 13. Точка х_о = 24 - центр РИ, так как в строке с этим номером возникает КВВ = КВК равный 24² (mod N) = 169 квадрату полуразности делителей (13²=169). В точке суммы делителей х_о = 11+37 = 48 возникает
также полный квадрат 48² – 407∙4 = 676 = (37– 11)², равный квадрату разности делителей.

Начнем выписывать первые степени КВК квадратов за пределами ТКВК, указывая также положение 0 – строки и строк идемпотентов (Id):13 - 2 - 9 - 20 -15- 4 -7- 18 - 0 -17 - 6 - Id -5 -16 - 19 - 8 - 3- 14 -10 -1-12. В этом списке 2 пары значений следуют без нарушения смежного порядка – это (18, 17) и (6, 5) и одна пара с заменой на 1 пропущенного элемента (10,11,12).
В таблице ниже выписаны полные квадраты номеров строк, парами окаймляющие 0-ю строку, строки идемпотентов (110, 111) и строку (221, 186) нетривиальных инволюций, для которых указаны номера строк-дублей (х_од).

При окаймлении парами строк, содержащих квадраты в левой позиции, для строки с инволюцией, половина суммы номеров этих строк равна значению
х_одс (r_ccc) = ½ (x_одв + х_одн) = ½ (175 +197) = ½ (162 +210) = ½ (151+ 221) =½ (140 + 232)=186 меньшей инволюции, а для  «нулевой» строки – это просто сумма номеров строк окаймления также равная такой инволюции
х_одс (r_ccc) = (х_одв + х_одн) = (92 + 94) = (81 + 105) = (70 +116) = (59 +127) = (57 + 129) = (46 +140) =  (35 + 151) = (24 + 162) =186.
Для номеров строк, окаймляющих идемпотенты сумма х_одс (r_ccc) = (х_одв + х_одн) = (105 +116)= = (94 +127) = (92 + 129) = (81 +140) = (70 + 151) =(59 + 162) = 221 равна большей инволюции.

Но для инволюции это позиции вытесненных центральных строк троек (средние строки троек) из ТССС, а для строки с r_ccc = 0 – это просто средняя строка между парой окаймляющих «0» строку пары строк.

Описание тривиальной области ТССС

Эта тривиальная область строк СММ, элементы r_ccc которой включается в колонку (Rс), и колонка возникает при разложении разности (х₁ – х_о = t = t₁ + t_о) в сумму смежных слагаемых (t₁ = 1+ t_о) и последующего перемножения слагаемых r_c = t₁ ˖ t_о. Эти же значения можно получить другими путями. Рекуррентно суммируя r_ci = r_ci -1 + t_пi предшествующий вычет, с i-м элементом колонки Т_п. Например, (для N = 407) при t_пi = 23, х_оi = (23 + 1):2 = 12,
t = N – 24 = 383 = 191 + 192 предшествующий вычет (при х_о = 11 равен r_ci -1 = 19, тогда
r_ci = r_ci -1 + t_пi = 19 + 23(modN) = 42. или 191˖192(modN) = 42

Колонка (R_с) средних вычетов в нижней части СММ содержит ТССС– область строк с r_с, меньшими модуля N, следующие подряд и которые имеют строки-дубли, как-то распределенные по всему списку модели. Область ТССС для N = 407 содержит возрастающие снизу в верх значения произведений смежных чисел от 0 до 380 (0•1 = 0, 1•2 = 2, 2•3 = 6, …, 19•20 = 380 <  N, (но для 20˖21 = 420 >N порог превышен). Объяснению такого распределения, начиная с верхних значений r_с = r_ссс в списке, посвящается этот пункт. 

Послойное окаймление строки инволюций (In), идемпотентов (Id) и 0-й строки строками с r_ссс.

Рассмотрение и анализ списков (колонок) СММ дает нам сведения о месте (номер строки) и причинах возникновения конкретных значений r_c и r_ccc среди них. Числовые значения r_c вдоль колонки R_c растут с ростом номеров строк до значений, превышающих N на некотором шаге r_c = r_{c -1} + t_п (r_{c -1} до превышения порога N) и на этом шаге «обрезаются» порогом N до остатка r_c = r_{c -1} + t_п – N, т.е. уменьшаются.

Малые значения r_ccc представляют больший интерес. Из этого следует, что малые значения r_ccc могут появляться только в области строк близких к порогам. Основное соотношение для значения r_c в строке r_c ≡ р (mod N), где р = t₁ ˖ t_о. Другое соотношение r_c = r_{c -1} + t_п, и еще одно r_c= r_л – r_ло .

Рост значений r_c определяется так. В соседней колонке Т_п справа помещен начальный фрагмент ПНЧ, т.е. нечетные числа t_п = (1, 3, 5, …) или t_п = 1(2) N–2. Текущему значению t_п соответствует строка с номером х_о (t_п) = ½ (t_п +1). Значение в этой строке r_c= х_о²(t_п) + r_по и при сложении его с r_ло получаем r_c + r_ло = х_о²(t_п) + r_по + r_ло = х_о²(t_п) + N = х_о²(t_п) квадрат номера строки r_с. 

Пример. Пусть ткущему значению t_п = 23 соответствует строка с номером
х_о (t_п) = ½ (t_п +1) =12. Предшествующее значение t_п = 21 и номер строки с этим значением
х_о (t_п = 21) = 11, а r_c = 19.
Значение r_c находим по соотношению  r_c  = r_c -1 + t_п= 19 +23 = 42 и  еще одно соотношение для r_c  = r_л – r_ло = 144 – 102 = 42.

Окаймление строки нетривиальных инволюций парами строк с r_cсс

Интерпретация процесса моделирования (действий СМ-модели). Весь список ТССС расчленяется на тройки строк. Первая тройка в средней строке имеет r_cсс = 306. Сумма номеров строк-дублей, окаймляющих строку с r_cсс = 306, дает в первом слое окаймления строками с r_cсс сумму х_о (r_cсс = 342) + х_о (r_cсс = 272) = 185 + 187 = 372 удвоенную меньшую инволюцию 372:2 = 186 = In.
Окаймление In второго слоя х_о (r_cсс = 56) + х_о (r_cсс = 30) = 174 + 198 = 372 дает такой же результат.

Именно это значение (306) появляется первым в строке-дубле с номером х_од = 186 в колонке СММ Rc при моделировании.  Крайние строки-дубли тройки получают номера х_о = 186 ± 1, которые содержат r_ccc= 342 и r_ccc = 272 и образуют первый слой окаймления строки нетривиальных (In, I_N) инволюций такими строками.
Строки х_о = 186 – 1 = 185 и х_о = 186 + 1 = 187 кратные и не дублируются (совпадают с дублями).  
Второй слой окаймления (In, I_N) из тройки с центром r_ccc= 42, лежащим в строке х_од = 12, а крайние строки-дубли с номерами х_од = 186 ± 12, и содержат сверху
х_од (r_ccc= 56) = 186 –12 = 174 и снизу х_од (r_ccc= 30) = 186 + 12 = 198.  
Строка хо (r_ccc= 30) =198 кратная, т.е. не дублируется.

Окаймление идемпотентов парами строк дает суммы 221
х_од (r_ccc= 132) + х_од (r_ccc= 156) = 104 + 117 = 221 в 1-м слое и
х_од (r_ccc = 0) + х_од (r_ccc= 2) = 93 + 128 = 221 во 2-м слое, в 3-м и последующих слоях
х_од (r_ccc= 110) + х_од (r_ccc= 90) = 82 + 139 = 221; х_од (r_ccc=182) + х_од (r_ccc=210) = 69 +152=221; х_од (r_ccc = 6) + х_од (r_ccc= 12) = 58 +163 = 221; х_од (r_ccc= 72) + х_од (r_ccc= 56) = 47 + 174 = 221;
х_од (r_ccc=380) + х_од (r_ccc= 342) = 36 +185= 221; х_од (r_ccc=240) + х_од (r_ccc=272) = 34 +187= 221;
х_од (r_ccc = 20) + х_од (r_ccc= 30) = 23 + 198 = 221 суммы сохраняют значение большей инволюции.

Окаймление 0-й строки парами строк дает суммы 186
х_од (r_ccc= 110) + х_од (r_ccc= 132) = 82 + 104 = 186;
х_од (r_ccc= 182) + х_од (r_ccc= 156) = 69 + 117 = 186; х_од (r_ccc= 6) + х_од (r_ccc= 2) = 58 + 128 = 186;
х_од (r_ccc = 72) + х_од (r_ccc= 90) = 47 + 139 =186; здесь мы пропускаем одно значение
х_од (r_ccc= 380) = 36
х_од (r_ccc=240) + х_од (r_ccc= 272) = 34 + 152 = 186; х_од (r_ccc= 20) + х_од (r_ccc= 12) = 23+163 =186;
х_од (r_ccc = 42) + х_од (r_ccc= 56) = 12 + 174 = 186; х_од (r_ccc= 306) + х_од (r_ccc= 342) = 1 +185 = 186;

Все суммы постоянны (186) и равны меньшей инволюции.
Мы рассмотрели, как окаймляются парами строк, содержащих средние вычеты (ССС), инволюции, идемпотенты и «нулевая» строка. Оказалось, что все окаймления связаны с нетривиальными инволюциями (большая \ меньшая). Это указывает на существенную роль этих элементов кольца вычетов.

Строка In (N = 407) имеет КВК = 1 в точке центра решающего интервала х_о= In =186 и в соответствии с ЗРД обеспечивает вычисление делителей N по формуле
d_1,2 = НОД (N, In ±1) = НОД (407, 186 ± 1) = 11, 37. Здесь использованы строки окаймления In первого слоя, а они всегда кратны разным делителям.   

Заключение

Строки модели выстраиваются весьма любопытным образом. Приведенный текст статьи иллюстрирует необычность, которая состоит в том, что суммы пар номеров строк, содержащие КВК (квадраты левых вычетов и средние вычеты вида (r_ccc)), окаймляющие ключевые строки в средней части модели равны постоянным значениям меньшей (186) или большей (221) нетривиальной инволюциям.

Строки тривиальных областей упорядочены по номерам, а вычеты в них упорядочены по значениям (в ТКВК квадраты в, ТССС средние вычеты). В строки средней части модели эти квадраты и средние вычеты перемещаются, перемешиваясь "загадочным" образом, относительно исходного порядка. Не по воле разработчика модели, а по каким-то своим законам.

Интерпретировать удалось не только поведение r_ccc, но и квадратов. Квадраты всегда принадлежат строкам-центрам решающих интервалов и реализуют закон распределения делителей, а средние вычеты как бы "выталкиваются" вверх списка модели из центров троек, на которые разбивается ТССС.

Если бы мы пожелали самостоятельно выстроить такую последовательность номеров строк (на самом деле они следуют подряд как в НРЧ), то вряд ли нам это бы удалось. С другой стороны, в список непрерывно следующих строк как бы вставлены ключевые строки: нулевая, нетривиальные инволюции, идемпотенты, центральная и др. Эти вставки сделаны так, что поведение сумм номеров пар окаймляющих строк становится закономерным.