Как стать автором
Обновить

Как работать с моделью числа

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров1.6K

Часто ли мы задумываемся о числах, о том какова их внутренняя структура, как они устроены? Пока не возникает потребность, необходимость в ответах на сформулированные и многие другие вопросы нас это никак не беспокоит. В какой-то момент жизни мне эти вопросы пришли в голову. Порылся в книгах о числах, понял, что так как они написаны лучше вообще не писать. Авторы не стремятся довести до читателя возникшую проблему, которая возникла перед ними, не формулируют цель, которую они поставили перед собой, не показывают тот путь, которым им пришлось пройти до достижения цели. Излагается, как правило, уже оформленный результат.

История науки содержит массу примеров такой фразы «отсюда с очевидностью следует» или «легко получить», после которой пишется про как-то полученный результат. Эти фразы сбивают с толку читателя. Приятное исключение представляют работы Ньютона и Эйлера, с оригиналами которых мне довелось познакомиться. Если они демонстрируют вывод формулы, то не опускают даже, казалось бы, очевидных вещей все излагается последовательно без пропусков, подробно комментируется. На память приходит случай с Лапласом, где он получил урок

Один школьный из провинции учитель Франции последовательно повторял за Лапласом все опубликованные им результаты, пока не споткнулся на одном из них. Желая прояснить вопрос, он из провинции прибыл в Париж и обратился к самому Лапласу. Тот не отвернулся от учителя, хотя и был удивлен, что нашелся кто-то, кто повторял за ним все его результаты, как бы проверяя их работоспособность и правильность.

Выслушав вопрос учителя, Лаплас попросил его прийти на следующий день, но оказался не готов ответить и перенес встречу на неделю, но и недели оказалось мало, учителю пришлось покинуть Париж без ответов, но с обещанием от Лапласа, что тот его известит, когда ответ будет готов. Это случилось три месяца спустя.

Лаплас пригласил учителя стать своим помощником-вычислителем, на что учитель согласился. Лаплас (возможно в отместку) усадил учителя за расчеты астрономических таблиц (рутинный труд). Учитель посвятил таблицам более 20 лет и свой жизненный путь так за их расчетом и закончил.

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

Введение

В статье приведена табличная форма модели числа N = 407. Это полная модель с претензией на универсальность, с которой работаю я сам. Можно сказать, что я раскрыл ее для читателей, но сохраняю на нее авторские права (©). Один из читателей самостоятельно по изложенным правилам построения модели написал программу, как он выразился «нашаманил». После этого потребовались небольшие консультации и исправление ошибки для полного совпадения его версии с авторским вариантом таблицы (списка СММ).
Изложенное здесь легко отследить в комментариях к статье. Лично я этому рад и доволен, так как теперь все мои утверждения и выводы, получаемые на основе этой СМ-модели, легко проверяются и могут быть повторены, подтверждены или опровергнуты, если мной допущена ошибка, и оппонент мне сможет указать даже место, где она допущена. Надеюсь, что время, затраченное читателем на написание программы (оно не может быть большим), уже окупилось, во-первых, пониманием устройства СМ-модели и, во-вторых, возможностями получать решения задач, которые вне рамок СМ-модели решаются только тотальным перебором (например, поиск корней квадратичных сравнений), либо не решаются вообще. Например, если для некоторого N найдена нетривиальная инволюция в кольце, то каким может быть другое N с такой же инволюцией, а при каких N это невозможно. Другой путь решения, судя по доступным публикациям, пока не найден.
Я использую модель для решения нескольких задач, в число которых включена факторизация составного числа N = pq, поиск корней квадратичных сравнений, ключевых элементов КЧКВ и др.

