Составное число и его факторизация

В комментариях к моим статьям факторизации составного числа регулярно встречаются возражения по поводу понятия «модель числа» – это какой-то оксюморон, фантазии автора и др.
В ответ могу только заметить, что в математике имеют дело с натуральными (N), целыми (Z), рациональными (Q), вещественными (R) и комплексными (С) числами. Приведенные термины по существу называют модели чисел с четко различимыми свойствами и допустимыми операциями в каждом из множеств названных чисел. Соотношения между этими моделями задается  включением левого (меньшего) в правое (большее) множество чисел N ⸦ Z ⸦ Q ⸦ R ⸦ C.
Главными операциями над множествами чисел в таких моделях являются сложение (+) и умножение (×), обратными к которым являются операции вычитания (–) и факторизация (×^-1).

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

Когда мы представляем число из некоторого множества суммой слагаемых а + b, то, изменяя значения а и b так, чтобы сумма их оставалась постоянной, мы задаем аддитивное представление конкретного числа или его аддитивную (линейную) модель. Такая списочная многострочная модель (СММ) допустима во всех известных множествах. Совокупность сумм для N = х + у, где х и у – переменные модели, с накладываемыми на них ограничениями, задает модель числа N. А распределение делителей числа N в натуральном ряде задается законом распределения делителей (ЗРД) числа.

При описании математическими средствами объекта, явления или процесса мы используем отображение (функцию от переменных), которое называем моделью объекта, явления или процесса. Разработка и исследование таких моделей имеет целью определение таких значений переменных модели, которые отвечают  наилучшим описаниям объекта, явления или процесса и цели проводимого исследования, не выходя за рамки допустимого.

Возможности СМ-модели составного числа

Рассматриваются полупростые бесквадратные составные нечетные натуральные числа (СННЧ). Интерес представляют возможности СММ применительно к решению ЗФБЧ, начиная с двух крайних случаев относительно max и min удаленности друг от друга собственных делителей числа N = dm∙dб. Оба случая однозначно определяют нетривиальные инволюции в СМ-модели.

Очевидно, min удаленности достигается, когда пара делителей СННЧ представлена  простыми  числами-близнецами, а max, – когда меньший из делителей тройка.  Покажем, что в этих крайних случаях задача факторизации большого числа (ЗФБЧ) решается, не прибегая к переборным алгоритмам, простыми средствами. Это стало возможным на основе изучения СММ и использования ЗРД.

В первом случае (mах) наибольшей удаленности делителей меньший из них dm = 3, а другой простой делитель dб >5  max удален от dm. Больший делитель (dб) в СММ и его удвоенное значение (2dб) размещаются в единственной строке – А1 – аттракторе с номером большего делителя dб. Из этого следует, что идемпонент кратный большему делителю как раз лежит в строке с номером хо = dб .

Но в СМ-модели строки, содержащие идемпотенты, – смежные, следовательно, строка с номером хо = dб – 1 содержит либо больший идемпотент кратный меньшему dm, либо четную инволюцию. Положение строки инволюции также определено, но номером хо= dб ±1, так как она окаймляется кратными разным делителям d_m и d_б строками. Но строка с большим делителем единственная, она примыкает (сверху\снизу) к инволюции.

Для однозначного ответа вычисляем КВВ номера строки (dб – 1)²(modN). Если результат равен 1, то хо = dб – 1 строка нетривиальных инволюций сверху, иначе – снизу. Между этим и случаем
с min удаленностью ∆ = 2, характерным для делителей простых чисел-близнецов, лежат все остальные случаи, которые решаются не так просто, как обозначенные (крайние).
 
Пример 1.  Рассмотрим в деталях случай (mах) наибольшей удаленности делителей.
Пусть N = dm∙dб = 3∙333331= 999993. Меньший делитель dm = 3, больший ограничен, но не кратен тройке. В этом случае (mах удаленности ∆ = 333331 – 3 = 333328). В списке СММ существует единственная строка с номером х_о = 333331 с аттрактором А1 – это сам больший делитель А1 = dб = 333331 и все квадраты (дубли КВК) группируются в его области аттракции. Коэффициент кратности номера этой строки k = 1. Из этого следует, что такая строка содержит идемпотент Id (меньший), а строка над ней (номер х_о = 333330) содержит другой идемпотент I_D (больший) со значением  I_D = N – 333330 = 666663.

