Модель натурального числа. Часть I

Теоремы существования и теоремы перечисления. Модели

Ограниченность научных, теоретических знаний тормозит научное и общественное развитие.
Взять закон распределения простых чисел (ЗРПЧ) или ту же основную теорему арифметики (ОТА). Да, они фундаментальны, но что ОТА утверждает?

Это всего лишь (как и ЗРПЧ) теорема существования, для любого числа N существует произведение степеней простых чисел, которое единственно и равно этому числу N. Как получить и увидеть отдельные делители N в теореме не говорится. Аналогично и с простыми числами. Сами числа (большие и очень большие) получать умеем только квазипростыми.

Но известно, что не менее фундаментальной является и проблема (теорема) перечисления. Начиная с древних греков (решето Эратосфена), делались и продолжаются попытки решить задачу перечисления – вторую часть или другую половину основной теоремы арифметики, и что? А пока весьма скромно, для больших чисел практически ничего! Надо просто видеть, понимать ситуацию и владеть процедурой быстрой факторизации чисел.

Более того, большинство и других основных теорем теории чисел – теоремы существования. Чтобы воспользоваться многими теоремами относительно простых или составных чисел N необходимо располагать разложением этого числа на делители. А этого-то мы и не умеем!
Где же ответ? Где ключевые направления для получения положительных решений?

Материал публикации представляется весьма обширным, поэтому для удобства ознакомления с ним разбивается на две части.

Предварительные результаты, необходимые для разработки модели числа

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

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

Упование на молекулярные, квантовые компьютеры с сумасшедшим быстродействием и распараллеливанием алгоритмов подтверждают мысль об использовании и на новых компьютерах тех же переборных алгоритмов. О причинах сложившейся ситуации я уже писал на Хабре и на повторение своего мнения не хотелось бы тратить время и место.

С учетом аудитории (надежда попасть на «крутых» спецов) и возможностей «Habra» (публикации в научных журналах не комментируются, что свойственно Хабру, журнальные рецензенты не в счет, это вопрос везения) в каждой публикации (в том числе и в рецензируемых журналах из списка ВАК) автору удается лишь в ограниченном объеме излагать отдельные новые оригинальные идеи подхода. Замечу, что нынешний рынок публикаций опубликует за деньги где хотите и что хотите — нынче и академический журнал не панацея для истины.

Но для заинтересованных лиц в публикациях автора (часто с минусовыми оценками, новое чаще принимается «в штыки», чем одобряется) можно более подробно ознакомиться с рядом результатов. Перечислю лишь некоторые: Закон распределения делителей (ЗРД здесь) числа, основная теорема факторизации (ОТФ здесь), необычное, независящее от разрядности, установленное новое свойство чисел (ф-инвариант нечетного числа здесь) и еще множество других деталей рассматриваемого подхода.

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

Известно крылатое выражение «электрон неисчерпаем», могу здесь его переиначить «Натуральный ряд чисел загадочен и неисчерпаем». Какой объект из двух менее изучен наукой сказать не берусь. Обнадеживают мои скромные усилия, те люди, которые (даже при наличии минусовых оценок на Хабре) в копиях публикуют на своих сайтах научные результаты моих публикаций и дают на них ссылки своим читателям.

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

В результате такой работы могут обнаружиться некоторые новые закономерности, то есть появляется возможность связать один ряд фактов с другим или сопоставить появление какого-то типа поведения с действием определенного ряда влияний. Такая связь в дальнейшем может быть сформулирована в виде обобщения или «закона природы».

Например, публикация в 2010 г Арнольда В.И. «Случайны ли квадратичные вычеты?» обратила более пристальное внимание на этот объект, поскольку я был убежден в его неслучайности, детерминированности, а сомнения в этом академика РАН от математики для меня было просто удивительным.

В рамках фрагмента НРЧ, определяемого значением N, ряд при его формировании как бы самостоятельно определяет в какой позиции, что нужно вписать, где полный квадрат, а где другое значение. Более правильным вопросом относительно квадратичных вычетов (КВВ) мог бы быть: «Почему они так распределены, почему так происходит?»