Как используется модель, как с ней работать, проводить исследования чисел?
На вход модели подается составное полупростое число N = pq. Программа модели строит строки, включающие элементы (х1, хо) конечного числового кольца вычетов (КЧКВ) по модулю N. Задать можно и любое другое число, но при N простом получим конечное поле, другие случаи не оговариваются, так как СМ-модель ориентирована на числовое кольцо вычетов.
Дополнительно программа вычисляет и помещает в строки таблицы квадратичные вычеты (КВВ) всех элементов КЧКВ (это колонка левых вычетов (Rл)), вычисляет средние вычеты (колонка ) и правые вычеты (это колонка (Rп) правая в таблице). Табличная форма модели дополняется также встречно направленными начальными фрагментами последовательности нечетных чисел (ПНЧ) – колонки (Т, Тп). Так же как это сделано природой с нитями ДНК для симметрии хромосом в живой клетке.
Для удобства обозрения и ускорения поиска элементов СМ-модели программа осуществляет разметку элементов (заливкой определенных ячеек в строках цветом). Понятно, что предварительно делается допущение о том, что делители (р и q) модуля КЧКВ известны.
Впрочем, они (в частности, меньший делитель dm) в СМ-модели легко определяются. В начальной части списка СММ находим ближнюю к началу списка пару смежных строк, в которых ячейки столбца средних вычетов (Rc) имеют общий делитель, при этом ячейка столбца Тп нижней строки пары будет занята значением dm. В примере с N = 407 это строки хо = 5, 6, а dm =11. Больший делитель определяется делением dб = N:dm.
Все клетки с полными квадратами в левой колонке заливаются (желтый цвет), клетки строк, содержащие кратные делителей N заливаются (синий цвет). В колонке средних вычетов часть элементов размечается заливкой (rccc зеленый цвет). В колонках Т, Тп непрерывные участки, включающие нечетное число клеток равное меньшему делителю (dm) с центральным элементом равным большему делителю () размечены (оранжевый цвет). Сумма оранжевых элементов равна N. Красным цветом выделены ключевые элементы СМ-модели строка нетривиальных инволюций, строка (ее номер равен половине четной инволюции), содержащая средний вычет равный нулю, называемая «нулевой».

После завершения разметки элементов разным цветом легко устанавливаются в колонках интервалы из элементов без заливки между строками с синей заливкой для (х1, хо), т.е. кратными делителям N. Такие интервалы бывают двух типов: с четным числом строк и нечетным числом строк. Когда четность интервалов установлена, то легко видеть, что центральные строки нечетных замкнутых интервалов строк без заливки всегда содержат полный квадрат в левой (первой) позиции (желтая заливка).

Граничными (правым, левым) элементами таких решающих (РИ) интервалов всегда являются кратные разных делителей N. Это явление имеет место в СМ-модели для всех исследуемых чисел (не простых и бес- квадратных). Явление объясняется действием Закона распределения делителей (ЗРД  здесь) числа. Все оказалось достаточно просто, но кто-то должен был это обнаружить, увидеть, понять и оформить как закон. Мне это удалось в 2014 году, о чем и была сделана публикация.
Меня не покидает убеждение, что СММ содержит (возможно с каким-то расширением) данные о делителях (это совершенно очевидно) числа N и сведения о том как и что надо делать с заданным составным числом N, чтобы вывести окончательную формулу для делителей. Кое-что уже сделано на этом пути, но желательно красивое завершение, после которого разговоры о методах решета, переборных схемах, алгоритме Шора и квантовых вычислениях отпадут сами собой.

ЗАМЕЧАТЕЛЬНЫЕ ЧИСЛА

Существуют составные полупростые числа, проявляющие удивительные замечательные свойства, о существовании которых можно задуматься, но совершенно непонятно как такие свойства у чисел устанавливаются и как получать сами числа с предсказываемыми, (желательными) свойствами. Например, как получить пару чисел (составных модулей приведения колец вычетов), при которых в одном и в другом кольце будут совпадающие нетривиальные инволюции или, например, как задать число заданного типа из трех возможных с нужным распределением средних вычетов вида rccc.
Из наличия такого свойства при различающихся модулях N1 ≠ N2 следует, что в СМ-моделях этих чисел номера строк нетривиальных инволюций в списках будут иметь совпадающие значения, так как номер строки инволюций – это и есть сама меньшая инволюция. Большие инволюции в строке, понятно, будут различны так как
IN1 + In1 = N1N2 = IN2 + In2, но In1 = In2.

Пример 1. Пусть N1 = 11·37 ≠ N2 = 17·37. Числа N1 и N2 имеют совпадающие большие делители своих модулей. Проверим наличие свойства N1 ≠ N2 – совпадения инволюций. По определению инволюция – элемент кольца вычетов по составному модулю, квадрат которого равен единице. В нашем примере элемент с номером хо = 186 обоих колец – инволюция.   Действительно, 1862 (mod N1) = 34596 (mod 407) = 1,
1862 (mod N2) =34596(mod 629) = 1.
Поиск таких пар чисел или подмножеств натуральных чисел – нетривиальная задача. Ниже в таблице 1 приводятся такие пары для небольших составных полупростых чисел. Любопытно, что при N = 73 и 79 обнаружены даже по две таких пары: для инволюции
In =218 это (N = 511 = 7·73 и N = 2263 = 31·73); для инволюции In = 220 это
(N = 949 = 13·73 и N =1241 = 17·73). С другой стороны, для N = dm·59 не нашлось ни одной пары.