Действительно, 333331²(modN) =333331 и 666663²(modN) = 666663. По свойству идемпотентов
их сумма равна N +1 = 666663 + 333331 = 999994, а их разность всегда равна четной инволюции In = 666663 – 333331 = 333332, (333332²(modN) = 1). Номер ее строки х_о = 333332 совпадает со значением инволюции. Строка инволюций примыкает снизу к строкам идемпотентов. (Для N =33
(см. табл. 3) нетривиальная инволюция хо = In = 10 примыкает сверху строк идемпотентов).

Поскольку в примере 1 существует единственный аттрактор, то все КВК-дубли размещаются в области его аттракции, наиболее удаленными от аттрактора являются значения КВК = 996004 (сверху) на удалении ∆ = 333331 – 332333 = 998 и (снизу) КВК = 994009 – в строке х_о = 334328 на удалении ∆ =334328 – 333331 = 997. Кратные строки из ТКВК не дублируются.

КВК = r_л=1 соответствует центру решающего интервала (ЦРИ) с х_о = 333332. Эта строка окаймляется строками с номерами кратными разным делителям. Номер строки сверху на единицу меньше
х_о = 333332 – 1 = 333331 – это аттрактор dб больший делитель. Строка снизу на единицу больше х_о = 333332 +1 = 333333 = 3∙ 111111 – ее номер кратен меньшему делителю dm =3.

Во втором случае (min) наименьшей удаленности в СММ – делители это простые числа-близнецы, например, N =17∙19 = 323 с min удаленностью (∆=2)  делителей друг от друга. Для наглядности приведена (таблица 1) СМ-модель числа (сокращенная до 4 столбцов), что для анализа наглядно и удобно. Приведу пару теорем, связанных с числами простыми-близнецами

Теорема. Если число N равно произведению простых-близнецов, то r_л левый квадратичный вычет (КВВ) последней строки СММ – полный квадрат.
N = 857*859 = 736163, d_m и d_б  близнецы r_ло = 429² = 184041 = [½(736163+1)]²(mod 736163).
Обратное положение неверно: для N = d_md_б = 65, (dm = 5, dб = 13 не близнецы), но в последней строке КВВ  r_ло = 49 =7².  Найти доказательство предлагаю читателям.
Теорема. Нетривиальная четная инволюция равна номеру строки со значением между близнецами In = ½(d_m + d_б).
Для N = 323, In = ½(17 + 19) = 18, что соответствует центру решающего интервала (ЦРИ). Эта строка примыкает к области ТКВК. 

В таблице обозначены: Ц – центр; Д0 – дубль нулевой строки; ДIn – дубль инволюции;
ДЦ–дубль центра; Id, ID – идемпотенты.

Анализ ситуации. Задано СННЧ N = 323. Делители N неизвестны, как и то, что они близнецы.
Пример 2. (Делители числа N неизвестны, и мы даже не знаем, что они простые-близнецы).
Формируем последнюю строку СМ-модели по заданному N = d_md_б = 323 разложением N в сумму смежных слагаемых 323 = х_1о + х_оо = 162 + 161. Вычисляем квадратичный вычет (КВВ) в строке.
При четном х1о > хоо, КВВ = r_ло = ½х1 = ½162 = 81 = 9².

Номер последней строки СММ х_оц = 161 для делителей-близнецов всегда содержит r_ло полный квадрат КВВ = КВК. По закону распределения делителей (ЗРД) границы ЦРИ-числа кратные разным d_m и d_б  делителям.
Вычислив границы (Гл, Гп) решающего интервала (РИ), находим делители числа N = 323,
Гл = х_оц –√КВК =161 –√81=152 =19∙8, 
Гп = х_оц+√КВК =161+√81 =170 =17∙10, делители d_m = 17 и d_б = 19.

Промежуточные случаи между удаленностями min и  max делителей также классифицируются, но по типам чисел. Тип числа определяется наличием\отсутствием строк-дублей, содержащих r_ссс, в области ТКВК СМ-модели. Строки в ТКВК отсутствуют (тип 0), имеется 1 строка (тип 1), имеется 2 строки (тип 2).

Для уяснения типологии чисел рассмотрим пример со сближением делителей. Устанавливаем проявление типов чисел, получаемых как произведение d_б = 997 на сомножители из списка:
d_m = 71,73,79,83,89,97,101,103,107,109,113,127. Произведение N = 997*71 = 70787 генерирует первый раз строку, содержащую средний вычет rcссо = 53592 =231*232 в позиции хо = 267. Строка с rcсс0 (вне ТКВК) примыкает снизу к ТКВК с порогом хо = 266 и КВК = 70756. Все произведения 997*d_m с меньшим сомножителем, чем d_m =71, не создают строк с rcсс в области ТКВК. В этом легко убедиться вычислениями: rcсс1-первая, rcсс2-вторая строки в ТКВК.