Поиск причин конкретных распределений квадратичных вычетов в конечных числовых кольцах вычетов (КЧКВ) по составному модулю N, и в частности, квадратичных вычетов полных квадратов (КВК) привел к формулированию нового в теории чисел «Закона распределения делителей числа в НРЧ».

Оказалось, что распределением, т. е. положением КВК в НРЧ естественным образом управляют делители составного модуля N, о значениях которых у нас нет никаких сведений, а у ряда натуральных чисел получается — есть. В нужной позиции ряд ставит кратное одному из делителей, на нужном удалении от него ставит полный квадрат и на таком же удалении дальше ставит кратное другому делителю. Есть чему удивиться!

Законом вскрывается причинно-следственная связь положения в НРЧ делителей, их кратных и квадратичных вычетов-полных квадратов по модулю N.

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

Долгое время оставалось загадкой, почему так происходит. Математики это видели всегда, но проходили мимо, не обращая внимания на сам факт, не удивлялись этому, не задавались вопросом и не искали разгадки. А академик РАН Арнольд В.И. вопрос себе задал, выполнил исследование и позднее опубликовал его.

Именно КВК несут в себе (содержат) информацию о делителях числа N (выполняют роль обнаружителей, детекторов делителей), и они вычисляются элементарными операциями. Так был открыт новый закон в теории чисел. Он мог быть открыт и раньше, но публикация, надоумившая меня серьезно заняться этим вопросом случайно попалась мне на глаза лишь в 2014 году.
Закон распределения делителей числа обнаруживает, устанавливает их положение (позицию, место) в НРЧ и обеспечивает их перечисление для заданного составного числа N.

Модель отдельного нечетного числа

В рамках любой строгой теории обычно рассматриваются математические задачи и соответственно математические методы их решения, основные объекты и процессы таких задач моделируются на ЭВМ. Это удобно, особенно если требуются обширные вычисления.

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

В теории чисел значительное место отводится проблеме факторизации. Теорема факторизации устанавливает необходимость рассмотрения числового множества, ограниченного лишь подмножеством составных нечетных натуральных чисел (СННЧ) определенного вида (здесь), что является и достаточным для решения задачи факторизации. Это ограничение существенно упрощает проблему моделирования основного объекта (числа), но все ещё не делает ее простой.

Кроме модели числа важно располагать и более объемлющей моделью, в которой сами числа являются всего лишь отдельными элементами. Таким объемлющим числа объектом рассматривается НРЧ, модели которого также создаются, синтезируются в предлагаемом новом подходе к проблеме факторизации. Это линейная модель (обычный НРЧ), плоскостные: контурная модель-спираль Улама (полная) и квадратичная Г^2±– модель (модель усеченного НРЧ). (здесь)

В этой публикации начнем рассмотрение моделей отдельного числа, которые могут быть аддитивными или мультипликативными. В каждой из названных моделей НРЧ элементами выступают отдельные числа: в линейной – это индекс позиции регистрового разряда, в котором помещается число, в контурной модели – нечетное число – полуконтур (левый или правый) с множеством свойств, в квадратичной Г^2±– модели число представляется разностью\суммой квадратов (целочисленными точками гиперболы, окружности) N=x1²±xo².

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

Обоснование выбора списковой многострочной модели (СММ) числа

В статье предлагается концепция линейной алгебраической модели числа N, с погружением ее в множество подобных, представляемой многострочной таблицей. Модель достаточно простая. Будем представлять СННЧ N разбиением на две части N=x1+x0 всеми возможными способами. Отдельное разбиение — уже частная модель N.

Очевидно, таких способов представления числа N существует ½ (N – 1), при этом каждая сумма размещается в отдельной строке таблицы модели. Переменная x0 пробегает все строки от 1 до
½ (N – 1), т. е. играет роль текущего номера строки СМ-модели, который может совпадать в некоторой строке с конкретным делителем N и его кратными (см. табл.1).

Таблица 1 — фрагмент СМ- модели

Обоснование выбора такой модели следующее. В линейной модели НРЧ присутствуют все числа без пропусков, что позволяет задать любое составное нечетное N = рq в соответствующей позиции. Очевидно, фрагмент НРЧ от 1 до N = рq, где р и q – простые числа (≠ 2), содержит следующие подряд все числа, среди которых обязательно встретятся р и q и их кратные. Добавив к этому множеству чисел нулевой элемент получим конечное числовое кольцо вычетов (КЧКВ) по составному модулю N.

