Как стать автором
Обновить

Модели натурального ряда чисел и его элементов: Геометрическая (плоскостная) модель натурального ряда

Информационная безопасностьКриптографияАлгоритмыМатематика

   

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

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

Введение

     
Хорошо ли мы знакомы с натуральным рядом чисел? Много ли знаем о нём? Да, это целые положительные числа, которые следуют одно за другим, начинаясь единицей (1) и увеличиваясь на 1 в каждом очередном числе, и так до бесконечности (∞).

Ещё все числа НРЧ делятся на два класса по делимости на 2: четные и нечетные. Единица — нечетное число (нуль не включается в НРЧ), двойка (1 + 1 = 2) — четное, за двойкой — тройка (2 + 1 = 3) — снова нечетное, а за ней следует четная четверка (3 + 1 = 4). Так в НРЧ нечетные и четные числа чередуются.

Числа умноженные на себя — это квадраты в НРЧ. Они занимают свои определенные места в НРЧ, так, что образуют такую же чередующуюся по четности последовательность — нечетный — четный квадрат. Между квадратами соседних чисел разность всегда нечетное число позиций, занимаемых не квадратами. Из этого следует, что сумма 1 + 3 + ...+ 2k — 1 = k2, где k число нечетных, подряд следующих чисел, равна квадрату числа слагаемых. Это неформальное рассмотрение НРЧ.

А как в теории определяется НРЧ? Натуральным рядом чисел называют непустое множество N = {1, 2, 3,...} с унарной операцией S, здесь через S обозначено отображение N в N, удовлетворяющее условиям или следующим аксиомам Пеано:

  1. для любого а ∊ N, 1 ≠ Sа;
  2. для любых а, b ∊ N, если Sа = Sb, то а = b;
  3. любое подмножество N, c 1 ∊ N, которое содержит вместе с каждым элементом а элемент Sа, совпадает с N. Элемент Sа множества N обычно называют элементом, непосредственно следующим за а.


Натуральный ряд чисел представляет собой вполне упорядоченное множество. В теории чисел доказывается, что следующие условия:

  1. а + 1 = Sа, а + Sb = S(а + b);
  2. а · 1 = а, а · Sb = а · b + а,

где а и b — любые элементы из N, определяют во множестве N, бинарные операции (+) и (·).

Система <N, +, ·, 1> является системой натуральных чисел.
Натуральное число — одно из основных понятий математики натуральных чисел и может быть истолковано как кардинальное число непустого конечного множества. Множество N = {1, 2,...} всех натуральных чисел и операции над ними: сложение (+) и умножение (·) образуют систему натуральных чисел <N, +, ·, 1>. В этой системе обе бинарные операции ассоциативны, коммутативны и связаны законом дистрибутивности; 1 — нейтральный элемент умножения, т.е. а · 1 = 1· а = а для любого натурального числа а; сложение не имеет нейтральных элементов и, более того, (а + b) ≠ а для любых натуральных чисел а и b. При этом выполняется аксиома индукции: любое подмножество множества N, содержащее 1 и вместе с каждым элементом а сумму а + 1, совпадает с N.

В дедуктивных научных теориях аксиомами называют основные исходные положения, т.е. аксиомы — это основные положения, самоочевидные принципы. Из аксиом в рамках таких теорий путем дедукции извлекается все их содержание.

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

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

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

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

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

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

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

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

Среди множества возможных моделей НРЧ весьма эффективной представляется следующая, обозначенная как Гs∓. Модель удовлетворяет практически всем требованиям, обычно предъявляемым к ним.

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

  1. Гs∓ — модель содержит все нечетные числа НРЧ, а факторизовать всегда требуется нечетное число, так как четные легко делятся на степени двойки.
  2. Соотношения, реализующие разложение числа на множители – это формулы сокращенных вычислений, суммы и разности одинаковых степеней переменных, среди которых наиболее предпочтительное соотношение: x12 — x02 = (x1 + x0)(x1 — x0)
  3. Все нечетные числа в НРЧ лежат между квадратами чисел разной четности.
  4. Любое составное нечетное натуральное число представимо суммой нечетного числа слагаемых — нечетных последовательных чисел и, возможно, не единственным образом.
  5. Сумма из пункта 4 легко преобразуется в произведение среднего слагаемого (больший делитель N) на число слагаемых (меньший делитель N).
  6. Значение в каждой клетке на пересечении горизонтали и вертикали подмодели Г2- с одной стороны, равно разности квадратов номеров этих линий, а с другой – равно произведению номеров короткой и длинной диагоналей, встречающихся в этой клетке.
  7. Значения чисел в клетках диагоналей кратны номеру диагонали, в которой они лежат.

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

     
Для построения модели на плоскости задаются две пересекающихся ортогональных координатных числовых оси, направленных х1 — вертикально вниз и х0 — горизонтально вправо. Точки осей, равноотстоящие одна от другой, размечаются числами натурального ряда. Пересечение осей помечается нулем. Через размеченные точки проводятся линии, образующие границы полос перпендикулярных направлений. На плоскости возникает рисунок решетки, подобие паркета из клеток размером 1х1. В работе фрагмент плоскости ограничим возможностями рисуночного представления и в нем выделим главную диагональ, подобно главной диагонали числовой матрицы. С каждой клеткой под главной диагональю свяжем значение N(x1, x0) = x12 — x02, а над главной диагональю и на диагонали клеткам припишем значения N(x1, x0) = x12 + x02, где х1 и х0 — координаты клетки (x1, x0).
     

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

