В арифметике известны элементарные действия с числами (+), (–), (×), (/) и др., использование которых при заданных исходных данных дает нам возможность получать определенные результаты: сумму, разность, произведение, частное. Обратное действие с результатами в качестве исходных данных возможно далеко не всегда. Например, возведение в третью степень числа 7 3 = 343, обратным действием имеет извлечение из результата корня третьей степени (343)1/3= 7. При заданных результатах определить какими были исходные данные не всегда возможно. Для суммы даже двух слагаемых 7 + 6 = 13 такого единственного обратного действия нет. Для числа 13 мы можем получить очень разные исходные 13 = 1+12 = 2+11 = 3+10 = 4 +9 = 5 + 8 = 6+7.
С умножением в качестве исходных составных чисел картина похожая, но если исходными сомножителями взяты простые числа, то обратной операцией для произведения является действие, называемое факторизацией числа – результата умножения. К сожалению, на сегодняшний день действие факторизации не может быть задано какими-то простыми вычислениями, а очень большие числа – результаты (сотни цифр в описании) вообще не могут быть факторизованы. Как выполнить поиск простых делителей результата-произведения мы сегодня не знаем.
Такие делители, вообще говоря, как-то распределены в числовых рядах. Например, в натуральном ряде чисел ( НРЧ) или в последовательности нечетных чисел (ПНЧ) простые числа-делители и их кратные имеют достаточно регулярные распределения, каждое со своим шагом.
Задавая произведение простых чисел N = p˖q˖h˖s, мы понимаем, что каждое из p, q, h, s меньше самого N. Если ограничить начальный фрагмент НРЧ или ПНЧ значением N, то в пределах выделенного фрагмента будут присутствовать кратные делителей с возрастающими от 1 коэффициентами (для ПНЧ коэффициенты будут нечетными). Сможем ли мы увидеть и выделить такие кратные делителей N? Они ведь нам неизвестны.
Сегодня ответ на этот вопрос положителен. В 2014 году мной на Хабре был опубликован закон распределения делителей (ЗРД) натурального числа N в НРЧ. Применение закона позволяет получать для заданного натурального N его простые делители и их кратные в НРЧ. Ниже я кратко повторю публикацию 2014 года и приведу расширенную версию ЗРД на ряд целых чисел N.
Введение
По мере изложения текста используются аббревиатуры (сокращения), которые я собрал в одном месте для удобства читателя. Эти сокращения мной используются во всех статьях.
Аi — аттрактор, значение кратное большему делителю;
СММ — списочная многострочная модель числа;
ЗРД — закон распределения делителей (dm – меньший, dб – больший делители);
ЗФБЧ – задача факторизации больших чисел;
НОД – наибольший общий делитель;
НРЧ — натуральный ряд чисел;
ПНЧ — последовательность нечетных натуральных чисел;
РЦЧ – ряд целых чисел;
ИБ — информационная безопасность;
КВВ — квадратичный вычет по модулю N;
КВК — квадратичный вычет полный квадрат;
КЧКВ— конечное числовое кольцо вычетов по модулю N;
СННЧ — составное нечетное натуральное число;
ТКВК — тривиальная непрерывная область строк модели, содержащая все КВК;
ТССС — тривиальная область строк модели, содержащая все средние вычеты, сохраняющие смежность сомножителей;
РИ — решающий интервал, замкнутый интервал нечетной длины, центр (ЦРИ) которого характеризуется КВК;
НИ — накрывающий интервал, интервал нечетной длины (равен dm), содержащий кратное
х = idб;
ДЦ, ДIn, Д0, — дубли строк центральной, первой (инволюций), последней (нулевой).
Из математических средств используется модулярная арифметика, сравнения по модулю, алгебраические структуры. Закон распределения делителей (ЗРД ) числа возник и существует с момента изобретения и использования числовых последовательностей. Но в течение тысячелетий его не удавалось открыть, сформулировать, нащупать. Причины этого явления здесь и сейчас рассматривать не будем.
Закон распределения делителей натурального числа в натуральном ряде чисел (НРЧ) опубликован в 2014 году на Хабре. Идея получения (вывода) соотношений и оформления закона возникла как очередной шаг выполнения исследований в области моделирования НРЧ и его элементов – отдельных чисел.
В настоящее время проблема разложения составного полупростого числа на множители является непреодолимой, если разрядность числа достаточно велика (сотни цифр). В теории чисел вопросу факторизации числа не уделяется должного внимания и отсюда отсутствие фундаментальных результатов.
Когда мне на кафедре ВУЗа поручили подготовить и читать новую дисциплину «Криптографические методы защиты информации», пришлось задуматься и углубиться в тему. Это был 1979 год. Никаких открытых опубликованных источников по криптографии в СССР просто не существовало. На Западе кроме монографий издавалось несколько периодических журналов.
Рассуждения мои тогда были просты. Поскольку современные системы кодирования и шифрования информации в основном – числовые, то необходимо создать модели самих числовых систем и их элементов (чисел), на которых можно было бы проводить исследования, экспериментировать, проверять гипотезы
Закон распределения делителей натурального числа
Стало ясно, что начинать надо с натурального ряда чисел (НРЧ) – системы, которая лежит в основе криптографических методов защиты информации. Непрерывная последовательность возрастающих целых положительных чисел (одномерная, линейная модель), где смежные элементы различаются на единицу. Но представления этой системы возможны в пространствах различной размерности 1 - линейное, 2 - плоскостное, 3 – объемное.
Известная спираль С. Улама стала мной рассматриваться как двумерная полная модель НРЧ. Инструментарий для работы с моделью, для выполнения исследования пришлось создавать самостоятельно. Объемная модель рассматривалась здесь. На плоскости точка (число N (x1, xо)) имеет две координаты: при их задании необходимо уметь определять N и обратно – при задании N находить координаты x1, xо, а также решать и другие задачи. Быстро выявилась ведущая роль нечетных чисел.
Понимание этого позволило создать усеченную плоскостную модель натурального ряда чисел, в основу которой положены сумма и разность квадратов натуральных чисел или гиперболическо-круговые зависимости. Модель гарантированно содержит все нечетные числа, но не все четные. Инструментарий для манипуляций с числами опять же создавался мной самостоятельно.
Все доступное у букинистов по теории чисел учебники, пособия, задачники собирались на моем рабочем столе. Так вот. НРЧ уходит в бесконечность, следовательно, в моделях можно задавать как угодно большие числа и работать с ними.
Числа – элементы моделей возможно представлять в мультипликативной или аддитивной форме. Я не стремился сразу усложнять модель. Допустимый вариант числа N = pq – полупростое число – произведение двух простых p и q чисел. Было понятно, что это значение N ограничивает начальный фрагмент НРЧ для исследования и формирования модели, содержит все нечетные и их кратные числа, меньшие N.
Разметка фрагмента НРЧ
Сделаем допущение, что нам известны делители N = pq. Очевиден факт, что для составных чисел N, где-то недалеко от начала фрагмента ряда встретится dm = p – меньший делитель N, и далее с постоянным шагом в регистровые ячейки будут вписаны его кратные; где-то также встретится dб = q – больший делитель и со своим постоянным шагом будут наблюдаться его кратные. Но как их увидеть, выявить? Нам ведь известно лишь составное N. Сделанное допущение обеспечивает создание наглядной картины. Ячейки, занимаемые кратными разных делителей, отмечаем заливкой разного цвета.
Пример 1. В таблице 1 анализируется для числа N = 77 распределение кратных делителей, их позиции отмечены заливкой (для dm зеленый и для dб синий цвет). Это границы замкнутых решающих интервалов, центрам хц интервалов соответствуют квадраты позиций, которые также отмечены заливкой (желтый цвет).
Таблица 1. Фрагмент НРЧ и квадратичных вычетов по модулю N = 77
Действительно, для всех замкнутых интервалов [7, 11]; [11,14]; [14, 22]; [22,28]; [21, 22]; [21,33]; [33,35], их границы кратные разных делителей (заливка разного цвета), все, кроме [11,14]; [28,33] и [21, 22] имеют нечетную длину, КВВ в средней (желтой) центральной точке – полный квадрат.
В интервале [7, 11] длиной L = 5 в центре КВВ(xцi =9) = 4, удаленность границ k =√4 =2. В позициях границ размещены Гл = 9 – 2 = 7, Гп = 9 + 2 = 11 делители с коэффициентами кратности равными 1.То есть интервал [7,11] – решающий интервал. Делители dm=7,dб =11 Интервал [21, 33] тоже решающий. Его длина L = 13, центр xцi = 27, КВВ(27) = 36, удаленность границ k = √36 = 6. Гл = 27 – 6 = 3˖7 = 21, Гп = 27 + 6 = 3˖11 = 33 делители с коэффициентами кратности равными 3. Делители dm= 7, dб = 11 вычисляются алгоритмом НОД Евклида.
В реальности для чисел и их КВВ мы должны распознавать только квадраты. Они детектируют замкнутые интервалы, называемые решающими интервалами. Окончательное вычисление значений делителей di = НОД(N, xц ± k), где k– удаленность границы от центра.
Понимая обозначения и символы в таблице 2, все после разметки фрагмента встало на свои места. Оказалось, что положением вычетов в списках КВК, управляют делители N.
Будем рассматривать замкнутые интервалы, между ячейками, занимаемыми разными делителями (с разной заливкой). Длины L замкнутых интервалов, измеряемые числом позиций (ячеек регистра) между границами (Гл, Гп – левойправой) интервала, образуемыми разными делителями (заливка разным цветом) и их кратными могут принимать четные и нечетные значения. При нечетных L в интервалах существует точка (позиция) хц центр интервала (см. табл. 1, 2), которым всегда соответствуют квадраты КВК. Приведем формулировку закона.
Теперь убираем допущение (о том, что делители известны). От разметки остаются только квадраты (табл.2). Удивительно, но никто из известных математиков, не остановил на этом своего внимания, не стал углубляться в суть распределения делителей составного числа N. Чтобы уяснить, о чем идет речь, представим фрагмент НРЧ (нижняя строка табл. 2) числами. Зададим составные модули сравнения N1, N2, N3 и для всего НРЧ N → ∞. Для каждого числа НРЧ вычислим квадратичный вычет по заданным модулям. Другими словами, найдем остатки от деления квадратов чисел на модули и выпишем их в строке модуля.
Вначале, при х2 < Ni, во всех строках одинаковые квадраты следуют подряд один за другим. Далее у нас х2 > Ni картина меняется. В строках для Ni появляются различные числа (остатки от деления), изредка перемежаемые квадратами. Но поведение квадратов в этой области выглядит хаотичным, невозможно предсказать где, когда и какой появится следующий квадрат для конкретной строки и для всего массива строк. Но мы-то теперь знаем, в чем здесь дело
Я в таблице 2 привожу всего три строки, но россыпь квадратов (желтые) в них не содержит никаких намеков на объяснение или существования закона, управляющего процессом их появления. Возможно, до меня никто и не формировал модель фрагмента НРЧ. В монографиях и трудах классиков мне это не встретилось. Если кто-то из читателей встречал что-то подобное, не сочтите за труд, сообщите мне источник. Буду Вам очень признателен и благодарен.
Таблица 2. Фрагменты НРЧ и списков квадратичных вычетов колец Z117, Z119, Z133, Z.
Таблица 2 содержит сведения о делителях составных модулей, но это надо было увидеть.
Разбиение НРЧ на отрезки можно не ограничивать фрагментом, а продолжать за его пределами вплоть до бесконечности, но лишь в положительном направлении аргумента х.
Левая колонка таблицы 2 содержит разные составные модули N. Приведенные в таблице фрагменты списков квадратичных вычетов по модулю N = dmdб для числовых колец вычетов с различными модулями сравнения порождают последовательности, содержащие полные квадраты, никак не связанные одна с другой и с положениями квадратов в НРЧ (нижняя строка таблицы). В 4-й строке (N => ∞) квадраты ряда целых чисел не изменяются и не перемещаются.
Анализ таблицы 2 показывает, что для разных чисел N тривиальная область может совпадать, а последующие появления КВВ = КВК распределены у всех по - разному, что трудно объяснить без знания ЗРД чисел. Общим свойством можно считать повторение значений вычетов КВВ(12) = КВВ(26)=11; КВВ(18)=КВВ(39)=58 в верхней строке; КВВ(23)=КВВ(40)=53 во второй строке; КВВ(14) = КВВ(40) = 79; КВВ(18) = КВВ(21) = 90, КВВ(25) = КВВ(38)= 40 в третьей строке. Аргументы КВВ(x) = соnst при равных значениях различаются на значение кратное одного из делителей составного модуля строки.
Действительно, 12+2·7 = 26, 18 +3·7 = 39 в верхней строке; 23 + 17 = 40 во второй строке;
14+2·13 = 40, 18 +3 = 21, 25+13 = 38 в третьей строке. Такие зависимости выполняются и для повторяющихся полных квадратов. Так во второй строке повторяются пять квадратов 4, 16, 25, 81,100. Для них КВВ(2) = КВВ(2 + 17) = 4, КВВ(4) = КВВ(4 + 2·17) = 16,
КВВ(5) = КВВ(5+7) = 25, КВВ(9) + КВВ(9 + 17) = 81, КВВ(10) = КВВ(10 + 2·7) = 100.
Пример 2. Задан составной модуль N = 119. Необходимо найти точки НРЧ х, в которых
х < N, x2 > N и x2(mod N) = r(x) =k2 — полный квадрат, где х — текущая точка НРЧ. После выполнения всех необходимых преобразований можно получить результаты, сведенные в таблицу 3.
Таблица 3. Фрагмент НРЧ и квадратичных вычетов по модулю N = 119
Краткий комментарий к таблице 3.
Две нижние строки таблицы содержат: предпоследняя — квадраты текущих элементов х кольца, а последняя строка — квадраты их дополнений х1, где х1 = N — х. Четвертая снизу строка содержит КВВ элементов кольца, которые являются полными квадратами (исключение точки
х = 11, ее КВВ = r(11) = 2 и х = 59, ее КВВ = r(59) = 30 ).
Такая картина распределения квадратичных вычетов конечного кольца вычетов имеет место всегда. Это послужило основанием для формулирования Закона распределения делителей (ЗРД) составного натурального числа. Выше (рис. 2-5) приведены решающие интервалы, соответствующие N = 119 (таблица 3).
Расширение закона распределения делителей на РЦЧ
Почему 1-я версия закона распределения делителей составного числа не применима для ряда целых чисел (РЦЧ)? Этот ряд, в отличие от НРЧ, допускает отрицательные значения переменных. НРЧ ценой упрощения вычислений накладывает ограничения на применимость ЗРД для других носителей (рядов). Так в 1-й версии ЗРД вводятся ограничения.
Во-первых, все числовые значения переменных не должны превышать значения N;
Во-вторых, отрицательные числовые значения не допускаются;
В-третьих, сужается множество точек х, способных быть центрами решающих интервалов
(ЦРИ). Такими центрами становятся только точки КЧКВ, в которых КВВ = КВК.
Изложение расширенной версии ЗРД числа, как и прежде, начнем с того, что имеется упорядоченный ряд Z целых чисел, элементы которого размещены в позициях (ячейках) некоторого сдвигового регистра.
Известно заданное составное нечетное число N с допущением об известных его делителях dm и dб. Такое допущение необходимо для получения соотношений, математических зависимостей, способствующих извлечению делителей из модели. Наше рассмотрение ограничим (с возможностью расширения) фрагментом Nр, симметричным относительно нулевой точки – начала координат.
Основные понятия, концепция исследования и подход сохраняются прежними.
Выполним разметку позиций (табл.4 столбцы Х1, Хо) непрерывного фрагмента целых чисел, включающего кроме интервала (1, N) и часть области отрицательных чисел. Такой фрагмент возможно произвольно расширять влевовправо, сохраняя разметку позиций на малые (dm) и большие (dб) интервалы, которые отсчитываются от начала координат, помещаемого в позиции с нулем.
Устранение (снятие) ограничений
В первой версии (публикация 2014 г.) ЗРД составного полупростого числа N = pq = dm·dб был рассмотрен ограниченный подход, что обусловливалось с одной стороны выбором в качестве носителя ЗРД числа N НРЧ, а с другой – математическим инструментарием – модулярной арифметикой, что все вычисления делало достаточно простыми.
Первое ограничение устраняется. включением отрицательных значений кратных делителям, которые существуют и при х < 0 в интервале от – ∞ до 0, и исключать их рассмотрение в теории – значит искусственно ограничивать ее возможности. Включение в качестве носителя ЗРД числа Z – ряда целых чисел (РЦЧ) дополнительно к НРЧ позволяет использовать отрицательные целые числа, что в рамках НРЧ было недопустимо.
Второе ограничение устраняется отказом от метода модулярной арифметики, что существенно расширяет возможности использования проявления ЗРД составного числа. Дело в том, что сравнение по модулю всех элементов х носителя (в их числе и квадраты центральной точки РИ) делает их меньшими этого модуля, что сужает область поиска РИ и вычисление границ РИ. В принципе квадраты в центре РИ могут быть и большими модуля, когда границы РИ достаточно раздвинуты (расширены).
Построение решающего интервала
При задании составного числа N его делители нам неизвестны. О решающем интервале нам известны только его свойства. Если для элементов фрагмента числового ряда вычислены КВВ по составному модулю N и среди них имеется полный квадрат k2, то этот квадрат всегда соответствует хц центру решающего интервала, а его значение – квадрат удаленности границ от центра. Извлекая квадратный корень k из КВВ = КВК, т.е. из найденного квадрата, определяем удаленность границ Гл и Гп РИ от его центра хц, Гл = хц – k, Гп = хц + k и значения границ.
Среди интервалов, имеющих границами кратные разных делителей, решающими могут быть только те, которые имеют нечетную L длину и соответственно хц центральную точку. Такой точке в новой версии ЗРД также всегда должен соответствовать полный квадрат. Первая степень k этого квадрата – задает удаленность границ РИ от его центра.
Как возникают такие квадраты в расширенной версии ЗРД? Мы возводим в квадрат очередную точку х, не предполагая, что она окажется центром РИ, это определяется вычетом по модулю N. Если вычет квадрат, то х – центр РИ и это случается редко. Но вычет всегда меньше модуля N, а квадрат х может быть больше модуля (х2 > N). Такой квадрат для текущей точки х не порождает РИ, так как левая граница при этом становится нулем.
Операция приведения по модулю – это многошаговое уменьшение квадрата на модуль N на каждом шаге, пока результат не станет меньше модуля. В новой версии мы не исключаем возможности на некотором шаге поиска (уменьшения х2 для больших х и увеличения для малых х) получить новый меньший квадрат, х2 >хm2 > КВВ, но больший КВВ. С другой стороны, при малых х их квадраты не велики и мы отыскиваем новый квадрат путем многократного суммирования модуля с КВВ + N + N + …+ N получаем больший квадрат.
Возникает вопрос, будет ли этот (меньший больший) квадрат, описывать удаленность границ интервала от точки х, а границы при этом получать кратными разным делителям?
Поясним ситуацию примерами.
Пример 3. (Получение нового квадрата многократным увеличением х2, суммируя с модулем). Задаем составной модуль N = 119. В упорядоченной последовательности Z целых чисел выделяем фрагменты слева и справа от нуля. Как и ранее, построим многострочную модель числа N = 119, в рамках которой выделим тривиальную область КВВ = КВК. Первое число х, квадрат которого превышает N равно х = 11. Его квадрат 112 = 121, а КВВ = 112 – 119 = 2. Такой квадрат не обеспечивает построение РИ, так как, например, Гл = хц – k = 11 – 11 = 0 условие кратности делителю не выполнено.
Может ли этот х = 11 быть центром РИ? Чтобы это случилось, надо для х = 11 найти соответствующий квадрат, который задаст удаленность k границ от х = 11, содержащих кратные разных делителей.
Построим РИ с центром в х = 11. Для этого к вычету КВВ = 2 будем многократно суммировать модуль N = 119, пока не получим новый квадрат 2 +119 + 119 + …+ 119 = 2025.
Такой квадрат существует и получается на 17-м шаге суммирования.
Вычисляем в цикле по i с проверкой получения квадрата на каждом шаге.
i = 1, 2+119 =121, Значение 121 не создает РИ, но его можно увеличивать до нового квадрата.
i = 2, 121+119 = 240 = ⃞?НЕТ; i = 3, 240 + 119 = 359 = ⃞?НЕТ; i = 4, 359+119 = 478 = ⃞?НЕТ
i = 5, 478 +119 = 597= ⃞? НЕТ; i =6, 597 +119 = 716 = ⃞? НЕТ; i = 7, 716+119 = 835 = ⃞?НЕТ
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
i =15,1668+119=1787= ⃞? НЕТ; i =16,1787+119=1906 = ⃞?НЕТ; i =17,1069+119=452 = ⃞?ДА.
В точке х = 11 мы нашли новый квадрат. Вычислим удаленность k границ и сами границы РИ:
k = 45; границы получились кратными разным делителям:
Гл = хц – k = 11 – 45 = – 34 = (-2)˖17,
Гп = хц + k = 11 + 45 = 56 = 8˖7.
Все получилось, но левая граница РИ имеет отрицательное значение (знак – припишем коэффициенту). Этот РИ не принадлежит НРЧ (коэффициент – 2 < 0), но принадлежит ряду целых чисел.
Пример 4. (Получение нового квадрата многократным вычитанием модуля из х2). Зададим составной модуль N =119, и х = 106, КВВ(х) = 50. Возводим хц в квадрат 1062 = 11236 > N. Такой квадрат не обеспечивает построение РИ, так как Гл= хц – k = 106 –106 = 0.
Будем уменьшать квадрат с проверкой результата 11236 –119 –119 – … –119 = 3025 = 552 пока не получим новый меньший квадрат. На 69-м шаге получаем новый меньший квадрат
хm2 = 3025 = 552. Этот же квадрат можно получить быстрее, многократно добавляя модуль к вычету25 раз. Проверим кратность делителям границ интервала с центром в точке х = 106,
Гл = хц – k = 106 – 55 = 51 = 3˖17,
Гп = хц + k = 106 + 55 = 161 = 23˖7.
Из примера следует: точка х = 106 является центром РИ, границы РИ кратны делителям N,
полученный в центральной точке другой квадрат (меньший) k2 = 3025<1062, описывает удаленность границ от центра РИ.
И более общий вывод: построение решающих интервалов возможно в других точках фрагмента, кроме тех, что имеют КВВ = КВК. Если в качестве носителя ЗРД рассматривать РЦЧ, то все расчеты и результаты допустимы.
В отличие от прежней версии ЗРД число РИ увеличилось, а ранее исключенный элемент
х = 11 стал центром нового РИ.
Границы интервалов содержат значения кратные разным делителям с целочисленными коэффициентами. Положительный ответ получаем и на более ранний вопрос – элемент х = 11 может быть центром решающего интервала, если в качестве носителя ЗРД выбрать не НРЧ, а последовательность целых чисел, так как в НРЧ отрицательные значения элементов недопустимы.
Важно отметить, что разность квадратов 452 – 112 для элемента х = 11 должна нацело делиться на модуль N, т.е. быть кратной модулю N, а именно, 452 – 112 = 1904 = 16·119.
Из этого следует, что квадрат числа 45 можно получить чисто формальным путем, а именно, последовательным увеличением значения 121, квадрата числа (х = 11) на N = 119. Это как бы операция приведения по модулю «наоборот» не уменьшением, а увеличением.
Продолжая получение квадратов для х = 12, 13, 14, 15, 16, 17, 18, 19 и т.д., спросим, могут ли эти значения быть центрами РИ, и если да, то как это обеспечивается?
В точке х = 122 = 144 просто используем редукцию по модулю N, 144 – 119 = 52;
Вычисляем границы Гл =12 – 5 = 1 ·7; Гп = 12 + 5 = 1·17;
В точке х = 132 = 169; 169 + 119 +119 +…+119 = 3025 = 552 и 3025 –169 = 24·119;
Вычисляем границы Гл =13 – 55 = – 42 = (–6) ·7; Гп =13 + 55 = 68 = 4·17;
В точке х = 142 = 196; 196 + 119 +119 +…+119 = 11025 =1052 и 11025 – 196 = 91·119;
Вычисляем границы Гл =14 – 105 = – 91 = (–11) ·7; Гп =14 + 105 = 119 = 1·119;
В точке х = 152 = 225; 225 + 119 +119 +…+119 = 1296 =362 и 1296 – 196 = 1071 = 9·119;
Вычисляем границы Гл =15 – 36 = – 21 = (–3) ·7; Гп = 15 + 36 = 51 = 3·17;
В точке х = 162 = 256; 256 + 119 +119 +…+119 = 1089 =332 и 1089 – 256 = 833 = 7·119;
Вычисляем границы Гл =16 – 33 = – 17 = (–1) ·17; Гп = 16 + 33 = 49 = 7·7;
В точке х = 172 = 289; 289 + 119 + +…+119 = 10404 =1022 и 10404 – 289 =10115 = 85·119;
Вычисляем границы Гл =17 – 102 = – 85 = (–5) ·17; Гп = 17 + 102 = 119 = 1·7·17;
В точке х = 182 = 324; 324 + 119 + 119+…+119 = 2704 =522 и 2704 – 324 =2380 = 20·119;
Вычисляем границы Гл =18 – 52 = – 34 = (–2) ·17; Гп = 18 + 52 = 70 = 10·7;
В точке х = 192 = 361; используем редукцию по модулю N, 361 – 3· 119 = 4 в точке хц.
Эти примеры иллюстрируют возможности расширенной версии ЗРД числа.
Заключение
Новая версия ЗРД распространяет действие закона на ряд целых чисел. Расширяет возможности построения решающих интервалов в текущих точках РЦЧ. Для этого в этих точках вычисляются новые квадраты, определяющие удаленность границ РИ от его центра.
Первая версия ЗРД с учетом ограничений, накладываемых на переменные натуральным рядом чисел (НРЧ) служит частным, более простым, случаем новой версии
Литература на русском языке
1. Коблиц Н. Курс теории чисел и криптографии — 2-е издание — М.: Научное издательство ТВП, 2001. — 254 с. — ISBN 978-5-85484-014-9, 978-5-85484-012-5
2. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии — М.: МЦНМО, 2002. — 104 с. — ISBN 978-5-94057-060-8
3. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с. — ISBN 978-5-94057-103-2
4. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие — Казань: Казанский университет, 2011. — 190 с.
5. Нестеренко А. Ю. Теоретико-числовые методы в криптографии — М.: Московский государственный институт электроники и математики, 2012.–224 с.–ISBN 978-5-94506-320-4
6. Кнут, Д. Искусство программирования = The Art of Computer Programming. — Москва: Вильямс, 2007. — Т. 2. — 832 с. — ISBN 978-5-8459-0081-4.
7. Введение в криптографию / Ященко, В. В.. — Москва: МЦНМО, 1999. — 272 с. — ISBN 5-900916-40-5.
8. Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — Москва: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
на английском языке
Bressoud, D. M. Factorization and Primality Testing. — N. Y.: Springer-Verlag, 1989. — 260 p. — ISBN 0-387-97040-1.
Mahoney, M. S. The Mathematical Career of Pierre de Fermat. — 2. — Princeton: Princeton Univercity Press, 1994. — P. 324—332. — 438 p. — ISBN 0-691-03666-7
Автор: VAE