Если это множество чисел (фрагмент НРЧ) содержит среди элементов делители и кратные им значения, то возникает мысль, нельзя ли «выудить» из таких элементов сами делители р и q. Поставим целью исследования модели числа — «выуживание» делителей из модели. Модель при этом должна сохранить полностью элементы фрагмента НРЧ.

Следовательно, простота, полнота, включение делителей и их кратных, структурность — КЧКВ и гипотеза о возможности „выуживания“ делителей положены в обоснование выбора СМ-модели.

Последовательность натуральных чисел СММ и ее фундаментальное свойство
Последовательность непрерывно следующих натуральных чисел используется в СМ-модели в двух колонках x1 и x0, в которых x0 играет роль текущего номера строки модели до середины исходного списка. Значения х1 = N — хо — дополнения до модуля подряд снизу вверх записываются в строках модели. Для каждого из элементов (номера и дополнения) строки вычисляется rл(x0) и rл(x1) квадратичный вычет по модулю N. Эти КВВ совпадают, что допускает ограничиваться вычислением только одного КВВ для хо.

Последовательность КВВ натуральных чисел СММ и ее фундаментальное свойство
Определение. (ТКВК). Тривиальной областью строк СМ-модели называется начальное множество строк списка, следующих подряд, содержащих в качестве rл (левого КВВ) монотонно возрастающие полные квадраты.
Определение. Границей ТКВК (левый 1-й верхний порог) называется наибольший КВК – полный квадрат, не превышающий составного модуля N, например, для N=34999, граница ТКВК rлmax ≡ √N (mod N) =√34999 = 187.
Извлекаемые квадратные корни округляются до целых значений.

Для малых значений x0 редукция по N не меняет значений rл (x0) и строки, содержащие такие неизменяемые левые вычеты, всегда образуют для различных N область тривиальных КВК, обозначаемую ТКВК. Граница этой области называется левым верхним первым порогом, а ее значение вычисляется, например, для N=1961, как x0в1= √N=√1961=44,28, округляется до 44.

Полные квадраты из ТКВК области не используются ЗРД (для них не выполнено условие х²>N) и они не используются в процедуре факторизации. При движении вниз по строкам таблицы за пределами порога КВВ (x0>44) превышают модуль и редуцирование уменьшает значения. В некоторых строках при этом получаются дубли из ТКВК и они (и только они) используются для решения задачи факторизации больших чисел (ЗФБЧ) в рамках ЗРД .

Итак, последовательность (фрагмент НРЧ) содержит делители N и их кратные; она начинается тривиальной ТКВК областью; некоторым значениям хо в дублях строк соответствуют КВВ — полные квадраты.

Последовательность нечетных чисел СММ и ее фундаментальное свойство
В предлагаемой модели возникают последовательности нечетных чисел Т и Тп. Они играют существенную роль и на этом явлении остановимся подробнее. Ряды нечетных чисел (колонки 4 и 7) в таблице СММ встречно направлены, но состав их и структура идентичны
Т, Тп = {ti, i = 1(1)½(N-1), ti =1(2) N-2}.

Они в НРЧ образуют бесконечную непрерывную последовательность нечетных значений, (но в примерах ограничены значениями от 1 до N – 2). Каждый элемент t такого ряда (последовательности) будем представлять суммой смежных чисел t=t1+t0, где значение tо=t1-1. Слагаемые t1+t0 будем перемножать друг на друга р(t)=t1·t0. Обозначим редуцированное произведение символом rc (t) =¼(t² -1) и назовем средним вычетом. Оказывается, такие произведения обладают рядом замечательных свойств.

Во-первых, произведения таковы, что их флексии принимают только три четных значения {0, 2, 6}. Флексии в нечетных рядах чисел идут пятерками строк, которые следуют в порядке 02620 (табл. 1) и повторяются периодически до бесконечности.

Во-вторых, значения произведения р(t) с ростом ti возрастают, но в рамках модели редуцируются при превышении модуля N. Произведения меньшие модуля при редукциях остаются без изменений, и обладают свойством сохранять смежность сомножителей (ССС).

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