Строка с пометкой In – содержит меньшую нетривиальную инволюцию в кольце. Цветом выделены совпадающие инволюции при отличающихся модулях кольца.

При большем делителе dб = 73 и dб = 79 возникает по две пары модулей КЧКВ с совпадающими меньшими нетривиальными инволюциями. Для
dб = 73 это пары 511, 2263 с In = 218, и 949,1241 с In = 220, для dб = 79 это пары 553, 869 с
In =78, и 1501,2291 с In=552.

В первом случае наблюдаем вложенный порядок пар, во втором – последовательный. Для dб = 151 наблюдаются три пары 1661 (In = 452), 3473 (In = 1358), 5587 (In = 9622), 6191(In = 452), 8003(In = 1962), 8909(In = 1358) с пересекающимся порядком следования.
Пара инволюций In = 1962 вложена в паре In = 1358, а одна инволюция из пары In = 452 вложена внутрь обеих других.

Составные полупростые числа с одинаковым большим делителем в колонках СММ левого и среднего вычетов содержат последовательности полных квадратов и произведений сохраняющих смежность сомножителей (свойство ССС), встречающихся, как правило, с шагом dm. Нарушение порядка в этих последовательностях определяется вклиниванием в них нетривиальных малых и больших идемпотентов (Id, ID) и инволюций (In, IN).

Заметим, что совпадение инволюций отмечено только у модулей с равным dб делителем.
Открытым остается вопрос о порядке следования значений средних вычетов вида rccc, но не значений полных квадратов, так как значения полных квадратов во всех позициях колонки КВВ определяются ЗРД. Со временем выяснилось, что для средних вычетов управление порядком следования значений rccc в большой мере осуществляется нетривиальной инволюцией (строкой инволюций), но это не окончательный вывод.

Эта строка окаймляется послойно строками, содержащими rccc, и сумма номеров строк (ход табл. А) окаймляющих строк слоя – удвоенный номер строки In. Слои окаймления в СММ концентрически (как в матрешке) вкладываются один в другой, начиная с меньшего (1-го номера). Пары строк в окаймлении каждого слоя – это крайние строки в тройках строк, возникающих в тривиальной области ТССС.

Ниже (табл. А) приведен фрагмент списка СММ, содержащий ТССС. В таблицу дополнительно вставлена (справа от колонки средних вычетов) колонка номеров (ход) строк-дублей размещения средних вычетов в списке СММ. Средние вычеты вида rccc, включаемые в кратные строки, которые не дублируются, сохраняют исходные номера строк. Например,
(хо = 185 = 5·37 для rccc = 342, хо= 187 = 11·17 для rccc = 272 и хо = 198 = 11·18 для rccc= 30), сохраняют номера строк оригиналов.

Ранее установлено, что строка нетривиальных инволюций занимает среднее положение между строками, содержащими КВВ – полные квадраты значений (dm + 1)2 и (dm – 1)2, т.е. позицию, как бы отводимую квадрату меньшего делителя N. Фрагмент (табл. А) в колонке левых вычетов включает полные квадраты КВК 102 = 100 и 122 = 144 (первый слой окаймления квадратами строки инволюций), а также строку-дубль с номером хо = 174, содержащую rccc = 56. Такое расширение фрагмента позволяет выполнить расчеты для троек ТССС (272, 306, 342) и (30, 42, 56) без заполнения колонки ход.

Пример 2
. Для N = 407 = 11·37, dm = 11. Окаймляющие строку нетривиальных инволюций строки (1-й слой), содержащие полные квадраты (102 = 100 и
122 = 144 лежат в строках хо = 175 и хо = 197) как бы предполагают между ними строку с квадратом (dm = 11), но она занята строкой инволюций
хо = ½ (175+197) = 186 (с квадратом 12 = 1). Вытесненная инволюцией средняя строка тройки содержит средний вычет rccc= 306 = 17·18.

Это средняя строка тройки строк в ТССС (272, 306, 342) вытесняется строкой нетривиальных инволюций в верх списка СММ, а ее место занимает строка нетривиальных инволюций. При этом номер строки, в которую вытесняется средняя строка тройки, равен половине разности номеров строк крайних в тройке. Половина суммы номеров этих строк – номер строки нетривиальных инволюций хо= In = 186.  Вычисления подтверждают высказанные положения.
Таблица А. Фрагмент списка СММ (N = 407), содержащий