Отметим, что клетки такой дискретной плоскости уникальны, а значения в них могут повторяться. При таком определении четность значений в клетках соответствует чередующемуся порядку, как цвет клеток на шахматной доске. Клетки при этом будем называть соответственно четными или нечетными. Клетки, размещаемые под главной диагональю образуют полуплоскость, которую будем называть Г2- (Г от слова гипербола), а над главной диагональю — К = Г2+ (К от слова круг). Обобщенную модель обозначим Гs∓, где s — может принимать значения 2, 3,… и др.



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


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

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

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



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

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

Пусть задано некоторое число N ∊ Г2-, и оно лежит в одной из клеток наклонной прямой (луча), формируемой условиями примера. Тогда можно получить следующее соотношение для модели луча:
при k = 2, имеем N(x1, x0) = x12 — x02 = (kx0)2 — x02 = x02(k2 — 1) = 3x02 . Луч Б3;
при k = 3, имеем N(x1, x0) = x12 — x02 = (kx0)2 — x02 = x02(k2 — 1) = 8x02 . Луч Б8;
при k = 4, имеем N(x1, x0) = x12 — x02 = (kx0)2 — x02 = x02(k2 — 1) = 15x02. Луч Б15;
при k = 5, имеем N(x1, x0) = x12 — x02 = (kx0)2 — x02 = x02(k2 — 1) = 24x02. Луч Б24;

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

Действительно, N(x1,x0) = x12 — x02=(x1+x0)(x1 -x0)= р ∙ q.

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

  1. Выполняется проверка принадлежности заданного числа одному из возможных лучей полуплоскости Г2-. Значение N = 968 проверяем на принадлежность лучу Б3, делим N на 3, число N = 968 не делится нацело на 3, проверяем принадлежность следующему лучу Б8, делим на 8. 968 / 8 = 121 = 112 = х02.
  2. Получили, что число N = 968 лежит в клетке, принадлежащей лучу Б8, и клетка имеет координату х0 = 11. Вторая координата клетки определяется из соотношения модели луча х1 = kx0=3 ∙ 11 = 33. Наличие координат клетки обеспечивает факторизацию числа в ней: N(x1, x0) = x12 — x02=(х10)(х10) = (33+11)(33-11) = 44 ∙ 22 = 968. Факторизация выполнена успешно.


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

  1. Первая же проверка подтверждает принадлежность лучу Б3 клетки с числом N = 507, и дает результат деления 507 / 3 =169 = 132 = х02. Координата клетки х0 = 13. Другая координата х1 = 2х0 = 2 ∙ 13 = 26.
    Эту координату можно находить и другим путем. Он имеет самостоятельное значение (ценность) и применим в других ситуациях. Из общего соотношения N(x1, x0) = x12 — x02 = (kx0)2 — x02 = x02(k2 — 1) = 3x02 = 507.
  2. Находим делением N / 3=507 / 3 = 169 значение x02 и суммированием с N этого квадрата находим квадрат другой координаты x12= N + x02 = 507 + 169 = 676. Откуда х1 = 26 и х0 = 13. Тогда факторизация числа N, представимого разностью квадратов, N = 507 = x12 — x02= (26 — 13)(26 + 13) = 13 ∙ 39 = 507, успешно выполняется и завершается.


Использованные источники


1. Гельфонд А.О., Линник Ю.В. Элементарные методы в аналитической теории чисел. -М.: ГИФМЛ, 1962.-272с.
2. Линник Ю.В. О представлении больших чисел суммою семи кубов, Матем. сб. 12(54),(1943),220-224.
3. Линник Ю.В. О разложении больших чисел на семь кубов, ДАН 36 (1942), 179-180
4. Манин Ю.Н, Панчишкин А.А. Введение в современную теорию чисел. –М.: МЦНМО, 2013. – 552с.
Теги:факторизациямодель НРЧмодель числа
Хабы: Информационная безопасность Криптография Алгоритмы Математика
Всего голосов 7: ↑6 и ↓1 +5
Просмотры3.2K

Похожие публикации

Лучшие публикации за сутки