Определение. Границей ТССС (средний 1-й нижний порог) называется наибольший КВК без первой степени квадрата, например, для N =34999, граница ТССС
rсmax ≡ (хо² -хо) (mod N) =1872 -187 = 34782.

Таким образом, множество строк, в которых ti следуют подряд и их произведения обладают свойством ССС называется тривиальной областью и обозначается ТССС (заливка в колонке 6 зеленый цвет).

Граница этой области называется нижним средним первым порогом, а ее значение вычисляется как 1892 = 44² – 44, где значение 44=√N=√1961≈44,2. В СММ (табл.1) в колонке 6 размещены строки ТССС средние вычеты rc(t) в строках с номерами хо = 937 по хо = 980 – элементы rc(t), принадлежащие ТССС.

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

Итак, последовательность нечетных чисел t завершается тривиальной ТССС областью (колонка 6); некоторым значениям хо в дублях строк этой области соответствуют КВВ-полные квадраты, что свидетельствует о непустом пересечении двух нетривиальных областей ТКВК∩ТССС≠∅

Пример 1. (Редуцированные значения со свойством ССС). Пусть в СММ (см табл.1) задано
N = 1961 = рq и значение t=t1+t0 = 45 = 22 + 23. Находим значение произведения смежных слагаемых р(t) = 22·23 = 506. Результат не превышает модуля 506 <1961, следовательно, редукция оставляет результат без изменения, т.е. rс(р) = р(mod N) = 506(mod 1961)= 506.
Флексия 506(mod10)=6 ∊{0, 2, 6} говорит о выполнимости свойства rс(р) ССС.

Изменим t = t1 + t0 = 89 = 44 + 45. Находим значение произведения смежных слагаемых
р(t) = 44·45 = 1980. Результат превышает модуль 1980 >1961, следовательно, требуется редукция, уменьшающая результат произведения, т.е. rс(р) = р(mod N) =1980(mod 1961)= 19.
Флексия результата 19(mod10)=9 ∉{0, 2, 6} показывает, что свойство rс(р) ССС не выполняется.

Рассмотрим явления, происходящие при моделировании отдельного числа N, в рамках СМ-модели. Удобно это сделать на числовом примере, сопровождаемом комментариями. Выбор числа сделаем таким, чтобы исключить простое угадывание делителей. Здесь ограничимся лишь строками нижней части основной таблицы СМ-модели, хотя и не столь малого объема.

Пример 2. Задано число N = 1961 = рq, которое подвергнем факторизации. Для этого воспользуемся оригинальной СМ-моделью (см. табл.1) и определим (заполнены) полные верхнюю
rл(1) = 1, х1=1960, хо =1, t=1959, rс(1) = 491, tп = 1, rп(1) = N – rл(1) = 1961 – 1 = 1960 и нижнюю
rл(0) = 1471, х1=981, хо =980, t=1, rс(0) = 0, tп = 1959, rп(0) = N – rл(0) = 1961 –1471 = 490, строки СММ а также остальные элементы в области ТССС и в других строках. Дело в том, что свойства модели допускают заполнение всех полей строк основной таблицы ручным способом, даже не прибегая к использованию компьютерной программы.

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

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

Теперь можно в деталях описать фрагмент модели числа (таблицы 1).
Описание фрагмента таблицы СМ-модели отдельного числа. Полная таблица строк СММ для N = 1961 содержит 980 строк и 8 столбцов (левый столбец примечаний не обязателен). Предварительно заполним поля столбцов t, tп, верхнюю и нижнюю строки СМ-модели. Строки нумеруются подряд сверху вниз хо до середины списка (нижняя „нулевая“ строка р = rc=0) и далее продолжение х1 снизу вверх в колонке слева (слева от хо = 980 стоит х1 = 981).

Строки имеют типовую начинку: левый квадратичный вычет rл(хо), номер хо строки, х1 – дополнение номера до N, разность t=х1–хо пробегает монотонно убывающие нечетные значения от N – 2 до 1, произведение р(t)=t1tо= ¼·(t² – 1), средний вычет rс(р) = р(mod N), tп – нечетные числа от 1 до N – 2, правый вычет произведения rп(хо) = хо·х1 (mod N) = N – rл(хо). Кратными будем называть строки, номера которых кратны делителям N.