Таблица А. Фрагмент списка СММ (N = 407), содержащий
Таблица А. Фрагмент списка СММ (N = 407), содержащий

Строка с rccc = 306 вытесняется из тройки ТССС в строку, с номером равным половине разности номеров крайних строк тройки ход = ½ (хо (272) – хо (342)) = ½ (187185)) = 1. Половина суммы номеров крайних строк равна ход = ½(хо(272) + хо(342)) = ½(187 + 185)) = 186 номеру строки меньшей инволюции. Тройка строк ТССС с таким свойством оказывается не единственной.

Во всех подобных тройках, номера средних строк которых равны половине суммы номеров крайних строк троек совпадают с инволюцией, средние строки тройки вытесняются в верх списка СММ.

Позиции вытеснения определяются при этом половиной разности номеров строк, крайних в тройках.  Для второй тройки (30, 42, 56) расчеты дают номер строки вытеснения равный половине разности номеров крайних строк тройки ход = ½ (хо(30) – хо(56)) = ½(198174)) = 12. Половина суммы номеров крайних строк тройки совпадает с номером строки инволюций, т.е. ход = ½ (хо (30) + хо (56)) = ½ (198 + 174)) = 186 = In.

Таблица Б. Совпадающие ключевые элементы колец вычетов (инволюции) при парах (N1= 407, N2 = 629), (N3 = 371, N4 = 1219), (N5 =469, N6=1943), (N7 =781, N8 =923)

Для инволюций ов - окаймляющая верхняя, а он - окаймляющая нижняя строки
Для инволюций ов - окаймляющая верхняя, а он - окаймляющая нижняя строки

Таблица Б разделяется на 8 частей, соответствующих конкретным модулям N. Левая часть таблицы соответствует первым в парах модулей – правая часть – вторым в парах. В каждой из 8-и частей приведены фрагменты из пяти строк СМ-модели. Верхние три строки содержат нетривиальные инволюции со строками окаймления 1-го слоя, две нижние – идемпотенты. В верхней части меньшая In = 186 совпадает для первой пары модулей, в следующих частях In = 160, In = 202, In = 285    – для других пар). Нижние две строки каждой части таблицы – это строки, содержащие идемпотенты своих колец.

Идемпотенты верхней пары модулей оба нечетные для N1 и четные для N2, в другой паре наоборот. По свойству идемпотентов КЧКВ их разность равна четной инволюции, что мы и наблюдаем. Значения t в строках идемпотентов совпадают с номерами окаймляющих инволюцию строк и совпадают для разных пар модулей. При этом значения tп различны. Замечание. Значение tп в строке с номером хо = In нетривиальных инволюций увеличено на номер окаймляющей ее сверху строки tп = хо + хо – 1 = о –1, в верхней строке rл = t.  В нижней строке окаймления значение tп на единицу меньше левого вычета этой же строки
rл tп = 1, а её  rл = 2(хо + 1) = tп + 1.
Пример 3. Пусть N = 887∙ 997 = 884339 = 442169 + 442170, тогда rло= 221085, rпо= 663254, rc1 = 1+663254 = 663255. Строки с инволюциями и окаймления первого слоя получают вид

В соответствии с замечанием имеем: номер строки инволюций хо = In = 128614; её половина ½ In = 64307, tп (In) = о – 1 = 2∙128614 – 1 = 257227; rл (хо + 1) – tп (хо + 1) = 1. 
rл (хо + 1) = 2(хо + 1) = 2(128614 +1) = 257230.

Вычисление инволюций в кольце вычетов по составному модулю

В СМ-модели строка нетривиальных инволюций является строкой-дублем тривиальных инволюций. Сами инволюции не являются кратными делителей N элементами кольца вычетов по составному модулю. По закону распределения делителей (ЗРД) центром одного из решающих интервалов является строка нетривиальных инволюций, так как в этой строке возникает полный квадрат, равный единице (12). Последнее соответствует тому, что строки, первого слоя, окаймляющие инволюцию и смежные с ней, являются кратными разным делителям N большему (dб) и меньшему (dm).

С другой стороны, значения х – х= 2 и хон – хов = 2 в окаймляющих строках различаются на 2. Из этого следует, что при известных делителях N наиболее простой путь отыскания нетривиальных инволюций, – метод перебора кратных большего делителя (kdб). В цикле меняете k, находите произведение (kdб), плюсуете (kdб+2) и делите сумму на (dm). Если разделилось нацело, то (хо = kdб+1) номер строки нетривиальных инволюций найден. Начинать поиск следует с большего делителя, так как их в списке меньше.