Для произведения 2-х чисел (ниже) в ТКВК возникает одна строка со средним вычетом rcсс1

997*73 =  72781, хо = 231,  КВК = 53361, rcсс1 = 71556 = 267*268,
997*79 =  78763, хо = 269,  КВК = 72361, rcсс1 = 52670 = 229*230,
997*83 =  82751, хо = 270,  КВК = 72900, rcсс1 = 52212 = 228*229,
997*89 =  88733, хо = 227,  КВК = 51529, rcсс1 = 73712 = 271*272,
997*97 =  96709, хо = 225,  КВК = 50625, rcсс1 = 74802 = 273*274,
997*101= 100697, хо= 224, КВК = 50176, rcсс1 = 75350 = 274*275,
997*103= 102691, хо= 275, КВК = 75625, rcсс1 = 49952 = 223*224,
997*107= 106679, хо= 276, КВК = 76176, rcсс1 = 49506 = 222*223,
997*109= 108673, хо= 222, КВК = 49284, rcсс1 = 76452 = 276*277.

Для произведения 2-х чисел (ниже и больших) в ТКВК возникает две строки с rcсс1 и rcсс2
N = 997*113 = 112661, хо = 221, КВК = 48841,
rcсс1 = 77006 = 277*278,
rcсс2 = 27060 = 164*165,
х0 = 334, КВК = 111556, Порог ТКВК = 112225 в Хо = 335
N = 997*127 = 126619, хо = 154, КВК = 23716,
rcсс1 = 118680 =344*345,
rcсс2 = 47306 = 217*218,
х0 = 281, КВК = 78961, Порог ТКВК = 126025 в Хо = 355

Сделаем вывод: расстояние (удаленность) между делителями N играет существенную роль при поиске решения различных задач, например, поиск корней сравнений и в первую очередь ЗФБЧ.
Это положение подтверждается анализом моделирования такой удаленности делителей.
Начнем сближать делители и контролировать поведение переменных (среднего вычета r_с и др.) Средний вычет строки (r_с) формируется из разности t = x1 – xо, которая всегда нечетное число.

Эту разность t = t1 + tо представляем суммой смежных слагаемых, после чего слагаемые перемножаем r_с = t1 × tо. При превышении средним вычетом (r_с) значения N приводим по (mod N). При этом происходит самое интересное (и важное) – часть средних вычетов сохраняет (после приведения по модулю N) свойство смежности сомножителей (их обозначим r_ссс, сомножители уменьшаются), а большая часть не сохраняет. Это еще не все!  

Те средние вычеты (r_ссс), что сохранили смежность сомножителей образовали в нижней части столбца Rc область непрерывно следующих тривиальных средних вычетов (см. табл.3), сохраняющих смежность сомножителей (они все обозначены r_ссс= 0,2,6,12,20,30), а саму область обозначим ТССС. Три значения (r_ссс= 0,6,12) из этой области дублируются в строках СММ, распределяясь по списку неким загадочным образом. Остальные (r_ссс= 2,20,30) принадлежат кратным строкам и не дублируются.

Дубли иногда могут попасть  даже в строки верхней области тривиальных строк ТКВК. Возможность такого попадания в строки ТКВК положена в основу типологии натуральных чисел. Числа N = 1961, N = 1963 и N = 1969 очень близки, но первое относится к типу 2, второе – к типу 1, а третье к типу 0. Дело в том, что факторизовать N = 1969 в рамках СММ значительно труднее, чем N = 1961 и N = 1963. К этим вопросам мы еще вернемся чуть позже.

Работа с моделью числа. Таблица 1 представляет собой СМ-модель составного натурального нечетного числа N = рq = d_md_б, обеспечивающую получение решений задач, которые без нее столь же просто решить не удается. С описанием списочной многострочной модели (СММ) можно ознакомится в (habr.com›ru/articles/829244/).

Пример 3. Подмоделей СММ N =2501, содержащих строки тривиальных (ЦМС Н-1) и нетривиальных (ЦМС Н-25) инволюций. Перестроение подмодели ЦМС Н-25 начинаем строкой  инволюций.
Таблица 2 – Разложение СММ N = 2501 на подмодели ЦМС с перестроением ЦМС Н-25

