Русский
Русский
English
Статистика
Реклама

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




Структура конечного кольца вычетов по составному модулю



Формирование работоспособной модели числа оказалось достаточно сложным и объемным процессом, поэтому принято решение разбить его на 2 статьи.
Будем рассматривать натуральный ряд чисел (НРЧ) и считать, что его элементы размещены в ячейках регистра бесконечной длины, для каждого элемента хо которого вычисляется квадрат, помещаемый в ленту другого бесконечного регистра. Если же задать нечетное составное натуральное число (СННЧ) N, то лента с квадратами преобразуется.

В нее будут включены не просто квадраты (хо), а квадратичные вычеты (КВВ) чисел rл хо2 (mod N) по модулю этого составного числа N=dмdб. Для ячеек двух этих регистровых полос будет выполняться условие комплементарности. При этом мы ограничиваемся рассмотрением лишь фрагмента НРЧ.

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

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


Тривиальные области СММ нечетного числа


Введем несколько определений.
Определение. Списочной многострочной моделью (СММ, СМ-моделью) числа называется таблица строк заданного вида (формата из 8 именованных полей: rл, х1, хо, t, p, rc , tп, rп). Ниже привожу расчетные формулы для переменных.

rлхо2(modN)x12(modN)-квадратичный вычет левый;
х1 = N xо дополнение хо до модуля;
хо текущий номер строки СММ;
t=х1 хо =t1 + tо разность слагаемых строки; раскладывается в сумму смежных;
p =t1tо произведение смежных слагаемых;
rс (t2 1)(mod N) =t1tо(modN); средний вычет в строке;
tпi = 2xоi 1; нечетное число; сумма номеров смежных строк;
rп х1хо(modN=N rл произведение слагаемых; правый вычет в строке.

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

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

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

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

Тип модели


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

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

Числа N в СММ могут существенно различаться не только своими значениями, но и делителями. Сами делители также могут иметь различия (малые и большие значения) при близких значениях их произведений, т.е. N1 и N2 близки, а их делители N1 = 111129 = 12419 существенно различаются на 1129 11 = 1118 или N2 = 101123 = 12423 всего на 123 101 = 22 единицы.

Числа, включающие в качестве делителей квадраты, имеют свои особенности. Указанные различия проявляются специфически в СМ-моделях и всегда желательно учитывать такую специфику N.
Например, в канонической СМ-модели (N = a(a+2) близнецы) дублируемые КВК следуют смежными парами, сумма первых степеней которых постоянна и равна среднему числу (a + 1).

Пример. (Делители числа значительно удалены друг от друга). Пусть N = 311129 = 34999; rс(1) = 26250 = 3rл(0) = 38750, контур НРЧ 34999 +35001 = 70000 с номером kп =70000:8 = 8750, инвариант N равен kп/2 = 4375, отсюда интервал для N содержит слагаемых 31 и среднее слагаемое равно dб = 1129, меньшее число tпм= 1 + dб dм = 1+1129 31 =1099 и большее число интервала tпб= dб + dм 1= 1129 + 311 = 1159; действительно, 15(tпм+ tпб) + dб =152258 +1129 = 34999.

Инвариант числа определяется суммой номеров 15 контуров и половиной номера большего
275+276+277+278+279+280+281+282+283+284+285+286+287+288+289+290/2= 4375.

Границы интервала и контуров левая Гл(k = 275) = (2275 1)2 = 301401, для интервала правая Гп(k = 290) = (2290)2 = 336400. Разность границ Гп Гл = 336400 301401 = 34999 = N.
Граница ТКВК хомах = 187 = 631 + 1; хо (rc = 0) = 3952; первая точка
хо = 952 дубля с КВК(177) = 31329.
В этой точке ЗРД определяются делители: 952 177 = 775 = 3125; 952 + 177 = 1129.

Рассмотрим поведение КВВ (всего имеется 187 КВК), дублирующих (181 КВК) тривиальной области списка. Квадрат числа 31 и квадраты его кратных не дублируются, так как число является делителем N.
Распределение КВК по списку обладает определенной регулярностью, КВК группируются по 12 строк с интервалом между ними 31, и интервал между группами строк равен 797 либо 766 строк. Это следует из анализа таблиц. Существует 15 групп 1-15. В пределах групп возникают аттракторы, строки как бы притягивающие полные квадраты КВК.

Определение. Аттрактором (притягивающим квадраты элементом НРЧ) будем называть точку (клетку) НРЧ, соответствующую значению кратному dб.

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

Для более ясного представления и понимания как все устроено с делителями N в НРЧ вначале будем рассматривать картину хорошо разделяемых областей аттракторов. Текст будем сопровождать числовым примером, в котором роль модуля играет полупростое число
N =311129 = 34999. Следовательно, аттракторами будут числа: 11129, 21129 = 2258, 31129 =3387, , 151129.


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

Пока хо малы (левая желтая колонка верхней части таблицы) их квадраты 187 штук (хо2 < N) не превышают модуль N. Таким образом, начальный отрезок строк CM-модели для (хо) в НРЧ от 1 до N, содержащих КВВ равные подряд следующим полным квадратам (КВК) мы определили как область тривиальных квадратичных вычетов (rл) квадратов (ТКВК).

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

Рассмотрение для подряд следующих всех нечетных чисел от 1 < t < N 2 преобразований вида rс (t2 1)(mod N), где
t = х1 хо = N 2хо разность значений, также порождает ещё одну другую тривиальную область значений переменной (rс), обозначаемую (ТССС).

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

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

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

На числовой оси с шагом, равным большему делителю dб, размечаются точки (позиции): dб, 2dб, 3dб, , dmdб аттракторы. После этого аналогичную разметку выполняем для меньшего делителя dm. Последняя точка в обоих случаях совпадает с N.

Между размеченными с разным шагом точками возникает множество интервалов разной длины четной и нечетной, среди которых имеются такие интервалы, которые называются решающими, так как именно они обеспечивают нахождение делителей составного модуля КЧКВ
N = dmdб.

В соответствии с законом распределения делителей (ЗРД) решающий задачу факторизации больших чисел (ЗФБЧ) интервал своими границами [Гл, Гп] должен иметь точки кратные разным делителям N.

Поскольку относительно произвольной точки кратной dб группируются точки кратные dm и их 2 или более слева и справа от dб, то точки кратные dб назовем (Аi) аттракторами (притягивающими). Для решающих интервалов между построенными точками их границы выбираются кратными одна меньшему делителю, другая большему.

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

Пример А. Пусть задан составной модуль приведения N = dmdб = 311129 = 34999 конечного числового кольца вычетов. Числовая ось (фрагмент ряда) разбита точками с шагами dm = 31 и dб = 1129. Требуется представить картину подобного разбиения фрагмента на отрезки и определить положение решающих ЗФБЧ интервалов с их характеристиками.

Решение. Начнем с первой (i = 1) точки (аттрактора А1) с координатой равной dб. Эта точка принадлежит замкнутому малому интервалу [1116, 1147 = 1116+31], накрывающему ее, 36dm<1129< 37dm или 1116< 1129 < 1147. Удаленность dб от границ замкнутого интервала [1116, 1147] слева от dб равна 1129 1116 = 13 нечетному числу и справа от dб равна четному числу 1147 1129 = 18.

Правый интервал [Гл, Гп] = [1129, 1147] имеет целочисленную среднюю точку с координатой хц = (Гл + Гп) = (1129 + 1147) = 1138. В этой точке хц ее квадратичный вычет по заданному составному модулю N (в соответствии с ЗРД) должен быть равен полному квадрату, в чем легко убеждаемся, 11382(mod 34999) = 81 = 92 и этот результат указывает на то, что этот интервал решающий, т. е. обеспечивает вычисление делителей модуля N. Вычисления делителей пока отложим.

Перейдем к рассмотрению интервала [1116, 1129] слева от А1 аттрактора, длина которого 13. Он не имеет целочисленной средней точки и не является решающим, но положение легко исправимо, переносом левой границы (Гл) в другую точку более близкую к началу координат (дальше от аттрактора).

Исправленный новый интервал [Гл, Гп] = [1116 31, 1129] решающий и он приобретает вид [1085, 1129] с изменившейся длиной 1129 1085 = 44, т. е. уже имеет среднюю точку, координата которой равна хц = (Гл+ Гп) = (1085 + 1129) = 1107.

В этой точке, следуя ЗРД, квадратичный вычет по заданному составному модулю также должен быть равен полному квадрату. В этом легко убедиться выполнив вычисления 11072 (mod 34999) = 484 = 222 , что также обеспечивает в соответствии с ЗРД вычисление делителей модуля.

Таким образом, найдены два (справа и слева) решающих ЗФБЧ интервала для аттрактора А1, т. е. точки 1dб, ближайшей (i = 1) среди кратных к началу координат. Зададимся вопросом ограничено ли количество решающих интервалов для этого аттрактора? Если да, то чем определяется это ограничение?

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

В рассматриваемом примере порог maxКВК = rлmax =N=34999=187,080, т. е. превышает 6-кратную длину малого интервала 631 = 186 < 187, но 7-кратное значение интервала превышает это значение maxКВК 731 = 217 > 187.

Следовательно, все значения КВК (дубли из ТКВК) могут принимать значения, не превышающие 187. Что касается количества решающих интервалов, группируемых аттракторами, то анализ ситуации показывает следующее.

Мощность множества ТКВК это 187 элементов кольца, из которых не дублируются КВК кратных значений kmdm, km = 1(1)(187/ dm). В примере таких шесть значений 31, 62, 93, 124, 157, 186. Строки СМ-модели в своем составе содержат строки, кратные разным делителям.

Строк кратных dб всего 15 = (dm 1), так в каждой из них сумма номера строки хо и его дополнения х1 = N хо остается постоянной равной N, т. е. дополнение также кратно числу dб.

Из анализа нашего примера следует, что существует всего 15 аттракторов Аi, i = 1(1)15 и с каждым из них связаны (187 6)/15 = 12,06 решающих интервалов, с центрами которых связаны дубли из ТКВК. Другими словами, сдвигаясь к началу координат с шагом 31, увеличиваем решающий интервал, КВВ в центре которого получаем новый полный квадрат.

Пример Б. Используя данные примера А, вычислим решающие интервалы, наиболее удаленные влево и вправо от аттрактора А1. Левые интервалы:
[Гл, Гп] = [1116 62, 1129] = [1054, 1129] этот интервал не имеет целочисленной центральной точки хц = (Гл +Гп) = (1054 + 1129) = 1091,5.
Обе границы интервалов должны быть нечетными числами.

Сдвигаемся еще на один dm интервал [1116 93, 1129] = [1023, 1129] и находим центр
хц = (Гл + Гп) = (1023 + 1129) = 1076, в котором
КВВ = КВК = 10762 (mod 34999) = 2809 = 532 .

Заметим, что положение центров (53 22 = 31) интервалов, как и их протяженности (rл) изменяются на величину кратную dm, а левой границы на 2dm. Таким образом, левые (правые) границы решающих интервалов и их центры принимают конкретные значения (здесь граница 1129 постоянная):



Зачеркнутые числа выходят за пределы допустимых элементов КЧКВ
Для аттрактора А2 = 2dб и всех последующих вычисления аналогичные. Их результаты приведены в таблицах 1-15.

В работе здесь рассмотрена контурная модель, связанная с изучением задачи факторизации больших чисел (ЗФБЧ). Особенность модели состоит в том, что в ней НРЧ представлен непрерывной последовательностью нумерованных (номер k = 1(1) ) контуров (блоков), размер которых (L(k)) с увеличением номера возрастает, но остается кратным числу 8, L(k) = 8k.

Каждый контур представляет множество позиций НРЧ, где крайние позиции содержат квадраты нечетных последовательных чисел. Эти крайние позиции называются границами: левая
(Гл(k) = (2k 1)2) и правая (Гп(k) = (2k + 1)2, Гп(k) > Гл(k)).

Все контуры образованы двумя полуконтурами с размерами левый полуконтур m(k) = 4k 1 и правый контур M(k) = 4k+1. Полуконтуры в k-м контуре имеют общую границу
Гц(k) = (2k)2 квадрат четного числа.

Длина (размер) каждого полуконтура нечетное число и M(k) m(k)= 2, а их сумма равна
M(k) + m(k) = L(k) длине k-го контура, левая и правая границы которого совпадают с левой границей меньшего и с правой большего полуконтура.

С введением понятий контура и полуконтура модель НРЧ можно представить как непрерывную последовательность нечетных чисел 1, 3, 5, , в которой каждое число является полуконтуром некоторого k -го контура, где при известном значении N полуконтура, его номер определяется соотношением
k =(N 1).

Знак (+) соответствует левому полуконтуру и () правому. Любое составное нечетное натуральное число (СННЧ) N >9, будем рассматривать как полуконтур или интервал в НРЧ с длиной N. Длина интервала нечетное число равное сумме нечетного количества последовательных слагаемых (полуконтуров), в которой количество слагаемых равно меньшему делителю N, а среднее слагаемое большему делителю N.

В действительности нам известны лишь N и, что оно составное, равно произведению двух простых чисел.
Рассматриваются составные нечетные натуральные числа (СННЧ) среди которых нет чисел N =k2 полных нечетных квадратов.

Дело в том, что такие квадраты дают другую картину распределения квадратичных вычетов (КВВ) элементов кольца, отличающуюся от картины для полупростых чисел N = pq, p < q. Квадратичные вычеты для N = k2 из тривиальной области не дублируются в списочной многострочной модели (СММ) числа и закон распределения делителей (ЗРД) в такой ситуации не работает.

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

Утверждение. Для двух нечетных произвольных простых чисел p и q их сумма и разность четные и либо их сумма = (р + q), либо их разность = (р q) делится на 4.

Расстояние (в числе строк) между этими строками равно меньшему делителю р. Номер верхней строки с дублируемым средним вычетом определяется соотношением хов = (р q):4. Отсюда номер нижней строки равен хон = хов + р. Положение этих (верхняя и нижняя) строк определяются элементами колонки Тп, которые кратны меньшему делителю.

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

Области аттракции модуля сравнения N = 34999






Размах области аттракции постоянный для всех аттракторов (равен 341 строке), кроме той, что содержит инволюцию (увеличен на dm =31 строку).
Между областями аттракции интервалы либо 766, либо 797 строк. Области хорошо разделены, хотя их влияние друг на друга не исключается.

Сближение значений делителей изменяет (уменьшает) удаленность областей вплоть до того, что области наезжают одна на другую и разобраться с решающими интервалами становится проблематично. Но закон распределения делителей (ЗРД) числа работает и в этих условиях. Здесь возникает множество вопросов, ответы на которые пока не получены.

Выводы



Основой списочной многострочной модели (СММ) числа N является модифицированное конечное числовое кольцо вычетов по модулю составного числа N;

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

В соответствии с законом распределения делителей (ЗРД) решающий задачу факторизации больших чисел (ЗФБЧ) интервал своими границами [Гл, Гп] должен иметь (и имеет) точки кратные разным делителям N;

Соотношение ЗРД (di=НОД(N, xоxо2(mod N))) обеспечивает получение (вычисление) делителей N.
Источник: habr.com
К списку статей
Опубликовано: 25.06.2020 20:11:16
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Алгоритмы

Информационная безопасность

Криптография

Математика

Натуральный ряд чисел

Модель числа

Категории

Последние комментарии

© 2006-2020, personeltest.ru