Типизация моделей составных чисел
Подход, выбранный в публикуемой работе для моделирования и исследования составного числа, основан на концепции закона распределения делителей (ЗРД) числа в натуральном ряде чисел (НРЧ). Приводятся общая и каноническая модель числа, сохраняющая основные свойства, присущие большинству реализаций, но имеющая стандартный (наиболее простой) вид. Возвращаясь к прошлым публикациям, перечитал комментарии и принял решение создать эту.
Разнообразие множества исследуемых и различающихся реализациями моделей чисел вынуждает исследователя вводить для них типизацию (не классификацию). Два близких по значению нечетных числа из одного класса могут иметь разный тип. Дело в том, что списочная многострочная модель (СММ), разработанная для составного числа, выявляет весьма тонкие, но существенные различия даже в очень близких числах из одного класса.
При введении (загрузке) в модель исходного значения N эти различия при их учете влекут использование отличающихся алгоритмов обработки, которые приспособлены к конкретному типу чисел. В работе приводится пример двух близких N1 = 1961 и N2 = 1963 чисел, тип которых не совпадает. Это, в свою очередь, приводит к выбору и исполнению (вычислению) соответствующих алгоритмов обработки этих чисел.
Цель публикации в первую очередь образовательная, познавательная, популяризация науки, а также стремление привлечь в ряды исследователей, в науку приток новых молодых умов, вызвать в таких умах стремление к поиску ответов на возникающие вопросы. Масштабность темы требует ввести разумные ограничения на излагаемый материал после краткого панорамного её рассмотрения.
Введение
По мере изложения текста используются аббревиатуры (сокращения), которые я собрал в одном месте для удобства читателя. Эти сокращения мной используются во всех статьях.
Аi — аттрактор, значение кратное большему делителю;
СММ — списочная многострочная модель числа;
ЗРД — закон распределения делителей;
НРЧ — натуральный ряд чисел;
ПНЧ — последовательность нечетных чисел;
ИБ — информационная безопасность;
КВВ — квадратичный вычет по модулю N;
КВК — квадратичный вычет полный квадрат;
КЧКВ — конечное числовое кольцо вычетов по модулю N;
СННЧ — составное нечетное натуральное число;
ТКВК — тривиальная непрерывная область строк модели, содержащая все КВК;
ТССС — тривиальная область строк модели, содержащая все средние вычеты, сохраняющие смежность сомножителей;
РИ — решающий интервал, интервал нечетной длины, центр которого характеризуется КВК;
НИ — накрывающий интервал, интервал нечетной длины (dm), содержащий кратное х = idб;
ДЦ, ДIn, Д0, — дубли строк центральной, первой (инволюций), последней (нулевой).
Предлагаю читателю внимательно рассмотреть таблицы 1, 2 и попытаться объяснить себе почему в указанных точках х числовой оси (нижняя строка таблицы) при разных составных модулях N=117, 119, 133 в некоторых из точек возникают квадратичные вычеты (КВВ) — полные квадраты (КВК), а в других нет? Этот вопрос и я задал себе в 2014 году, после прочтения статьи В.И. Арнольда (2010 года) «Случайны ли квадратичные вычеты?»
Ответом на мой вопрос получился закон распределения делителей числа в НРЧ. Ни о какой случайности я даже не мыслил. Удивило, что академик РАН от математики опубликовал эту статью. С другой стороны, стало понятно, что если даже академик предполагает КВВ случайными, то значит в мире математики ответа на вопрос о распределении делителей натурального числа вдоль НРЧ не существует. И ответ придется искать самому.
Для меня НРЧ всегда был полностью детерминированным объектом. Из этого следовало, что причиной появления КВВ = КВК, т.е. полных квадратов однозначно является не стохастичность. После того как в пределах фрагмента НРЧ сделал разметку чисел, кратных разным делителям (табл. 2, N = 77 =7∙11) все встало на свои места. Квадраты появляются только в точках центров замкнутых интервалов нечетной длины, границами которых служат числа кратные разным делителям N. Такие интервалы позднее были названы решающими интервалами (РИ).
Заниматься моделями числа и натурального ряда мне было интересно и в этой области уже имелись определенные результаты. Один из моих учеников написал и успешно защитил диссертацию по этой тематике. Просматривалась и тесная связь проблемы с криптоанализом в криптологии, с двухключевыми шифрами и односторонними функциями.
Таблица 1. Фрагменты НРЧ и списков квадратичных вычетов колец Z117, Z119, Z133, Z.
Рассмотрим составные натуральные числа N1 = 117, N2 = 119, N3 = 133, которые ограничивают начальные фрагменты НРЧ, и N→ ∞. Для элементов фрагментов выпишем квадратичные вычеты (КВВ) по модулям Ni . Пока элементы малы их квадраты при редукции не изменяются и эту область КВВ назовем тривиальными квадратичными вычетами (ТКВК). Дальше эти квадраты встречаются повторно, но порядок их появления (возникновения) долгое время не получал объяснения.
В публикации 2014 года я привел объяснение этому феномену.
Таблица 2. Фрагмент НРЧ и квадратичных вычетов по модулю N = 77
Действительно, замкнутые интервалы [7, 11];[11,14];[14, 22]; [22,28]; [21, 22];[21,33]; [28,33];[33,35] все, кроме [11,14]; [28,33] и [21, 22] имеют нечетную длину, их границы кратные разных делителей (заливка разного цвета), КВВ в средней (желтой) центральной точке — полный квадрат. В реальности для чисел и их КВВ мы можем распознавать только полные квадраты. Они детектируют замкнутые интервалы, называемые решающими интервалами (РИ).
Типы моделей числа
Принимая в обработку число N, практически никогда неизвестно, к какому типу оно относится. При очень близких значениях N1 = 1961 и N2 = 1963 их делители очень сильно различаются. Эти различия сказываются на процессе моделирования и всего исследования числа. Этот факт отмечался уже П. Ферма. Основной принцип разделения на типы СМ-моделей числа — соотношение между его делителями. Когда для делителей модуля N соблюдены требования шифра к числам RSA: делители простые нечетные числа одинаковой разрядности и разность между ними имеет такую же разрядность, то такие числа описываются и исследуются в рамках моделей второго типа (ТКВК∩ТССС = 2, тип 2). Главной особенностью чисел моделей 1-го и 2-го типов является непустое множество пересечения тривиальных областей строк ТКВК∩ТССС ≠ Ø. Как правило, строки пересечения содержат КВК и ССС для полупростых N пересечение в СММ представлено множеством из двух строк. Другие два типа моделей имеют такое множество (ТКВК∩ТССС = Ø, тип 0) пустым, либо (ТКВК∩ТССС = 1, тип 1) с множеством, состоящим из одной строки.
О тривиальных областях модели уже писал раньше, и ограничусь ссылками на свои работы.
Замечу здесь, что в области теории чисел мои статьи активно копируются другими сайтами и, что мне кажется несколько странным (я ведь не математик), представляются читателям уникальными. Публикация о ЗРД в топе с 2014 года. О моделях числа тоже на мой запрос выдаются мои же статьи.
Приведу названия некоторых известных атакующих алгоритмов, решающих ограниченную задачу факторизации. Конечно, в них используются модели числа, но авторы не оформили такие модели как самостоятельные структуры и не сделали их универсальными. Эту работу за них никто не сделает
1) The Quadratic Sieve (QS) — метод квадратичного решета []; Pomerance;
2) The Namber Field Sieve (NFS) — метод решета числового поля []; J Pollard;
3) The Elliptic Curves Method (ECM) метод эллиптических кривых [] Х.Ленстра.
Второй из методов распадается на два:
— Special Namber Field Sieve (SNFS);
— General Namber Field Sieve (GNFS).
Известно, что в начальном фрагменте от 0 до N — 1 НРЧ делители dm и dб простые числа и их кратные значения занимают множество распределенных регулярно позиций. Такая регулярность объясняется постоянной величиной шага между последовательными значениями (позициями) для каждого из двух делителей. Другими словами, НРЧ разбивается кратными точками на малые (dm) и большие (dб) интервалы. Для нашего исследования интерес представляют интервалы между парами последовательно занимаемых позиций кратными разных делителей, в роли которых выступают кратные делителям числа.
Чем больше разность Δ между делителями, тем меньшее число позиций будет занято кратными большего из делителей. Все такие позиции оказываются внутренними точками малых интервалов с длиной dm. Например, для N = 1961 = 37·53, Δ =16, N = 1963 = 13·151, Δ=138. Назовем те малые интервалы, которые содержат позиции (точки), занимаемые кратными большего делителя, – накрывающими интервалами (НИ). Очевидно, их число равно dб — 1, т.е. числу позиций, которые могут быть заняты кратным делителя dб. Дальше текст будем иллюстрировать моделью второго типа для N = 1961 = 37·53. Первый (Т1) и второй (Т2) типы СММ имеют подтипы, определяемые конфигурациями одиночных строк с rccc и пар смежных кратных строк (см. рис. ф).
Общая модель составного нечетного натурального числа
Сейчас здесь речьпойдет об упрощенной модели числа без перегрузки читателя деталми. Важным вопросом в исследовании чисел следует признать вопрос о моделировании отдельного составного числа. Занимаясь вопросами и задачами информационной безопасности (ИБ), исследователю приходится разрабатывать модели явлений, объектов, процессов и технологий, среди которых значительное место занимают модели чисел.
При создании моделей используются разнообразные переменные. Интернет определяет переменную, исходя из потребностей программистов и IT-специалистов, и там она определяется так.
Таблица 3 — Примеры списочных многострочных моделей (СММ) для разных N
Переменная — это ячейка в оперативной памяти микроконтроллера, которая имеет своё уникальное название (а также адрес в памяти) и хранит значение соответственно своему размеру. К переменной мы можем обратиться по её имени или адресу и получить это значение, либо изменить его. Зачем это нужно?
В переменной могут храниться промежуточные результаты вычислений, полученные «снаружи» данные (с датчиков, из Интернета, от интерфейсов связи) и так далее. С этим можно согласиться, но это далеко не все, что нужно при моделировании числа.
Работая с натуральными, целыми числами, моделируя такие числа, для решения многообразных задач нам приходится вводить и другие понятия для различения как моделей, так и самих чисел. Например, значения чисел N = 1961 и N = 1963 близки (различаются всего на две единицы), но их модели мы относим к разным типам, так как они структурно и функционально сильно различаются.
Причиной такого различия служит, прежде всего, как аддитивный (задается непрерывным отрезком последовательности нечетных чисел (ПНЧ)), так и мультипликативный состав чисел:
1963 = 13∙151 = 139+141+143+145+147+149+151+153+155+157+159+161+163;
1961 = 37∙53 = 17+19+21+23+25+27+29+31+33+35+37+39+41+43+45+47+49+51+
+53+55+57+59+61+63+65+67+69+71+73+75+77+79+81+83+85+87+89.
В случае 1963 требуется лишь 13 слагаемых, в то время как для 1961 необходимо уже почти в три раза больше — 37 слагаемых.
Классификацию (типизацию) подобных чисел по типам удобно ввести через типы их моделей. При построении модели числа N, устанавливается ее тип, который приписывается и самому числу. Вначале рассмотрим использование такой модели для составного нечетного натурального числа (СННЧ), получаемого как произведение всего лишь пары простых чисел (близнецов) или как разность полного квадрата четного числа и единицы (N = 142 — 1 = 195), а затем и уменьшенного втрое (N = 195:3 = 65) при сокращении на нечетный делитель.
Для конечного числового кольца вычетов (КЧКВ) с единицей по составному (полупростому) модулю все классические законы и теоремы о таком кольце остаются справедливыми и круг задач, излагаемых в учебной литературе и знакомых мне монографиях, обеспечен методами их решения, но сам по себе этот круг достаточно узок, ограничен.
Известно, что КЧКВ содержат ключевые элементы (идемпотенты, тривиальные и нетривиальные инволюции), а также элементы, называемые делителями нуля, квадратичные вычеты и др. Вопрос выявления таких элементов, их количества, состава и распределения в кольце, если и рассматривается в литературе, то, как правило, предлагаются переборные методы решения. Для КЧКВ с ограниченным порядком аддитивной и мультипликативной групп кольца такой подход приемлем, но при значительном росте порядков групп практически непригоден. Различие СМ-модели N= 1963 и N= 1961 состоит, прежде всего, в устройстве многострочного списка. (табл. 4, 5).
Строки, содержащие полные квадраты (левые вычеты) для N = 1963, организованыкак разбиение полного списка СММ на области аттракции с аттракторами в центральных строках областей. Количество таких областей возникает в зависимости от большего делителя. Размер области аттракции определяется меньшим делителем и количеством РИ в области. Для всех РИ в его центральных точках хцвозникает rл = k2 = КВК, где k — удаленность границ РИ от хц. Одна из границ всех РИ в области аттракции равна самому аттрактору, т.е. idб, i — номер области, центры РИ следуют с нарастанием значений с постоянным шагом (dm).
Таблица 4 — Строение модели для N = 1963 (6 областей аттракции)
Строки СМ-модели, содержащие полные квадраты (левые вычеты) для N = 1961, организованыиначе. Они равномерно распределены по списку и следуют парами, между строками которых размещаются 8 других строк. Сумма ∑ первых степеней квадратов (КВК) постоянна и равна полусумме делителей ∑ = ½(53 + 37) = 45, а число строк Δ между строками пары равно полуразности делителей Δ = ½(53 — 37) = 8, между парами число строк равно меньшему делителю (37). Сказанное иллюстрируется данными таблицы 5.
Таблица 5 — Строение модели для N = 1961 (равномерные пары квадратов)
Каноническая модель нечетного составного натурального числа
Список (табл. 6) СМ-модели (N = 323 = 17·19) разбит на три колонки и состоит из 161 строки. Квадратичные вычеты–квадраты (КВК) вне пределов ТКВК размещаются в левой колонке смежными парами (сумма первых степеней пары квадратов постоянна (18), равна полусумме делителей, зеленая заливка). Сумма нечетных элементов правой колонки (оранжевая заливка) равна N — составному модулю приведения кольца. Элементы 305 и 18 –нетривиальные инволюции, а 171 и 153 — идемпотенты, их разность — меньшая инволюция 171 — 153 = 18. Строка с хо = 81 — центральная. Строки-дубли: Д0, ДIn, ДЦ.
Рассмотрим некоторые свойства ограниченной модели составного отдельного полупростого числа N, в основу которой положен принцип погружения простой линейной модели в множество подобных. Каждая из частных моделей (строкка) для заданного числа N = pq = dбdm представляется суммой двух целочисленных слагаемых х1 + хо = N с постоянным значением.
Количество таких частных моделей конечно, так как переменные N, х1, хо — целочисленные. Формирование модели осуществляется построением прямоугольной таблицы, списка с множеством строк, каждая из которых кроме переменных (х1, хо) линейной модели включает в левой позиции (rл) квадратичный вычет (КВВ) переменных х1, хо строки по модулю N, , а справа от них разность (t) переменных t = х1 — хо. Таким образом, в каждой строке заполняются четыре позиции.
Таблица 6 — Каноническая модель нечетного составного натурального числа N = 17∙19 = 323
Перечислим некоторые свойства СММ, которые легко проверяются в таблице 6 СММ:
— значения КВВ строк, которые послойно (верх\низ) окаймляют центральную строку различаются на величину номера слоя;
— значения КВВ строк, послойно окаймляющие строку нетривиальных инволюций, размещаются в первом слое строк, содержащих КВВ = КВК полные квадраты;
— значения КВВ строк, которые послойно (верх\низ) окаймляют строку, содержащую
КВК = 22=4 размещаются во втором слое строк, содержащих КВВ = КВК большие 4 полные квадраты;
— значения КВВ строк, которые послойно (верх\низ) окаймляют строку, содержащую
КВК = 32=9 размещаются в третьем слое строк, содержащих КВВ = КВК большие 9 полные квадраты;
Аналогично и с другими полными квадратами. В этом легко убедиться:
Сверху над КВК =1 размещены: 289, 256, 225, 196, убывающие полные квадраты, до 9, 4, 1;
Снизу под КВК = 1 размещены числа: от 38, 77, 118, 161, 206, …, до 187 КВВ 4, 9, 16, …, 289 лежит между 256–4–77; 225–9–118; 196–16–161; …;187–256–4;256–289–1
Переменная хо может выполнять роль номера строки и принимает значения от 1 до хоmax = ½ (N — 1), а переменная х1 = N – хо, служит дополнением хо до N. Правая переменная t = 1(2)N — 2 принимает только нечетные значения 1, 3, 5, …, N — 2, следующие непрерывно подряд одно за другим. Списочная многострочная модель числа N упорядочена лексикографически (возрастает) по переменной хо.
Предлагаемая модель выстраивается при допущениях, что N составное полупростое, следовательно, нечетное число, и делители dб, dm числа N известны, что позволяет произвести разметку кратных делителям чисел. Но после формирования модели ее функционирование определяется заданием только модуля N делители неизвестны и находятся путем использования свойств модели. Она обеспечивает детальное визуальное представление списка всего множества частных линейных моделей числа N с возможностью выделения любой из переменных в любой строке списка.
Строки списка полезно разделять на кратные делителям и некратные им, что обеспечивается знанием значений dб, dm. Кратными называются те строки, которые содержат хотя бы один элемент (переменную) кратный одному из делителей N. Таким элементам для большей наглядности рекомендуется выполнить заливку их позиций (клеток) разным цветом для разных делителей.
Эту модель нечетного составного большого числа N можно представить, как объединение двух самостоятельных подмоделей числа. Одна базируется на начальном фрагменте НРЧ, в которой элементы кратные делителям N регулярно встраиваются в список с коэффициентами пропорциональности 1, 2, 3, 4, …, d — натуральными числами.
Другая базируется на начальном фрагменте последовательности нечетных чисел (ПНЧ), в которой элементы, кратные делителям N также регулярно встраиваются, но коэффициенты пропорциональности всегда 1, 3, 5, 7, …, d — нечетные числа. Свойства одной и другой подмоделей по большей части имеют совпадающий характер, но часть свойств различается и информационно дополняют одна другую. Структурно и функционально модели тесно переплетаются и информационно обогащают друг друга.
В первой подмодели элементы фрагмента НРЧ представляются суммой двух слагаемых, равной постоянному числу N, во второй — элементы ПНЧ раскладываются в сумму двух смежных слагаемых, которые затем перемножаются с приведением произведения по модулю N.
Список строк СММ содержит характерные крайние строки (первую\последнюю) и центральную строку (хоц = rпо, t = tп = xоо), являющуюся «осью симметрии» для ключевых строк и их областей. Так дубль-строка нулевого среднего вычета и строка идемпотента расположены на одинаковом удалении от центральной строки. Симметричное расположение по отношению к центральной строке имеют и строка нетривиальных инволюций, и средняя строка четверки смежных кратных пар строк.
Для иллюстративного примера выберем составное полупростое число N = рq = 1739161 и для него построим СММ. Создадим первую хо = 1 и последнюю хо = 869580 строки списка. Номер последней строки впечатляет и, понятно, весь многострочный список выводится на печать не будет. Будем рассматривать некоторые части, начиная сверху с области ТКВК. Колонка Rс проявляется первым средним вычетом вида rсссв=442890 в строке хо = 90. Затем в строках хо = ½ (dm +1) и хо = ½(dб +1) появляются кратные делителям значения средних вычетов, которые сверху дополняются меньшими кратными тем же числам значениями, т.е. возникают пары смежных кратных разным делителям строк. Сами значения таких средних вычетов рассматриваются ниже.
После двух пар (верхняя\нижняя) смежных кратных строк появляется следующий средний вычет вида rсссн = 235710 в строке хо = 90 + dm = 90 +1151 = 1241.
Второй (нижний) по списку средний вычет rсн = rсссн = 235710 = tо·t1= 485·486 появляется в строке хо = 90 + dm = 1241. Этот номер строки определяется суммированием с приведением по модулю
хо = rсссн + rло = 235710 + 1304371 = 1540081 = хо2 =12412. С другой стороны, номер строки верхней пары смежных кратных строк может быть определен иначе, а именно, суммированием большего сомножителя нижнего среднего вычета и номера строки верхнего rсссв, т.е. хон = хонв + t1 = 90 + 486 = 576.
Первый КВК rл = 1225 =352 за пределами ТКВК получается в строке с номером равным сумме смежных сомножителей первого среднего вычета хо = tо + t1 = 665 + 666 = 1331.
Заключение
Приводится общая и каноническая модели чисел. Различие в моделях создается КВК квадратами, порядком их следования по списку модели. Если в канонической модели соблюдается жесткий порядок (пары КВК смежные и разделяются одинаковым промежутком), то в общей модели такой порядок разрушается и выглядит хаотичным.
В статье рассмотрены числа, с очень близкими значениями, но их модели имеют существенные различия для их целевой обработки. Эти отличия приводят к необходимости строить алгоритмы обработки таких чисел, учитывая их особенности, которые в статье названы типами.