Пример 4. Пусть N = 41∙ 61 = 2501. Найти нетривиальную инволюцию. Начнем с большего делителя. Если окаймляющая строка с номером
хо = (kdб) = 2∙61 = 122 кратным большему делителю, то номер окаймляющей строки с другой стороны на 2 единицы отличается от этого номера, т.е. хов = 122+2 = 124 и должен нацело делиться меньшим делителем. Но 124 не делится на dм= 41. Следующий шаг (k = k+1= 2+1=3) поиска в цикле дает значение хов = 3∙ 61 = 183 кратным dб для него пара хон = 183 + 2 = 185 не делится на dм = 41. Третий шаг (k = k+1 = 3+1 = 4) поиска дает значение хов = 4∙ 61 = 244 кратным dб для него пара хон = 244+2 = 246 делится нацело меньшим делителем dм = 41. Следовательно, между значениями хов = 244 и хон = 246 лежит меньшая нетривиальная инволюция (In = 245).

Между строк окаймления лежит строка инволюций с номером хо = 245. Действительно,
2452(mod N) = 60025(mod 2501) = 1. Этот результат получен при допущении об известных делителях N. У нас другая задача – отыскание самих делителей, когда они неизвестны.
Здесь приводится пример нахождения такого решения.

В СМ-модели строка тривиальных инволюций (самая верхняя строка) может дублироваться. Это происходит и тогда, когда значение среднего вычета (rc1) в этой строке сохраняет свойство смежности сомножителей (ССС). Эти условия однозначно обеспечивают поиск строки нетривиальных инволюций, а ее окаймление – делители модуля N.

Устанавливается эти факты следующим образом. При заданном полупростом N = dмdб вычисляются значения rл0, rп0 нижней («нулевой») строки и rc1 = rп0 +1, и, если флексия rc1 принадлежит множеству Ф ={0,2,6}, в цикле по i проверяется (извлечением квадратного корня) разложение rci на множители в соответствии с описанной ранее процедурой. После чего вычисляется сумма (t0 + t1)= t сомножителей, которая равна разности
t = x1 – xо в некоторой строке, а произведение вычисленных сомножителей должно совпадать со средним вычетом первой строки t0 ∙ t1 = rc1.

Для определения нетривиальных инволюций определяется номер строки, содержащей эти инволюции. Для этой строки как раз и определена разность t = x1 – xо. Из этого уравнения находим номер строки дубля инволюций, а именно, xо = ½ (N – t). Этот номер является (совпадает с) меньшей нетривиальной инволюцией и для него (в качестве проверки) должно выполняться соотношение xо 2 ≡ 1(mod N).

Дальше решается задача факторизации самого составного модуля N = dмdб. При известном номере строки-дубля инволюций – решение этой задачи оказывается практически тривиальным, использующим алгоритм НОД Евклида. Возникает вопрос обращения в рамках рассмотренной задачи. Когда, в каких условиях средний вычет первой строки приобретает свойство ССС.

В прямой задаче используется соотношение rc1 = rп0 + 1, но это значение среднего вычета может быть рассчитано иначе. Разность частей x1 – xо = t = t0 + t1 первой строки СМ-модели N – 2xо = t раскладывается в сумму смежных слагаемых t0 = t1 – 1, после чего их произведение редуцируется (приводится по модулю) tо∙ t1 ≡ rc1(mod N).  В алгоритме решения задачи используются оба способа вычисления.

Рассмотрим в качестве модуля приведения N алгебраического кольца по составному модулю числа: 407, 559,1159, 32239, 330007. Каждое число представим суммой смежных слагаемых (последняя строка списка СММ), после чего определим для них (rло) квадратичные вычеты (левые КВВ) по модулю и разность (N – rло = rпо) правый вычет «нулевой» строки.
В СМ-модели числа N сумма 1+ rпо = rс1 равна среднему вычету первой строки списка для всех пяти заданных чисел.

Средний вычет для них раскладывается в произведение смежных сомножителей, так как rс1 = rссс. Такое свойство среднего вычета обеспечивает определение номера строки-дубля тривиальных инволюций (для 1-й строки СММ). Это делается так. Смежные сомножители (это t1 и tо), найденные для каждого среднего вычета, суммируются (t = t1 + tо).

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