Из полного списка строк приводимый фрагмент (табл.1) включает лишь 57 строк: первую, 901-ю, и все с 925-й по 980-ю строки. Заливкой выделены пары строк: номера хо = 901 и хо = 954 которых кратны большему делителю (оранжевый цвет); номера хо = 925 и хо = 962 которых кратны меньшему делителю (зеленый цвет); номера хо = 958 и хо = 966 строк, содержащих квадратичные вычеты КВК– полные квадраты (синий цвет).

Следовательно, оранжевые и зеленые строки кратные. В таблице замкнутый интервал строк между ближайшей парой кратных строк разного цвета хо = 954 и хо = 962 содержит 9 строк, средняя с номером хоц = ½(954 + 962) = 958 строка.

В соответствии с законом распределения делителей числа в этой хоц точке КВВ должен быть полным квадратом удаленности (в числе строк) от нее кратных строк (точек) с разным цветом заливки. Действительно, строки хо = 954 (оранжевая) и хо = 962 (зеленая) удалены от центральной хоц = 958 обе на 4 позиции (строки) каждая.

Более поучительный случай (синяя) строка, имеющая номер хоц = 966. Поскольку вычисление КВВ в этой точке дает результат
rл(хоц) = хоц (t)²(mod N) = 966²(mod1961) = 41² равный полному квадрату (41²), то эта точка (по ЗРД) должна быть центром замкнутого интервала с нечетным числом строк в нем 83 = 2·41+ 1.

Удаленность (41 позиция) обеих границ интервала от центра. Действительно, такая пара строк (заливкой разного цвета) с номерами кратными делителям N, существует. Это строки с номерами хо = 925 (зеленая) и хо = 1007 (оранжевая). Удаленность границ равна разности
1007– 966 = 966– 925 = 41. Длина замкнутого интервала 83 = 2·41+ 1.

Наличие таких строк (даже одной синей из них) делает допустимым на основе ЗРД быстрое и успешное завершение ЗФБЧ. В соответствии с законом распределения делителей числа N в НРЧ в установленных строках определяются значения их текущих номеров. Это номера (точки хо) тех строк, в которых КВК порождаются самим рядом.

Далее, следуя пунктам алгоритма (ниже) вычисления значений делителей р и q, находятся и сами делители. Вообще подряд все строки восстанавливать не обязательно, хотя и полезно для понимания и обучения. Важно уметь оперативно получать те из них, в которых КВВ полные квадраты.

Установление таких строк реализуется элементарными действиями над элементами СМ-модели. В приведенном фрагменте таблицы СММ такими строками являются строки с номерами хо = 958 и хо = 966 (выделены заливкой синего цвета).

Каким образом получаются окончательные решения, т. е. как вычисляются делители N?
На самом деле кратные делителям правая и левая границы Гп, Гл замкнутых симметричных относительно центров интервалов с нечетным числом строк неизвестны, так как неизвестны ни делители N, ни коэффициенты кратности номеров строк-границ.

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

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

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

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

При установленных в примере значениях таких квадратов (КВВ 16 и 1681) и точек хоц= 958, хоц= 966, в которых они получены возможно (обратная задача) построение замкнутого интервала с определением его границ Гп, Гл = хоц ± √(rл )= 958 ± 4 = 962, 954, а также
Гп, Гл = хоц ± √(rл )= 966 ± 41 = 1007, 925.

Для окончательного получения значений делителей используется алгоритм Евклида наибольшего общего делителя НОД. Для первого случая, строка
хоц= 958 (синяя) и rл(хоц) =16 =4² имеем результат
di = НОД(N, Гi ) = НОД (1961, 962) = 37; di = НОД(N, Гi ) = НОД (1961, 954) = 53.

Для второго случая, строка с номером хоц = 966 (синяя) и КВК rл(хоц) =1681 = 41² имеем результат
di = НОД(N, Гi ) = НОД (1961, 925) = 37; di = НОД(N, Гi ) = НОД (1961, 1007) = 53.

Для обеих строк с КВК найдены по два делителя, и они одинаковы в обоих случаях, это свидетельствует о том, что для фактического решения достаточно даже одной строки (синей), в которой установлен (найден, вычислен) КВК.

