Ранее в статьях. о симметриях списочной многострочной модели (СММ) рассматривались окаймления строки нетривиальных инволюций (НIn) парами строк, содержащих квадратичные вычеты – полные квадраты (КВК). В таблице А0 (N = 989) показаны названные зависимости.
При изложении текста статьи решается задача определения нетривиальных инволюций (НIn) в конечном числовом кольце вычетов (КЧКВ) по составному (полупростому) модулю и построение (формирование) полного списка модели. Для получения решения используется модель составного числа и Закон распределения делителей (ЗРД здесь). Любая пара строк СММ, окаймляющая строку нетривиальных инволюций, имеет номера, полусумма которых равна номеру строки НIn, совпадающему с меньшим значением инволюции.
Доказательство этого факта в следующем. На числовой оси (хо) отметим номера окаймляющих строк в слое k. Эти строки симметрично расположены по отношению к строке НIn, т.е. они одинаково удалены от НIn. Оба номера окаймляющих строк либо четны, либо нечетны, так как их полусумма – целое число (номер строки). Средняя точка замкнутого интервала между номерами пары окаймляющих строк определяется по формуле хоц = ½ (хон + хов). Найденное значение – номер строки нетривиальных инволюций.
Индексы у номеров строк СМ-модели обозначают: ц – центральный, н – нижний, в – верхний. Невыясненным остается вопрос, где и как получить нужные строки и их номера? Оказывается, что среди пар строк окаймления некоторого k-го слоя встречаются такие, обе из которых содержат средние вычеты вида rccс. Именно такие пары строк обеспечивают успех поиска решения.
Первая сверху списка СММ строка с rccс, с номером хо (rccс) = k указывает на пару окаймляющих строк смежных с ней в тройке строк области ТССС. Эта строка является центральной строкой тройки, а крайние строки этой тройки окаймляют строку НIn в k-ом слое. Таким образом, состав тройки строк определен (rccсв, rccсц, rccсн) – это средние вычеты верхний, центральный и нижний. Номер центральной строки (хоц) тройки строк уже получен. Заметим, что в теории чисел задача определения ключевых элементов КЧКВ решается только тотальным перебором элементов.
Отсюда следует новизна подхода к решению задачи в рамках оригинальной (авторской) модели составного числа. Я оцениваю уровень трудности публикации высоким, но только в силу тех оценок, которые выставляются моим статьям. Эти статьи не о разных вопросах теории чисел, а объединены общим замыслом и как бы дополняют материал предшествующих статей. Замысел я уже объявлял, но готов повторить. Решается задача факторизации числа — поиск обратной операции для умножения. Мои ученики (конечно не все) видят результаты моих исследований на Хабре и понимают, что к чему излагается в статьях. Их вопросы свидетельствуют об этом.
Для читателей Хабра кто стремится вникнуть в проблему, следует быть в теме и разбираться в изложенном ранее материале. Он совершенно новый, требует введения новых понятий, обозначений, формулировок. Я не утверждаю, что все там О’key, допускаю промахи и ошибки. Рассчитываю на Ваши замечания и подсказки для исправления. Ожидаю вопросы по существу статей. Это совершенно новый подход, новая модель, новые конструкции, новые результаты, которые другими не получены, и ни в каких учебниках о них не прочитать.
Часть решенных мной задач аналитически, в учебниках высшей алгебры до сих пор предлагается решать перебором. Новые результаты открываются и появляются со временем. Когда я создавал модель, не мог даже предположить, например, что она разложима на подмодели. Но после получения разложения удалось продвинуться в разных направлениях исследования составных чисел.
Введение
При разных составных числах N и формировании полного списка СММ строки ключевых элементов модели могут следовать в разном порядке, т.е. на разном удалении от начала списка и одна от другой. Так, для N = 2501 ближайшей к строке нетривиальных инволюций (НIn) хо = 245 оказываются строки идемпотентов (Id = хо = 123, хо (ID) = 122 ) c номерами хо = 122 и хо = 123, а для N =1961 ближайшей к строке нетривиальных инволюций (хо=741) оказывается строка-дубль с rccс= 0 («нулевая» строка с хо= 610).
Строка нетривиальных инволюций (хо = 741) послойно окаймляется парами строк, содержащих средние вычеты вида rccс на разном удалении слоев от нее. Так окаймление 1-го слоя образуют строки с хо (rccс = 462) = 737 и хо (rccс = 552) = 745 удаление одна от другой в паре 745 –737 = 8 строк и от строки инволюций между ними 4 строки, т.е. их номера хо = 741± 4. Это строки границ замкнутого интервала [737, 745], образованного девятью числами [737, 738, 739, 740, 741, 742, 743, 744, 745], где среднее число 741 – нетривиальная инволюция, 7412 (mod 1961) = 1.
О модели числа. Напомню основные положения СМ-модели составного нечетного натурального числа N = рq, образованного перемножением пары простых нечетных чисел p и q. Именно так построены в шифре RSA – числа-модули. Для построения модели числа N используются элементы фрагмента натурального ряда чисел (НРЧ) от 1 до N, размещенных каждое в отдельной ячейке регистра.
Регистр подобно ленточному портновскому метру складывается вдвое так, чтобы совмещаемые по горизонтали ячейки содержали числа, сумма которых постоянна и равна N. Эта конструкция – скелет СМ-модели, помещается в таблицу (столбцы: 2-й содержит переменную х1 и 3-й – хо), а число ее строк ½(N – 1). Первый столбец таблицы – квадратичные вычеты (КВВ) чисел х1 и хо строки. КВВ элементов строки х1 и хо совпадают. Так 9812 (mod 1961) = 9802(mod 1961) = 1471.
Четвертый столбец разности чисел t = х1 – хо. Эти разности (t) раскладываются в сумму смежных значений t = t1 + tо, t1 = tо + 1 и слагаемые перемножаются р = t1 × tо, (5-й столбец). Если р >N, то выполняется приведение р по модулю N (6-й столбец). Седьмой столбец СММ – начальный фрагмент последовательности нечетных чисел (ПНЧ) от 1 до N – 2. В СММ возникают две тривиальные области строк ТКВК (содержат КВК) и ТССС (содержат rссс). Для вычетов использованы обозначения rл – квадратичные вычеты (КВВ), rс – средний вычет и rп = N – rл правый вычет.
В списке строк (N = 1961, табл. А3) пара строк области ТССС, содержащая средние вычеты
rccсн = 462 = 21˖22 и rccсв = 552 = 23˖24 разделяется строкой со средним (центром) вычетом
rccсц = 506 = 22˖23. В полном списке СММ (строк-дублей) позиция центрального элемента в тройке (462, 506, 552) автоматически замещается строкой инволюций, а значение rccсц = 506 вытесняется и помещается в строку с номером хо = (dб – dm) : 4 = (53 – 37) : 4 = 4 в верху списка. Для 1-го и последующих слоев окаймления строки НIn строками со средними вычетами вида rccс ситуация повторяется – центральная строка очередной тройки вытесняется строкой инволюций. Вытесненные элементы уходят ниже вытесненного (506) первым, затем 210,930,42.
В каком-то окаймляющем слое строка окаймления инволюции (хо (rccс= 56) = 655) оказывается также строкой окаймления 655 – 610 = 45-го слоя строки с дублем «нулевой» строки (Iо), или с другим ключевым элементом идемпотентом (Id, ID), и др.
Замысел и свойства модели. В статье о симметриях, относящихся к нетривиальным инволюциям, мной были рассмотрены послойные окаймления строки НIn строками, содержащими квадратичные вычеты (КВВ). Модель числа N базируется на свойствах и зависимостях НРЧ.
В таблице А0 показано как квадратичные вычеты-квадраты (КВК) взаимодействуют с переменными х1 и хо и друг с другом в пределах НРЧ. Замысел и идея СМ-модели для исследования числа N, его свойств и структуры формулируется достаточно доступно и просто для понимания.
Среди чисел НРЧ от 1 до некоторого составного натурального N непременно будут встречаться его делители dm (меньший) и dб (больший) и их кратные. Если согласиться, что это так, то нельзя ли в рамках некоторой модели N попытаться извлечь из фрагмента НРЧ делители, обитающие там? Теоретически такое извлечение оказалось достаточно просто показать и практически выполнить, используя закон распределения делителей dm и dб составного натурального числа N. Для значений N не очень больших закон прекрасно работает.
Но на Хабре ЗРД минусуют сегодня без объяснений, как и 10 лет назад. Может быть это минусы читатель ставит себе самому. Впервые за несколько тысяч лет получен простой закон определения делителей составного числа. Никто из минусующих не сказал, что это ошибочно, неправильно, или кем-то было сказано раньше. За 10 лет ситуация не поменялась, очень высокая устойчивость у минусаторов.
Доказательство многих теорем в Теории чисел выполнено при допущении, что делители числа N известны. Это и основная теорема арифметики, теоремы о количестве делителей числа N, о сумме этих делителей и другие. При работе с числом N, как правило, делителей его мы не знаем и тогда использование таких теорем и их результатов невозможно.
Удивительно, но при огромном количестве математиков в мире не нашлось того, кто взялся бы решить эту задачу и объявил о решении. Всех устраивала ситуация переборного подхода поиска делителей или каких-то других методов, имеющих ограниченное применение. В 2010 году была опубликована академиком РАН работа: В. И. Арнольд, “Случайны ли квадратичные вычеты?”, Нелинейная динам., 6:3 (2010), 513–520. Само название статьи вызывало некоторое недоумение.
Получается, что уважаемый академик Арнольд знает, что не существует универсального метода определения делителей составных чисел, не известен закон распределения в кольце вычетов делителей его модуля (составного числа N). Он предлагает выполнить проверку гипотезы о случайности квадратичных вычетов в кольце вычетов по составному модулю.
Гипотеза не подтвердилась и на этом академик остановился. Мне пришлось заниматься этой предметной областью и этой задаче я уделил время. Статья Арнольда подтолкнула разобраться в этом вопросе поглубже. Завершилось все в 2014 году (статья мне попалась в этом 2014 году) формулированием нового закона о распределении делителей натурального числа.
Позднее удалось распространить закон на множество целых чисел. Для огромных N ЗРД долго, но тоже работает. Необходима доработка алгоритма поиска КВВ, ускоряющая поиск КВК. Над этим сейчас и идет интенсивная работа, часть такой работы и результатов эта статья.
Область тривиальных средних вычетов ТССС. Строка НIn (N = 989) имеет КВК = 1 в точке решающего интервала хо= In =300 и в соответствии с ЗРД обеспечивает вычисление делителей N по формуле d1,2 = НОД (N, In ±1 ) = НОД (989, 300 ± 1) = 23, 43. Здесь использованы строки окаймления НIn первого слоя, а они всегда кратны разным делителям.
В колонках rссс таблицы А1 заливкой выделены строки, образующие тройки смежных средних вычетов и в колонке хо справа номера этих строк-дублей. Таких троек может быть несколько. Следующая колонка хисх исходных положений содержит номера строк области ТССС для всех упорядоченных средних вычетов.
Колонка квкд – порядок следования КВК вне области ТКВК; ход – номера строк-дублей с КВК.
Символом ∆ обозначено количество строк, разделяющих последовательные КВК в списке.
При неизвестном значении нетривиальных инволюций их значение может быть определено с использованием другой пары строк окаймления, ближайшего к строке инволюций слоя, в котором лежат средние вычеты вида rссс. Как определить такую ближайшую пару? На нее указывает строка полного списка строк СММ, впервые содержащая средний вычет rссс.В нашем случае это строка с номером хо (272) = 5, где средний вычет 272 = 16×17 = rссс первый в полном списке СММ.
В таблице А1 показано как средние вычеты взаимодействуют с переменными х1 и хо и друг с другом в пределах ТССС фрагмента НРЧ. Анализ таблицы А1 позволил вскрыть свойства СМ-модели или фрагмента НРЧ, о существовании которых ранее нигде не говорилось и даже не предполагалось.
Это свойство СММ состоит в формировании в области ТССС троек смежных строк, содержащих средние вычеты вида rссс, такие, что, если крайние элементы (2 строки) из тройки в некотором слое окаймляют строку нетривиальных инволюций, то центральный элемент тройки как бы выталкивается инволюцией, «всплывает» вверх общего списка строк. Эти средние вычеты центральных строк троек ТССС вверху списка играют роль детекторов инволюции.
Они обнаруживаются первыми при анализе модели и указывают на пары строк, окаймляющих строку инволюций. Номера строк-дублей для крайних строк в каждой тройке при их суммировании получают удвоенное значение меньшей нетривиальной инволюции. Ниже на числовом примере показывается как это происходит.
Пример 1. Вытеснение строкой нетривиальных инволюций строки средних вычетов rссс из упорядоченного списка ТССС . Для N = 989 =23×43 (таблица А1). Речь идет о колонках: (rссс) средних вычетов (точнее об ее области ТССС) и номеров (хо) строк их размещения (исходных хисх) и (дублированных хо). В колонке ТССС все rссс упорядочены по возрастанию в списке снизу вверх. Практически все эти средние вычеты дублируются и в полном списке СММ встречаются еще раз, в другом порядке и в других строках с номерами, указанными в колонке хо (справа от rссс).
Первым в списке СММ встречается средний вычет rссс = 272 (таблица А1,строка с номером хо(272) = 5). Обратившись к ТССС, находим тройку (306, 272, 240), крайние значения rссс = 240 и rссс = 306 лежат в строках-дублях 1-го слоя окаймления НIn, имеющих номера хо(306) = 305 и хо(240) = 295, сумма номеров In = ½(305+295) = 300 равна удвоенному номеру меньшей нетривиальной инволюции.
Сделаем выборку возрастающих номеров строк-дублей этой колонки средних вычетов полного списка. Самый меньший номер хо = 5, затем следуют номера хо (42)= 5 + 23 = 28, хо (702) = 28 + 2˖5 = 38, хо (870)= 28+23 = 51, хо (12)= 51+2˖5 = 61,хо (380) = 61+ 23 = 84, хо (182)= 84+ 2˖5 = 94, хо (90) = 94+ 23 = 117, хо (552) = 117 + 2˖5 = 127. Элементы rссс в этих строках троек из ТССС окаймляются парами смежных с ними элементов (сверху\снизу).
Например, в 38 строке-дубле лежит центр тройки (650, 702, 756)), а крайние rссс лежат в строках 3-го слоя окаймления инволюции с номерами хо ( 650 ) = 262 и хо ( 756 ) = 338. Сумма номеров In = ½( 262 + 338 ) = 300 определяет инволюцию.
Этот удивительный факт открывает возможность определения инволюции в кольце вычетов. Впрочем, удивляться особенно нечему, так как окаймляющая строку инволюций пара строк с крайними средними вычетами в тройке rccc равноудалена от строки инволюций, которая лежит как раз в центре между ними.
In =½(305 +295) = ½(272+328) = ½(338 +262) =½(351 +240) =½(361 +239) =½(394 +206) = 300.
Приведем еще несколько примеров для других значений N = 1963 = 13×151, N = 2561 = 13×197
(таблица А2) и N = 1961 = 37×53, N = 2501 = 13×197, (таблица А3)
Пример 2. Поиск первой сверху списка СММ строки со средним вычетом вида rccc в списке.
Для N = 2561 =13×197 (таблица А2) можно указать (отыскать) в области ТССС такие тройки смежных строк, в которых сумма номеров крайних строк становится равной постоянному значению и это значение равно удвоенной меньшей инволюции. В таких тройках средние строки включают начиная с верха полного (развернутого) списка СММ строки-дубли с rccc. Ниже выписано множество равенств для сумм, где центральные строки смежных троек в ТССС содержат значения rccc = 1560, rccc = 1482, rccc = 702, rccc = 650, rccc = 182, rccc = 0, rccc = 156 и др. В приведенном множестве rccc значений центров троек пары троек перекрываются и центральная строка в верхней тройке становится крайней строкой в нижней тройке:
In = ½(255+137) = ½(59 + 333)= ½(268+124) = ½(72 + 320) = ½(281+ 111) = ½(85 + 307) = 196. Особенностью этой модели следует назвать отсутствие строк в области ТКВК со средними вычетами вида rccc, что объясняется пустым множеством пересечения областей ТКВК ∩ТССС = Ø.
Другая особенность состоит в том, что делители N = 2561 = 13×197 линейно зависимые числа, т.е. dб = а˖dm + b => 197 = 15×13 + 2. Для таких составных N инволюция определяется выражением In = N ± 1. Проверка свойства инволюции для вариантов выписанного соотношения обеспечивает ее нахождение.
In = N +1 = 197+1 =198, 1982(mod 2561)=789 ≠ 1; In =N –1=197–1 =196, 1962(mod 2561)=1.
Следовательно, инволюцией является значение In = 196. Это не общее правило для любых N, но при выполнении указанной зависимости делителей N выполняется всегда. Но сами делители еще надо уметь до проверки вариантов вычислить.
Фрагмент ТССС содержит также неперекрывающиеся 4 тройки с постоянной суммой 2169 номеров крайних строк троек, содержащих средние вычеты
Для rccc = 380, ∑= [хо(420)+ хо(342) =1104 +1065] = [хо(1122)+ хо(992) = 1052 + 1117] = [хо(2162)+ хо(1980) = 1039 +1130] = [хо(56)+ хо(30) = 1078+ 1091] = 2169 эта сумма равна не удвоенной инволюции, а разности t в строке инволюций.
Поэтому проверять необходимо все варианты троек с постоянными суммами номеров крайних строк, т.е. устанавливать являются ли они удвоенной инволюцией.
Когда СМ-модель числа N построена, то относительно нее могут возникать разные вопросы. Например, как и почему в области строк ТКВК появляются строки, содержащие средние вычеты вида rссс? Существует простой ответ на этот вопрос – эти строки, как и все другие, получаются по правилам модели простыми вычислениями по заданным формулам. Тогда вопрос уточняем. Как средние вычеты rссс зависят от ключевых элементов (например, от инволюций (In)) СММ?
В этом случае можно дать развернутый ответ, который в какой-то мере будет интерпретировать получаемый результат. Ниже такой ответ выстраивается на числовых примерах.
Пример 3 Вытеснение строкой нетривиальных инволюций строки средних вычетов rссс из упорядоченного списка ТССС . В списке СМ-модели (N = 1963, N = 2501) возникают фрагменты, содержащие ТКВК и ТССС. Во втором (ТССС) можно выделить тройки строк (выделены заливкой) rссс., в которых позицию центральной строки из трёх (в полном списке СММ) занимает строка нетривиальных инволюций. Центральная строка тройки как бы вытесняется вверх строкой нетривиальных инволюций в полном списке СММ. При этом крайние строки тройки становятся послойно окаймляющими для строки инволюций. Такая тройка в ТССС не единственная их множество распределено по списку равномерно (с шагом (dб – dm):2), начиная от строки с меньшим хо номером.
Тройки в ТССС (N =1963) упорядочиваются (1122, 1190, 1260), (420, 462, 506), (272, 306, 342), (56, 72, 90), (12, 20, 30). Этим тройкам соответствуют тройки номеров строк-дублей, содержащих rссс – элементы: (495, 41, 413), (400, 54, 508), (361, 93, 547), (387, 67, 521), (374, 20, 534).
Дубль-строка для rссс. = 1190 имеет меньший номер хо (1190) = 41 и далее хо (462) = 54 = 41+13, хо (306) = 93 = 54+39, хо (72) = 67 = 54 + 13, хо (20) = 80 = 67 +13. Замечательным свойством троек обладает сумма номеров строк-дублей крайних элементов троек. Эта сумма равна удвоенному значению нетривиальной инволюции.
Действительно: In = ½(413+195)=½(400+508)=½(361+547)=½(387+521) =½(374+534)= 454.
Тройки (N = 2501, табл. А3) упорядочиваются (702, 650, 600), (272, 240, 210), (1332, 1260, 1190), (42, 30, 20), (2162, 2070, 1980). Центральные элементы троек {650, 240, 1260, 30, 2070} последовательно появляются в строках списка ТКВК и вне его. Пара rссс={1Id 2070, 1Id 2162} последней тройки является окаймляющей 1-го слоя (1Id) для идемпотентов модели – особая.
Номера строк, в которые вытесняются средние вычеты: хо(rссс= 650) = 5 = (dб – dm):4 = 5; хо(rссс= 240) = 5 + dm = 5 + 41 = 46; хо(rссс =1260) = 46 +(dб – dm):2 = 46 +10 = 56;
хо (rссс=30) = 56 + dm = 56+41 = 97; хо(rссс =2070) = 97 + (dб – dm):2 = 97+10 =107.
Выпишем суммы номеров строк-дублей крайних элементов троек. Эти суммы равны удвоенному значению нетривиальной инволюции. Действительно,
In = ½(240+250) = ½(291+199) = ½(342+148) = ½(189+301) = ½(138+352) = 245.
В списке СМ-модели (N = 1961=37×53) возникают фрагменты, содержащие ТКВК и ТССС. Здесь в отличие от СМ-модели (N = 2501) ближней ключевой строкой к строке НIn нетривиальных инволюций оказывается не пара строк идемпотентов, а строка-дубль «нулевой» строки.
Эта строка имеет общую со строкой инволюций окаймляющую строку. В фрагменте (ТССС) можно выделить тройки строк (552, 506, 462), (240, 210, 182), (992, 930, 870),(56, 42, 30), (1560, 1482, 1406). Центральные элементы троек {506, 210, 930, 42, 1482} последовательно появляются в строках списка ТКВК и вне его. Номера строк, вытесненных rссс элементов:
хо (506) = (dб – dm):4 = 4; хо (210) =хо(506)+dm=4+37 = 41; хо(930)=хо(210)+(dб – dm):2=49, хо (42) =хо (930)+dm = 86; хо (1482)= хо (42)+(dб – dm):2 = 94.
Расположение квадратичных вычетов (КВК) и средних вычетов (rccc) по строкам СММ
Сумма номеров строк-дублей крайних элементов троек. Эта сумма равна удвоенному значению нетривиальной инволюции. Действительно,
In = ½(745+737) = ½(700+782) = ½(790+692) = ½(655+827) = ½(835+647) = 741.
Пример 4. (N = 119, rпо = 89 ). Поиск строк пересечения ТКВК ∩ТССС тривиальных областей и делителей N возможен непосредственными вычислениями всех строк с проверкой свойства ССС средних вычетов (путь перебора строк). Используя полученные при исследовании СМ-модели математические зависимости, такой поиск можно ускорить. Как это осуществить?
Допустим (см. пример 5), что средний вычет с нужными свойствами разместился теперь в верхней (первой) строке СМ-модели. В позиции среднего вычета располагается сумма
1+ rпо = 90. Для нее проверяем свойство среднего вычета (ССС) сохранять смежность сомножителей. Путем извлечения квадратного корня из суммы 90½ = 9, 48, отыскиваются сомножители, т.е. 9˖10 = 90, свойство ССС выполнено и далее находим разность t.
Если этот средний вычет (90) обладает свойством rссс, то он раскладывается 90 = 9˖10. в смежные сомножители, которые суммируем. t = 9 +10 =19, т.е. получаем разность х1 –хо= t, t = t1+tо, t1= tо+1 и для нахождения среднего вычета перемножаем слагаемые р = t1 × tо, проверяем правильность вычислений. Находим номер строки, где размещена эта разность хо (19) = ½ (N – t ) = ½ (119 – 19 ) = 50. Получили дубль (50) первой строки СММ, т.е. дубль инволюции. Для строки инволюции строки 1-го слоя (±1) окаймления всегда содержат кратные разных делителей. По правилу ЗРД находим делители (либо их кратные)
dm,б = НОД (N, хо ± 1 ) , dm = 50 – 1 = 49, 49½ =7, dб = (50 + 1):3 = 51:3 = 17.
Проверка N = dm dб = 7˖17 = 119. Решение верно.
Если средний вычет rс 1-й строки не обладает свойством ССС, то начинаем поиск rссс.
Для (N = 989) только в строке хо= 5, появляется rссс (5) = 272 = 16˖17, средний вычет, который раскладывается в смежные сомножители. Сомножители в сумме равны разности х1 – хо = t = 16 + 17 = 33, что позволяет найти номер строки-дубля для этого rссс, т.е. центр решающего интервала (РИ), хо (t = 33) =½ (N – t ) = ½ (989 – 33 ) = 478.
В точке центра РИ всегда КВВ = КВК, т.е. полный квадрат 4782(mod 989) = 25, 25½ = 5.
Далее по правилу ЗРД находим делители,
dm,б = НОД (N, хо ± 5), dб = 478 – 5 = 473= 11˖43, dм = (478+5):21 = 483:21 = 23.
Проверка N = dm dб = 23˖43 = 989. Решение верно.
Пример 5. Ускорение поиска строк пересечения тривиальных областей ТКВК ∩ТССС.
Пусть N=1963 (табл. А3), х1о= 982, хоо= 981, rло= 491, rпо= 1473, (1473) ½ =38,37 ≠ rссс. Пытаемся вычислить значение среднего вычета rссс сохраняющего смежность сомножителей (свойство ССС)
rссс = 38 × 39 = 1482 и проверяем полученный rс на свойство ССС 1482 + 491 = 1973 ≠ □;
далее уменьшаем\увеличиваем значения сомножителей и выполняем проверку свойства ССС
rссс = 38×37 =1406+491=1897 ≠ □; увеличиваем rссс = 39×40=1560+491=2051–1963 = 88 ≠□; уменьшаем значения сомножителей
rссс = 36×37 =1332+491=1823 ≠□; увеличиваем rссс = 40×41=1640+491=2131–1963=168 ≠ □; уменьшаем значения сомножителей
rссс = 36×35=1260+491=1751 ≠ □; увеличиваем rссс = 41×42=1722+491=2213–1963=250 ≠ □; уменьшаем значения сомножителей
rссс = 34×35 =1190+491 = 1681 = 412 = □; за 9 шагов (вместо 41) нашли истинное значение элемента (1190) строки пересечения. Более того параллельно нашли и номер (хо = 41) этой
строки (именно она формирует полный квадрат)
При построении СММ (N = 2501) в 5-ю строку попадает rccc = 25×26 = 650. Что привело этот средний вычет в эту позицию? Далее следуют значения rccc = 240, 1260, 30, 2070. Прямые вычисления строк СММ по формулам дают (rccc = хо2 + rпо, сумма квадрата номера строки и правого вычета нулевой строки: 650 = 52 + 625; 240 = 462 + 625; 1260 = 562 + 625; 30 = 972+ 625; 2070 = 1072 + 625) эти же значения, но без логической интерпретации и обоснованности. Использование формулы при известном значении rccc обеспечивает вычисление номера строки положения среднего вычета. хо = (rccc – rпо)½. Все значения rccc в таблице А3 (фрагмент ТССС) выписаны в лексикографическом порядке с указанием разности (t) и номеров строк-дублей.
Сумма номеров строк-дублей, содержащих rccc, и окаймляющих те строки в ТССС, которые вытесняются инволюцией, равна удвоенной нечетной нетривиальной инволюции. Средний вычет rccc = 650 окаймляется строками хо (600) = 250 и хо (702) = 240, тогда
In = ½(240 + 250) = ½(199 + 291) = ½(189 +301) = ½(148 +342) = ½(138 +352) = ½490 = 245.
Более глубокий анализ зависимостей приводит к разумному объяснению появления этих конкретных значений в позициях. Как и все другие эти средние вычеты следуют при размещении общему закону: чередуясь полусуммой делителей (51) модуля и с шагом меньшего делителя (41)
Покажем как послойно окаймляются нетривиальные инволюции строками со средними вычетами (rccc) с представлением их сомножителями и как «выталкиваются» строки с rccc из смежных троек в ТССС
1-й слой: 600 =24×25 — In -26×27=702 позицию In должно занять произведение пары 25×26 = 650,
2-й слой: 210 =14×15 — In -16×17=272 позицию In должно занять произведение пары 15×16 = 240,
3-й слой: 1190 =34×35 — In- 36×37= 1332 позицию In должно занять произв-е пары 35×36 = 1260,
4-й слой: 20 = 4×5 — In- 6×7 = 42 позицию In должно занять произведение пары 5×6 = 30,
5-й слой: 1980 = 44×45- In- 46×47 = 2162 позицию In должно занять произв-е пары 45×46 = 2070.
Анализ списка (в таблице А3) показывает, что «выталкиваемые» вверх средние вычеты выбирались регулярным образом (тройки с окаймлением следуют с постоянным шагом между ними в 7 строк) с чередованием очередности низ – верх по отношению к первой.
Значения КВК в этой таблице А3 выписаны в лексикографическом порядке с указанием первых степеней и номеров строк размещения дублей КВК. Строка с КВК меньшего делителя (1681) не дублируется. Номера (1123, 1133) строк-дублей КВК, окаймляющих «нулевую» строку-дубль (с нулевым значением среднего вычета rccc = 0), в сумме равны четной нетривиальной инволюции 1123+1133 = 2256 = In. Пары смежных строк с такими суммами в таблице следуют регулярно с шагом равным полусумме делителей (½(41 + 61) = 51). Четная нетривиальная инволюция
In =2256 = (1021 + 1235) = (1072 + 1184) = (1123 + 1133) = (1082 + 1174) = (1031 + 1225)
Пусть задано N = 2561 = 13×197. Пересечение областей ТКВК ∩ТССС = Ø пусто. В СМ-модели в строке (хо = 59) обнаруживается первый средний вычет (rccc = 1560 = 39×40) со свойством ССС. Он является центральным элементом в тройке (1640, 1560, 1482) смежных строк из списка ТССС. Крайние элементы (строки тройки) имеют номера хо (1640) = 255,
хо(1482) = 137 – 59 слой полного списка СММ (первый слой окаймления инволюции строками со средними вычетами).
В строке инволюций средний вычет rc = 641. Квадраты сомножителей (39 × 40 = 1560) центрального элемента тройки образуют первый слой строк окаймления строки с (rccc = 0). Рассмотрим послойное окаймление строки с нулевым значением среднего вычета (rccc=0), он лежит в строке с номером хо = 98 равным половине номера строки четной инволюции
In = 196).
Строками 1-го слоя (59-го в списке СММ) с КВК для rccc = 0 (их номера хо (rл = 1521) = 39, хо (rл = 1600) = 157) являются строки, содержащие квадраты сомножителей в произведении rccc = 39×40 = 1560. Эти КВК задает средний вычет, первым вытесняемый вверх списка инволюцией из строки с номером (хо = 196).
Замечание о зависимости делителей модуля N
При заданном (N = 2561 =13×197) соотношение делителей 197 – 2 = 13×15 = 195, инволюция In = 196. Для идемпотентов в строках с номерами хон = 1183, хов = 1182 значения разности равны tн =195, tв =197.
Строка нетривиальных инволюций окаймляется в 1-м слое строками со средними вычетами: хов = (rccc = 1482) = 137 и хон = (rccc = 1640) = 255, в центре между которыми в строке хо = ½ (137 + 255) = 196 должен лежать вытесняемый инволюцией средний вычет rccc = 1560 = 39×40, но он вытеснен в строку (симметричную строке с rccc=1640 относительно нулевой строки с rccc=0)
хо = 59 = 157 – 98 (первую с rccc =1560 ниже ТКВК). Произведение первых степеней этих КВК (39×40 =1560 = rccc) указывает на вытесняемый инволюцией вверх средний вычет.
В списке ТССС тройка смежных средних вычетов:1482=38×39 –1560=39×40 –1640 = 40×41. Крайние в тройке вычеты окаймляют первым слоем инволюцию
Заключение
На основе установленного свойства СММ определяются пары строк, образующие слои окаймления строки нетривиальных инволюций. Свойство СММ состоит в вытеснении строкой нетривиальных инволюций центральных строк из некоторых троек ТССС вверх списка СММ. Крайние строки троек – строки слоя окаймления НIn, а сумма их номеров определяет НIn.
Номер слоя окаймления строки инволюций совпадает с номером строки, в которую вытеснена центральная строка с rccc тройки.
При известных значениях номеров строк окаймления однозначно определяется номер строки нетривиальной инволюции, т.е. сама, меньшая из двух инволюция.
Строки 1-го слоя, окаймляющие инволюцию, содержат элементы кратные делителям модуля N, что при использовании ЗРД и алгоритма НОД Евклида обеспечивает вычисление делителей.
ссылка на оригинал статьи https://habr.com/ru/articles/869006/
Добавить комментарий