Приведем несколько однотипных вычислительных примеров: больший делитель равен трехкратному меньшему, увеличенному на 4.
Пример 5. Пусть N = dмdб = 11∙37 = 407 = 203 + 204. Заметим, что больший делитель определяется линейной формулой со свободным членом с =4, k=3, dб = kdm+c = 37 = 3∙11+ 4.

Больший делитель является линейной функцией меньшего делителя. Выполним вычисления rл0 = ½∙204 = 102, rп0 = 407 – 102 = 305, тогда rc1 = 305 + 1 = 17∙18 = 306 раскладывается на смежные сомножители. Для rc1 = rcсс выполнено свойство ССС, так как 17 = 18 – 1.  Для факторизации модуля N находим значение t = 17 + 18 = 35, и нетривиальную инволюцию xо = In = ½∙ (N – t) = 186, GCD (N, xо ± 1) = {dм = 11, dб = 37}.

Пример 6. Пусть N = dмdб =13∙43 =559=279+280. Заметим, что 43 =13∙3+4.
Больший делитель является линейной функцией меньшего делителя. Выполним вычисления
rл0 = ½∙280 = 140, rп0 = 559 – 140 = 419, тогда rc1 = 419 +1 = 20∙21. Для rc1 выполнено ССС, так как 20 = 21 – 1. Для факторизации модуля N находим значение t = 20 + 21 = 41, а по нему инволюцию xо = In = ½∙ (N – t) = 259, и делители GCD (N, xо ± 1) = {dм= 13, dб = 43}.

Пример 7. Пусть N = dмdб = 19∙61 = 1159 = 579 + 580. Заметим, что 61 = 19∙3 + 4. Больший делитель является линейной функцией меньшего делителя. Выполним вычисления rл0 = ½∙580 = 290, rп0 = 1159 – 290 = 869, тогда rc1 = 869 + 1 = 29∙30 = 870. Для rc1 выполнено свойство ССС, так как 29 = 30 – 1. Для факторизации модуля N находим значение
t = 29 + 30 = 59, а по нему инволюцию xо = In = ½∙ (N – t) = 550, после чего делители модуля GCD (N, xо ± 1) = {dм = 19, dб = 61}.

Пример 8. Пусть N = dмdб = 103∙313 = 32239 = 16119 + 16120. Заметим, что 61 = 19∙3+4. Больший делитель является линейной функцией меньшего делителя со свободным членом с = 4. Выполним вычисления
rл0 = ½∙16120 = 8060, rп0 = 32239 – 8060 = 24179, тогда rc1 = 24179 +1 = 155∙156 = 24180.

Для rc1 выполнено свойство ССС, так как 155 = 156 – 1. Для факторизации модуля t = 155 + 156 = 311, xо = In = ½∙ (N – t) = 15964, GCD (N, xо ± 1) = {dм = 103, dб = 313}.

Пример 9. Пусть N = dмdб = 331∙997 = 330007 = 165003 + 165004. Заметим, что 997 = 331∙3 + 4. Больший делитель является линейной функцией меньшего делителя. Выполним вычисления для rл0 = ½∙165004 = 82502, rп0 = 330007 – 82502 = 247505, тогда

rc1 = 247505 + 1 = 497∙498. Для rc1 выполнено ССС, так как 497 = 498 – 1. Для факторизации  t = 497 + 498 = 995, xо = In = ½∙(N – t) = 164506, GCD (N, xо ± 1) = {dм = 331, dб = 997}.

 Заключение

1. В статье рассмотрены вопросы моделирования составного числа N с задачей нахождения его неизвестных делителей (задача факторизации N).
2. Показано, что область строк (ТССС) тривиальных средних вычетов СМ-модели может быть разбита, на тройки строк, средняя строка которых вытесняется строкой нетривиальных инволюций в верх списка модели в строку полуразности номеров крайних в тройке строк, а половина суммы номеров крайних в тройках строк равна номеру строки нетривиальных инволюций.
3. Установлена связь пар модулей приведения колец вычетов, содержащих совпадающие меньшие нетривиальные инволюции. Показано, что для некоторых пар составных чисел N (модулей кольца вычетов), имеющих общие большие делители (dб) в построенных СМ-моделях нетривиальные меньшие инволюции могут совпадать, что указывает на совпадающий номер строки нетривиальных инволюций в обеих моделях. Совпадающие номера строк, окаймляющих строку инволюций в моделях, совпадают со значениями разностей (t) в строках идемпотентов.




Теги:
Хабы:
-2
Комментарии15

Публикации

Ближайшие события