Один из видов исследования, обработки модели числа – это разложение модели на подмодели. (см. табл. 2). Подмодели – это тоже модели (представляются таблицами строк), но меньших размеров. Все подмодели в объединении их элементов (строк) образуют исходную СМ-модель. Основной признак подмодели – цикличность порождения ее строк. Здесь уместно заметить, что цикл в подмодели можно начинать с любой строки, подмодель для удобства перестраивается.

В связи с этим свойством выбрано название подмоделей: циклическое множество строк (ЦМС). К подмоделям обычно предъявляются требования: разделение по подмоделям множества строк СММ на кратные делителям (d_m и d_б) и некратные (ЦМС Нi); в свою очередь, желательно разделять строки кратные разным (М – малым и Б – большим) делителям (ЦМСМi) и (ЦМСБi), i – указатель строки порождения. Таблицы подмоделей желательно иметь небольшого объема, т.е. множества строк большой мощности представлять несколькими подмоделями, желательно одинакового размера.

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

В подмоделях можно ограничиваться длиной строки, т.е. элементами только из первых 4-х
столбцов. Остальные элементы строк легко восстанавливаются при необходимости. 

Перечень подмоделей

Для подмодели строк, кратных большему делителю, получаем таблицу ЦМС Б11(одна строка). Начнем с подмоделей некратных строк модели, затем получим подмодели кратных для меньшего делителя строк, и завершим подмоделью кратных большего делителя.

Подмодель строк кратных d_б

Выписываем начальную (порождающую) строку первой подмодели некратных строк (Шаг1, ЦМС Н1, хо =1, t = 31). В специальный массив S включаем номер верхней строки S = {1}, в другой специальный массив InId ={Ø} включаем переменную а² (mod N) = а или 1 с указанием номера шага, на котором получены инволюции (In) и (Id) идемпотенты.

Этот массив обеспечивает и установление делителей N. Для нахождения корней квадратичного сравнения желательно перестроить ЦМС, содержащую строку нетривиальных инволюций не первой по порядку. (в примере перестроенная ЦМС Н5 некратных строк).  На Шаге 2 разность
t =31 нечетное число верхней строки помещаем в соответствующую позицию новой (формируемой) строки х1= t = 31, помещаем 31 в позицию х1 новой строки.

По-другому, на Шаге 2 в массив S1 включаем S1 = {1, 2}. Х1 и Хо верхней строки удваиваются: Х1 = 64 и Хо = 2, но 64 >33, поэтому значение 64 приводим по модулю N =33, Х1= 64 (mod N)=31, а номер строки Хо =2. На шаге 3 в массив S1 включаем S1 = {1, 2, 4}, Хо = 3 пропущено. Новую подмодель начнем с пропущенной Хо = 3. Так формируем строку за строкой подмодели, пока в некоторой строке t не станет равным Хо первой строки. В подмодели ЦМС Н1 это случилось на шаге 5, t = 1.

Если продолжать, то строки начнут повторяться в цикле. Завершается цикл Шагом 5, c S1 ={1, 2, 4, 8, 16} и InId ={Ø}. На каждом шаге определяется меньшее из чисел строки, сравнивается, с ранее включенными в массив, и включается в массив S1, если оно там отсутствовало.

Вторая подмодель начинается Шагом 6, на котором анализируется массив S1 и определяется меньшее число, отсутствующее в нем: 1-есть, 2-есть, а 3-нет, так как после 2 следует 4, поэтому начинаем формировать ЦМС М3, т.е. первая строка новой подмодели содержит Хо = 3, так как в специальном массиве S1 этого числа нет и оно наименьшее из отсутствующих, а t = Х1 – Хо = 30 – 3 = 27 Завершается цикл подмодели два Шагом 10, c S2 = {1, 2, 3, 4, 6, 8, 9, 12, 15, 16} и InId = {Ø}. Заметим, что все числа этой подмодели кратны 3. Это возможно только для кратных строк СММ.

Следующая третья подмодель ЦМС Н5 начинается Шагом 11. Из анализа массива S2 подмодель должна начинаться строкой, содержащей в позиции Хо = 5 (число 5 в S2 пропущено), а Х1 = 28 и t = N – 2Хо = 33 – 10 = 23. Если в массиве InId для элемента (1, шаг12) шаг не кратен числу строк в подмодели некратных строк, то подмодель перестраиваем, делая верхней строкой строку нетривиальных инволюций.

