Модель числа что это

Одним из разделов аддитивной теории чисел является исследование суммирования последовательностей. Важной является ситуация, когда в результате суммирования ограниченного числа последовательностей, получаются все достаточно большие числа или другой вариант — все натуральные числа, что в сущности эквивалентно моделированию НРЧ.
В теории вводится понятие базиса k-го порядка, под которым понимают многократную (k-кратную) сумму последовательности П с собой k раз и при этом формируются все натуральные числа. Дальнейшее суммирование последовательности П к предыдущему результату k = k + 1-й раз не меняет полученный базис.

Так, например, известна теорема Лагранжа о том, что любое натуральное число есть сумма четырех квадратов. Таким образом, последовательность квадратов Q есть базис 4-го порядка [1]. Известно [2, 3], что последовательность кубов образует базис 9-го порядка. Последний результат доказывается более сложным путем.

Усеченные модели НРЧ (не все натуральные числа присутствуют в модели), в которых обязательно присутствие лишь достаточно больших чисел, получаются при меньшем числе слагаемых последовательностей. Так из теоремы И.М. Виноградова [1] следует, что достаточно трижды просуммировать последовательность Р + Р + Р, где Р — последовательность простых чисел и эта сумма будет содержать все достаточно большие нечетные числа. Таким образом, последовательность Р образует базис 4-го порядка для достаточно больших чисел. Последовательность кубов в этой ситуации образует базис базис 7-го порядка для достаточно больших чисел. Таковы в общем результаты строгой теории чисел.

Мы при изложении материала не будем прибегать к строгим доказательствам, в части положений они пока отсутствуют, а где имеются занимают много места

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

Ранее было показано, что использование геометрической (плоскостной) модели натурального ряда чисел в форме–плоскости позволяет формулировать задачу факторизации больших чисел (ЗФБЧ) в терминах и понятиях этой модели и сводить ее по существу к определению координат целой точки гиперболы, характеризуемой модулем сравнения N шифра RSA, который доступен всем абонентам сети. Использование другого доступного ключевого параметра (показателя шифрующей экспоненты е), найденных факторов и модуля обеспечивает простое вычисление закрытого ключа шифра d и доступ к исходному виду сообщения.

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

Сформулируем ряд положений для обоснования выбора рассматриваемой модели:

Конструктивное описание Г 2∓ модели

_{Визуальное представление модели}

Равнобочная гипербола N = x1 2 – x0 2	Г и К – полуплоскости и гипербола

Элементами модели являются клетки (аналог точки плоскости), прямые линии (совокупности клеток-точек, примыкающих одной из сторон или вершиной, одна к другой) горизонтальные (Н_i), вертикальные (V_i), наклонные (совокупности примыкающих вершинами клеток-точек или клетками без контакта, формирующих направление линий с разрывами — лучей): длинные (Д_i) и короткие (К_i) диагонали, которые содержат либо только четные значения и при этом называются четными, либо нечетными диагоналями, образованными нечетными клетками. Короткие диагонали заканчиваются и начинаются в точках координатных осей с совпадающими координатами (номерами диагоналей). Длинные диагонали (Д_i) проходят параллельно главной (с номером (Д₀)) имеют только начальные точки на координатных осях и продолжаются вниз до ∞. Их положение выше и ниже (Д₀) характеризуется совпадающими номерами и для их различения диагонали верхней полуплоскости снабжаются дополнительным (+) значком (Д_i + ). Нечетная диагональ (Д₁ + ) начинается на оси х₀ клеткой с 1 и содержит в своих клетках нечетные числа. Нечетная диагональ Д₁ начинается на оси х₁ клеткой с N=1 и содержит все без исключения нечетные числа, упорядоченные по возрастанию. Тем самым обеспечивается требование к модели НРЧ содержать все нечетные числа.

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

Зависимости чисел в организованных клетках

Под организацией клеток будем понимать принадлежность некоторых (семантически выделенных) клеток некоторому изображению, задаваемому математической зависимостью либо координат, либо значений в клетках, либо того и другого. Свойства получаемых изображений будем использовать для решения теоретико-числовых задач, в частности для ЗФБЧ. Начнем рассмотрение с очень простых изображений прямых линий, лучей. Г 2- — модель обеспечивает их визуализацию.

Пример 1. Рассмотрим нижнюю полуплоскость Г 2- и значения чисел в клетках с координатами (х₁, х₀), где координата х₁ пропорциональна другой х₀ координате х₁ = kх₀, коэффициент пропорциональности изменяется монотонно k = 2,3,4. ∞, что кратко записывается так k=2(1)∞. С изменением координаты х₀ = 0(1)∞, т. е. от нуля до бесконечности с шагом 1 и при фиксированном значении k будут вычисляться клетки и натуральные значения в них, принадлежащие линиям (лучам) с разрывами. Так при k = 2, получаемые клетки располагаются посередине отрезков горизонталей нижней полуплоскости, а линия получает вид луча-биссектрисы (обозначена Б3) нижней полуплоскости. При k = 3 получаемые клетки располагаются посередине отрезков коротких диагоналей нижней полуплоскости, а линия получает вид другого луча-биссектрисы (обозначена Б8) нижней полуплоскости.

Основное свойство таких лучей для ЗФБЧ состоит в том, что числа в клетках лучей определяются одной координатой x₀, т.е. значение N(x₁, x₀) = N(kx₀, x₀) = (kx₀) 2 — x₀ 2 = x₀ 2 (k 2 — 1) в клетке, принадлежащей одному из лучей, становится функцией только одной координаты x₀. Наличие числа N, факта принадлежности его клетке конкретного луча, обеспечивают определение второй координаты и получение решения ЗФБЧ за время долей секунды, которое практически не зависит от разрядности числа. Значение второй координаты находится из соотношения модели луча полуплоскости х₁ = kx₀. Из наличия обеих координат клетки вытекает, что все числа линии в таких клетках факторизуются элементарными действиями и практически мгновенно. Приводимые простые наглядные примеры убеждают нас в этом.

Пример 2. Подтверждение работоспособности модели вычислительным экспериментом. Пусть заданы для факторизации числа N = 968 и N = 507 ∊ Г 2- — модели, и каждое лежит в одной из клеток наклонной прямой, формируемой соотношением при некотором k, например, k = 2 получаем N(x₁, x₀) = x₁ 2 — x₀ 2 = (kx₀) 2 — x₀ 2 = x₀ 2 (k 2 — 1) = 3x₀ 2 = 968.

Для второго числа N = 507 выполняем такие же действия.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В статье предлагается концепция линейной алгебраической модели числа 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 и их кратные; она начинается тривиальной ТКВК областью; некоторым значениям хо в дублях строк соответствуют КВВ — полные квадраты.

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

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

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

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

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

Граница этой области называется нижним средним первым порогом, а ее значение вычисляется как 1892 = 44 2 – 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) =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 2 – 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) 2 (mod N) = 966 2 (mod1961) = 41 2 равный полному квадрату (41 2 ), то эта точка (по ЗРД) должна быть центром замкнутого интервала с нечетным числом строк в нем 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 2 имеем результат
di = НОД(N, Гi ) = НОД (1961, 962) = 37; di = НОД(N, Гi ) = НОД (1961, 954) = 53.

Для второго случая, строка с номером хоц = 966 (синяя) и КВК rл(хоц) =1681 = 41 2 имеем результат
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.

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

Далее, для любых 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.

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

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

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

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

В алгоритме задается составное число 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 2 = 2474, это меньше 1-го порога равного 2501.

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

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

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 и повторяем действия цикла.

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

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

Источник