Продолжим обоснование полученных результатов

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

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

Другая особенность СМ-модели состоит в замечательном свойстве самой модели. Вне модели воспользоваться свойством не удается. Оказывается, левый квадратичный вычет, может вычисляться не только через квадратичное сравнение. Он может представляться суммой левого квадратичного вычета нижней строки модели rл(0) и текущего среднего вычета строки. Используется и это свойство КВВ в СМ-модели: rл(хоц) = rл(0) + rс(хоц) = 1471 + 506 = 1977.

Выбор среднего вычета 506 специально сделан таким, чтобы сумма его с rл(0) превысила N.
Поскольку найденное значение превышает модуль N = 1961, то его следует редуцировать, т. е. привести по N модулю rл(хоц) = rл(0)+rс(хоц) (mod1961) = 1977 – 1961=16 = 4². Редукция суммы при этом равна разности, что для rл(хоц) ожидаемо как малое значение (получили квадрат =16).

Если бы был получен не квадрат, то выполняется переход в следующую строку и действия повторяются до тех пор, пока не возникнет квадрат, а его возникновение гарантируется. Поясним откуда взялось значение rс(хоц) = 506? Это достаточно простой трюк.

Среди прочих отыскивается наименьший средний вычет rс(хоц), который при суммировании его с КВВ нижней строки модели превысил бы значение модуля N. Само значение rс(хоц) = 506 получено из t – нечетного числа, rс(t) до определенной границы (порога) не зависит от N. Для некоторых значений t их отображение р(t) = rс(t) = t1·tо обратимо, т. е. по значению rс(t) можно восстановить t = р(р(t))^-1=р(rс(t))^-1.

Далее, для любых N набор rс(хо) одинаков до определенного предела (порога, зависящего от N). Зная значение rс(t) = 506, найдем и значение t. Извлекаем квадратный корень и округляем до меньшего целого t1 = √506 = 22,49, тогда значение tо= t1+1 и t = t1 + tо.
Фактически получены значения tо = 23, t1 = 22 их сумма t = t1 + tо =22 + 23 = 45. По значению t можно восстановить все элементы строки, в которой оно лежит.

Поиск центра интервала. Нам требуется определить точку хоц центра замкнутого интервала, в которой КВВ полный квадрат. Еще одно свойство СМ-модели обеспечивает решение и этой задачи. Свойство реализуется достаточно простой формулой
хоц(t) = ½(N – t) = ½(1961 – 45) = 958. Итак, центр найден хоц(t) = 958.

Проверим, действительно ли, в этой точке КВК rл(хоц) = 16.
rл(хоц) = хоц (t)²(mod N) = 958²(mod1961) = 917764(1961) = 4²+ 468·1961 = 16+ 0 = 16 =4².
Поиск границ интервала. При наличии центральной точки интервала и КВК в ней границы интервала находятся по зависимостям ЗРД Гп, Гл = хоц ± √(rл(хоц)).

Алгоритм решения ЗФБЧ с учетом области ТКВК

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

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

Универсальный быстродействующий алгоритм до настоящего времени не найден. В работе, представленной читателям, к рассмотрению предлагается алгоритм, устраняющий большинство ограничений существующих известных алгоритмов, главное из которых- зависимость от разрядности ключа.

В алгоритме задается составное число N = рq = dm·dб где р и q – простые числа высокой разрядности. Для удобства изложения при описании воспользуемся числовым примером, в котором р и q – простые числа не очень высокой разрядности, что позволит без больших усилий воспринимать текст и понимать (проверять на калькуляторе) практически все результаты промежуточные и окончательные.

Задача 3. Пусть задано составное число N = рq = 2501, необходимо найти его делители р и q. Предварительно находим пороги ТКВК хов1 = √N=√2501= 50,0099, ТССС хон1=1201, rсн1(t) = 2450.

Пример реализации алгоритма