Перестроенная подмодель (перестроена  ЦМС Н5 некратных строк) следует за исходной неперестроенной подмоделью. Рассмотренные действия обеспечивают нахождение нетривиальных инволюций и идемпотентов в процессе разложения СММ на подмодели.

Для решения ЗФБЧ важно определить к какому из трех типов относится число, подвергающееся обработке. При этом важное значение имеет удаленность между делителями числа. На практике в подавляющем большинстве случаев мы априори этого знать не можем.

Известно, что значение модуля N в RSA-подобных шифрах задается разрядностью делителей N, его длина сопоставима с суммой разрядности делителей, а длины делителей – это √N. Удаленность делителей одного от другого имеет разрядность сопоставимую с делителями. Это условие позволяет отнести модули N шифра к типу 2. Ниже рассмотрим факторизацию чисел N, относящихся к разным типам.

Как определить тип числа N вне СМ-модели неизвестно, а в рамках СМ-модели на основе анализа области ТКВК (ее размер√N). Проверяются строки ТКВК на содержание r_ссс и определяется их номер.

Пример 4.
В СММ для N = 1961 мы устанавливаем строку хо = 4, содержащую r_ссс = 506 = 22×23 и вычисляем делители. Найденные делители суммируем t = t1 + tо = 23 + 22 = 45. По значению
t = 45 находим хо = ½(N – t) = ½(1961 – 45) = 958 номер строки с таким t = 45. После этого вычисляем КВВ (он должен быть КВК, т.е. квадратом), 958²(mod N) = 16 = 4². Другими словами, мы нашли центр решающего интервала (ЦРИ) и соответствующий квадрат, по ЗРД находим границы РИ и делители N с привлечением НОД
Гл = 958 – 4 = 954 = 18×53, где  d_б = 53;
Гп = 958 + 4 = 962 = 26×37, где d_m = 37.
Пример 5.
В СММ для N = 1963 мы устанавливаем строку хо = 41, содержащую r_ссс = 1190 = 34×35 и вычисляем делители. Найденные делители суммируем t = t1 + tо = 35 + 34 = 69. По значению
t = 69 находим хо = ½(N – t) = ½(1963 – 69) = 947 номер строки с таким t = 69. После этого вычисляем КВВ(он должен быть КВК, т.е. квадратом), 947²(mod N) = 1681 = 41². Другими словами, мы нашли центр решающего интервала (ЦРИ) и соответствующий квадрат, по ЗРД находим границы РИ и делители N с привлечением НОД
Гл = 947 – 41 = 906 = 6×151, где  d_б = 151;
Гп = 947 + 41 = 988 = 76×13, где d_m = 13.
 
В последнем примере N = 1969 мы не можем воспользоваться строкой с r_ссс в области ТКВК, так как там такая строка просто отсутствует. Поэтому вынуждены воспользоваться ЗРД, ЦРИ фрагментов НРЧ, задаваемых составными числами N всегда характеризуются КВВ полными квадратами.

Пример 6.
В СММ для N = 1969 мы устанавливаем в списке строку хо = 139, содержащую полный квадрат КВК= r_л = 1600 = 40×40 и вычисляем квадратный корень из √ r_л = 40. Найденное значение соответствует ЦРИ с хо = 139. Другими словами, мы нашли центр решающего интервала (ЦРИ) и соответствующий ему квадрат, по ЗРД находим границы РИ и делители N с привлечением НОД
Гл = 139 – 40 = 99 = 9×11, где  d_m = 11;
Гп = 139 + 40 = 179 = 179×1, где d_б = 179.

Заключение

Установление строк с левыми вычетами (КВК = r_л) и средними вычетами (r_ссс) СМ-модели в области ТКВК обеспечивают нахождение решения ЗФБЧ (факторизацию N). Поиск таких строк осуществляется для чисел 1-го и 2-го типов только в области ТКВК.

Обнаруженные значения r_ссс = t1× tо раскладываются в смежные сомножители, которые после определения преобразуются в разность t = х1 – хо = t1 + tо суммированием.
Эта разность соответствует строке из тривиальной области ТССС, левый вычет которой КВК полный квадрат, а номер строки хоц = ½(N – t) определяется по найденной разности.

По закону распределения делителей эта строка ЦРИ, а границы РИ кратны разным делителям и определяются зависимостями Гл,п = хоц±√r_л.