1. Заполняется первая строка. Левый, средний и правый вычеты rл(1)=1, rс(1) = 626, rп(1)=2500.
х1 = 2500, хо = 1, t = N – 2 = 2501 – 2 = 2499, tп = 1.
В последней строке СММ rл(0) = 1251 + 625 = 1876, смежные значения х1 + хо = N = 2501,
х1 = 1251, хо = 1250, разность t = х1 – хо = 1, rс(t =1) = 0, tп = N – 2, rп(0) = 625.

2. Определяем циклически в области ТКВК номер строки меньшего среднего вычета со свойством ССС (из перебора исключаются все строки до верхнего 1-го порога среднего вычета) хо = √N=√1876=43,3 квадрат этого значения (округление в меньшую сторону) дает для
rс(хо) = 625 + 43² = 2474, это меньше 1-го порога равного 2501.

Повторяем цикл, увеличиваем еще на единицу номер строки хо = 43 +1 = 44.
Следующее значение rс(хо) = 625 + 44² – 2501= 2561 – 2501 = 60 превышает порог на 60. Значение rс(хо) не соответствует ССС. Увеличиваем еще на единицу номер строки хо = 45, тогда
rс(хо) = 625 + 45² – 2501 = 2650 – 2501 = 149.

Значение rс(хо) превышает порог, но также не соответствует свойству ССС.
Увеличиваем еще на единицу номер строки хо = 46. Тогда средний вычет имеет свойство ССС
rс(хо) = 625 + 46² – 2501= 2741 – 2501 = 240 = 15·16.

3. Вычисляем значение разности t = x1 -xо (нечетного t в области ТССС) t = 15 + 16 = 31.
4. Определяем для этого t номер центральной строки хоц (t) = ½(N – t) = ½ (2501–31) = 1235.
5. Находим для хоц (t) квадратичный вычет центральной строки замкнутого интервала.
rл(хо)=хо (t)²(mod N) =1235²(mod2501) = 46² — КВК.

6. Вычисляем делители с использованием НОД
dб = НОД(N, 46+1235) = 61; dm = НОД(N, 1235 – 46) = 41.
7. Проверка N = рq = 41·61 =2501. Делители N успешно найдены.

Задача может решаться иначе:

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

Задано составное число N = рq = 2501, необходимо найти его делители р и q. Предварительно находим пороги ТКВК хов1 = √N=√2501= 50,0099, ТССС хон1=1201, rсн1(t) = 2450.

Первая строка. Левый, средний и правый вычеты rл(1) = 1, rс(1) = 626, rп(1) = 2500.
х1 = 2500, хо = 1, t = N – 2 = 2501 – 2 = 2499, tп = 1.
В последней строке Вычисляем сумму и разность смежных слагаемых N = 1250 +1251,
rл(0) = 1251 + 625 = 1876, смежные значения х1 + хо = N = 2501, х1 = 1251, хо = 1250, разность
t = х1 – хо = 1, rс(t =1) = 0, tп =N – 2, rп(0) = 625.

В цикле по хо от хо = 1 вычисляем rс(хо) и проверяем его принадлежность области ТССС. Если rс(хо) принадлежит ТССС, то переходим к П.3 алгоритма, если не принадлежит, то увеличиваем значение
хо= хо +1 и повторяем действия цикла.

На пятом шаге хо = 5 получаем значение t =N -2xо = 2501 -10 =2491,
rс(хо =5) =¼(t² — 1)(modN) =650. Флексия 650(mod10)=0 ∊{0, 2, 6} говорит о том, что средний вычет может иметь свойство ССС. Устанавливаем из смежных ли чисел образовано произведение равное 650? Извлекаем квадратный корень
t0=√650 =25,49 округляем до t0=25, t1 = t0+1 = 25+1=26.
Находим произведение р(t) = 25·26= 650, редуцированный вычет принадлежит ТССС.
Вычисляем значение нечетного t в области ТССС t = 25 + 26 = 51.

Определяем для этого t номер строки хоц (t) = ½ (N – t) = ½ (2501 – 51) = 1225.
Находим для хоц (t) квадратичный вычет (левый в СММ)
rл(хо) = хо (t)²(mod N) =1225²(mod2501) = 5².

Вычисляем делители с использованием НОД
dб = НОД(N, 5+1225) = 41; dm = НОД(N, 1225 – 5) = 61.

Проверка N = рq = 41·61 = 2501. Такая схема также приводит к успешному решению.