Существующие подходы к решению задачи факторизации больших чисел (ЗФБЧ), интенсивно используемые в мире математики последние 20-30 лет свидетельствуют, что для них эта задача достаточно сложная, она упорно сопротивляется внешнему натиску специалистов и позиций не сдает. Вместе с тем, не могу упомянуть работ, авторы которых предложили бы глубокий анализ проблемы, состояния вопроса или выступили бы с критикой используемого подхода. Основной принцип в подходе — просеивание множества чисел (принцип решета) доминирует в этой области, но думается это не единственный путь и возможно не лучший. Большие надежды исследователями ЗФБЧ возлагаются на вычислительные средства новых типов, на новых физических принципах (квантовые, молекулярные и др.), но о смене подхода речь не идет. Тем не менее, некоторые выводы уже сегодня как бы напрашиваются сами собой. В атаках на RSA-подобные шифры ЗФБЧ является основной задачей.
Таблица тестовых RSA-чисел, опубликованная фирмой RSA в 1991 году, пока далека от завершения. Опубликованные результаты факторизации части RSA-чисел из этой таблицы позволяют заключить, что применяемые методы решения ЗФБЧ построены с использованием свойств чисел, непосредственно зависящих от разрядности (длины) чисел. Чем короче было число, тем меньшим оказалось время (в годах), затраченное на факторизацию.
Второе, что обращает на себя внимание — это изолированное, автономное рассмотрение факторизуемого числа. Ситуация сейчас воспринимается так, что число N существует как бы само по себе, а не выбрано из стройной, хорошо организованной структуры, его связи со средой оборваны, свойства, присущие числу, не наследуют свойств среды окружения и местоположения числа в среде.
Небольшой пример демонстрирует наличие таких связей ближнего действия. Для произвольных трех смежных чисел одно из них всегда кратно трем, а произведение крайних чисел всегда равно квадрату среднего числа без единицы, х =24963 = 157∙159 . Положение числа 158 между 157 и 159 позволяет легко факторизовать число х.
Чтобы успешно преодолеть кризис в области теории факторизации необходимо рассматривать и другие подходы, методы решения ЗФБЧ в которых базировались бы на свойствах чисел, слабо зависящих или вообще не зависящих от разрядности числа. Эти подходы связаны с разработкой моделей числовых систем в целом и моделей отдельных чисел в рамках таких систем.
Описание модели НРЧ и ее особенности. Среди известных моделей НРЧ спираль (рис. 1) математика Станислава Улама (1909 -1984) занимает заметное место Она замечательна простотой своего строения и оставляет незабываемое впечатление от первого знакомства с ней и ее восприятия. По существу модель — это клетки плоскости, оцифрованные числами натурального ряда, располагаемые витками в следующем порядке. На середине бумажного листа (см. рис. 2) в клетку вписывается 1, справа от нее 2, сверху 3, влево 4, 5, вниз 6,7, вправо 8,9 и число 10, которое начинает новый виток спирали. Каждый новый виток назовем его "контур" увеличивает свою длину на 8 клеток по отношению к предшествующему. Дальше как бы продолжая ленту шириной в клетку впритык виток за витком против часовой стрелки накручиваются геометрические квадраты — контуры модели. Каждый контур (квадрат) будем снабжать порядковым номером k, начиная от центра спирали,k = 1,2,3,.... Клетки с четными и нечетными числами располагаются в спирали подобно клеткам шахматной доски. Диагонали четных и нечетных чисел чередуются друг с другом.
Удивительно, но такая простая закрутка линейного списка в спираль вводит весьма жесткий порядок в организацию чисел, размещаемых в клетках модели. Внешние признаки такого порядка обращают на себя внимание сразу, а что внутри ...?
Выяснение этого вопроса и многих других требует наличия инструментария для работы с элементами и объектом НРЧ в целом. Целью предлагаемой работы и является подготовка, создание такого инструментария.
Замечательными особенностями модели являются, во-первых, то, что модель полная — все числа натурального ряда отображены в клетках спирали, во-вторых, все клетки, содержащие числовые квадраты, выстраиваются вдоль одного направления (вдоль одной линии, проходящей через центр), в-третьих, все числовые квадраты еще и разделяются на четные квадраты по одну сторону от центра, нечетные — по другую; в-четвертых, от центрального контура k = 1 отходят вертикальные и горизонтальные лучи, а также нечетные диагонали, из них некоторые образованы клетками, в которых не могут содержаться простые числа. Клетки этих лучей и диагоналей уходят в бесконечность и содержат только составные числа.
Сам С. Улам отметил темной заливкой клетки, содержащие простые числа, и получил картину (рис.1) весьма похожую с космической высоты на многомиллионный город с его кварталами и проспектами. Кому-то, возможно, картина представляется похожей даже на звездное небо, но обилие отрезков прямых линий и фигур с прямыми углами несколько нарушают такое сходство. При разглядывании спирали напрашивается вывод, что простых чисел не так уж и мало, а их плотность на единицу площади, если и убывает с удалением от центра, то убыль визуально не ощущается
Рисунок 1 — Представление спиралью фрагмента натурального ряда с закрашенными клетками для простых чисел (200х200 клеток)
Разными авторами в разное время предпринимались попытки модифицировать внешний вид спирали Улама. В центр спирали встраивался нуль, в частности, проводились исследования шестиугольной числовой спирали. Кроме того, предпринимались попытки представить трехмерный аналог спирали Улама. Так, например, демонстрировалась числовая «спираль» в виде плоского треугольника, вдоль высоты, которого выстроились целые квадраты. Иллюстрировался конус, как результат «склеивания» боковых сторон треугольника, имеющих одинаковые числовые значения. Отметим, что такой способ представления усиливает наглядность, то есть позволяет единым взглядом охватить чисел больше, чем просто на числовой прямой. Но в таких работах нет cредств изучения, исследования модели.
Одной из целей автора являлось стремление использовать, вскрыть закономерность появления
простых чисел, сделать ее наглядной и удобной для дальнейшей работы с моделью.
Введение координатной системы. Для практической работы с моделью и ее элементами желательно иметь возможность выделения любой отдельной клетки двумя координатами (х1, х2) или их группы (контура), и установления в клетке с заданными координатами приписанного ей из НРЧ числового значения N(х1, х2), как функции этих координат. Также желательно иметь возможность решать и обратную задачу — по заданному значению N(х1, х2) натурального числа в произвольной клетке иметь возможность определять ее положение в модели, т. е. ее координаты.
Покажем здесь как решаются подобные задачи. Модель в целом представляет собой дискретную плоскость. Ее хорошо различимыми элементами (точками, группами точек) будем рассматривать отдельные клетки и контуры из клеток, горизонтальные (Г), вертикальные (В), диагональные (Д) линии и лучи.
Заметим, что каждый контур всегда содержит пару клеток, заполненных квадратами разной четности. Примем за начало контура его клетку с нечетным квадратом. Этот квадрат назовем левой границей k-го контура — наименьшее число в контуре. Обозначим границы контура символами Гл(k) = (2k — 1)²- левую (меньшую) и Гп(k) = (2k +1)² — правую (большую).
Длиной контура L(k) будем называть число клеток в нем. Длина контура вычисляется как L(k) = 8∙k, либо как разность значений нечетных квадратов — границ контуров, начинающих пару смежных контуров и всегда кратна 8. Это легко показать, так как следует из того, что квадрат любого нечетного числа 2n+1 имеет вид1 + 8∙Аi , где Аi комбинаторное сочетание по два из n+1. Следовательно, при Аj > Аi разность квадратов двух нечетных смежных (и также не смежных) чисел 1+8∙Аj -1- 8∙Аi = 8∙(Аj — Аi) , кратна числу 8. Полуконтуры образуются делением контура на две части: меньшую m(k) c длиной L(m(k)) = Гц(k) -Гл(k) и большую M(k) c длиной L(M(k)) = Гп(k) -Гц(k) , где Гц(k) = (2k)² — общая граница полуконтуров.
Длины всех последовательных контуров модели образуют бесконечно возрастающую арифметическую прогрессию с разностью d = 8 и начальным членом а = 8.
Система координат модели. За начало координат примем центральную клетку с единицей. В плоскости положение каждой точки однозначно описывается двумя координатами. Назначение координат — локализация точки. Удобно такую локализацию точки выполнить вначале с точностью до контура, а затем в пределах фиксированного контура — с точностью до клетки. Координаты не обязательно должны быть декартовыми. При таком подходе роль первой координаты отведем номеру контура (х1 = k). Роль второй координаты х2, определяющей положение клетки в контуре, — отведем расстоянию (удаленности) клетки от начала контура.
Рисунок 2 -Модель НРЧ и увеличеный фрагмент центральной части спирали
На рисунке 2 просмотр большего фрагмента НРЧ (399х399 клеток), представленного в уменьшенном виде, дает возможность убедиться в том, что расширение границ модели в сущности мало меняет общую картину. Из этого рисунка вырезается центральная часть с числом клеток 19х19 = 361 и приводится справа увеличенный фрагмент с заполнением клеток числами. На рисунке (с числами) даже в ограниченном объеме хорошо просматриваются полосы (магистрали), не содержащие закрашенных клеток.
Это наблюдение над магистралями приводит к определенному выводу относительно простых чисел близнецов. В каждом контуре существуют позиции (клетки), которые не могут быть заняты простыми и числами близнецами. Например, пара простых близнецов не может быть в клетках обочин двойной магистрали, а это четыре подряд следующие клетки и две из них нечетные. Между близнецами (Р >7) всегда должна быть клетка с четным числом. Значения четверки таких чисел для любого контура определяются однозначно.
Пример 1. Пусть задано число N = 39. Требуется определить его положение в модели, т. е. (х1, х2) координаты клетки с этим числом.
Решение. Извлекаем квадратный корень из числа N и округляем его до меньшего нечетного числа. Значение извлеченного квадратного корня равно 6,244. Меньшее ближайшее целое 6 = 2k, четное число, меньшее него нечетное число 6 — 1 = 5. Это число нечетное и клетка, содержащая его квадрат 25 является начальной клеткой контура, содержащего число N = 39. Это самое меньшее число (25) в контуре. Квадрат удвоенного номера контура равен единственному четному квадрату в клетках контура, он получен из числа на единицу большего основания нечетного квадрата в контуре. Отсюда номер контура и первая координата х1 = k = 6/2 = 3 . Анализ ситуации показывает, что число N = 39 вписано в клетке 3-го контура (с номером k = 3) и эта клетка лежит дальше четного квадрата от начальной клетки этого контура. Вторая координата клетки находится как разность значений заданного числа N = 39 и значения нечетного квадрата — начала контура, т. е. х2 = 39 — 25 = 14. Решение получает вид (х1, х2) = (3, 14) .
Решим обратную задачу. Пусть задана своими координатами клетка (х1, х2) = (3, 14). Найти число, вписанное в клетке. Первая координата — номер контура х1 = k = 3. Значение числа в начальной клетке контура находится как нечетный квадрат, определяемый по номеру k из формулы2k-1 = 2∙3 -1 = 5 . Этот квадрат, очевидно, равен 25. Значение числа N в заданной клетке, удаленной от начальной клетки контура на величину х2 = 14, определяется суммой N(х1, х2) = 25 + 14 = 39.
Таким образом, в работе предложен метод, обеспечивающий выделение (локализацию) задаваемой числом N точки НРЧ на плоскостной модели НРЧ, двумя координатами. И решение обратной задачи — по заданным координатам числа N на плоскости находить его значение. Простое решение этих двух задач позволяет выполнять обработку данных в разнообразных задачах, формулируемых относительно натурального ряда чисел. В последующих постах некоторые из таких задач будут предложены вниманию читателей.
Q= [λ]P
• ≠ ≢ ≡ ∄ ℕ ℤ ℝ ℙ ℒ ℂ ℚ ℍ ℘ ā ⊞ ∞ ∩ ∆ ℓ → ≤ ≥ & × Ø φ є ϵ ±
Таблица тестовых RSA-чисел, опубликованная фирмой RSA в 1991 году, пока далека от завершения. Опубликованные результаты факторизации части RSA-чисел из этой таблицы позволяют заключить, что применяемые методы решения ЗФБЧ построены с использованием свойств чисел, непосредственно зависящих от разрядности (длины) чисел. Чем короче было число, тем меньшим оказалось время (в годах), затраченное на факторизацию.
Второе, что обращает на себя внимание — это изолированное, автономное рассмотрение факторизуемого числа. Ситуация сейчас воспринимается так, что число N существует как бы само по себе, а не выбрано из стройной, хорошо организованной структуры, его связи со средой оборваны, свойства, присущие числу, не наследуют свойств среды окружения и местоположения числа в среде.
Небольшой пример демонстрирует наличие таких связей ближнего действия. Для произвольных трех смежных чисел одно из них всегда кратно трем, а произведение крайних чисел всегда равно квадрату среднего числа без единицы,
Чтобы успешно преодолеть кризис в области теории факторизации необходимо рассматривать и другие подходы, методы решения ЗФБЧ в которых базировались бы на свойствах чисел, слабо зависящих или вообще не зависящих от разрядности числа. Эти подходы связаны с разработкой моделей числовых систем в целом и моделей отдельных чисел в рамках таких систем.
Описание модели НРЧ и ее особенности. Среди известных моделей НРЧ спираль (рис. 1) математика Станислава Улама (1909 -1984) занимает заметное место Она замечательна простотой своего строения и оставляет незабываемое впечатление от первого знакомства с ней и ее восприятия. По существу модель — это клетки плоскости, оцифрованные числами натурального ряда, располагаемые витками в следующем порядке. На середине бумажного листа (см. рис. 2) в клетку вписывается 1, справа от нее 2, сверху 3, влево 4, 5, вниз 6,7, вправо 8,9 и число 10, которое начинает новый виток спирали. Каждый новый виток назовем его "контур" увеличивает свою длину на 8 клеток по отношению к предшествующему. Дальше как бы продолжая ленту шириной в клетку впритык виток за витком против часовой стрелки накручиваются геометрические квадраты — контуры модели. Каждый контур (квадрат) будем снабжать порядковым номером k, начиная от центра спирали,
Удивительно, но такая простая закрутка линейного списка в спираль вводит весьма жесткий порядок в организацию чисел, размещаемых в клетках модели. Внешние признаки такого порядка обращают на себя внимание сразу, а что внутри ...?
Выяснение этого вопроса и многих других требует наличия инструментария для работы с элементами и объектом НРЧ в целом. Целью предлагаемой работы и является подготовка, создание такого инструментария.
Замечательными особенностями модели являются, во-первых, то, что модель полная — все числа натурального ряда отображены в клетках спирали, во-вторых, все клетки, содержащие числовые квадраты, выстраиваются вдоль одного направления (вдоль одной линии, проходящей через центр), в-третьих, все числовые квадраты еще и разделяются на четные квадраты по одну сторону от центра, нечетные — по другую; в-четвертых, от центрального контура k = 1 отходят вертикальные и горизонтальные лучи, а также нечетные диагонали, из них некоторые образованы клетками, в которых не могут содержаться простые числа. Клетки этих лучей и диагоналей уходят в бесконечность и содержат только составные числа.
Сам С. Улам отметил темной заливкой клетки, содержащие простые числа, и получил картину (рис.1) весьма похожую с космической высоты на многомиллионный город с его кварталами и проспектами. Кому-то, возможно, картина представляется похожей даже на звездное небо, но обилие отрезков прямых линий и фигур с прямыми углами несколько нарушают такое сходство. При разглядывании спирали напрашивается вывод, что простых чисел не так уж и мало, а их плотность на единицу площади, если и убывает с удалением от центра, то убыль визуально не ощущается
Рисунок 1 — Представление спиралью фрагмента натурального ряда с закрашенными клетками для простых чисел (200х200 клеток)
Разными авторами в разное время предпринимались попытки модифицировать внешний вид спирали Улама. В центр спирали встраивался нуль, в частности, проводились исследования шестиугольной числовой спирали. Кроме того, предпринимались попытки представить трехмерный аналог спирали Улама. Так, например, демонстрировалась числовая «спираль» в виде плоского треугольника, вдоль высоты, которого выстроились целые квадраты. Иллюстрировался конус, как результат «склеивания» боковых сторон треугольника, имеющих одинаковые числовые значения. Отметим, что такой способ представления усиливает наглядность, то есть позволяет единым взглядом охватить чисел больше, чем просто на числовой прямой. Но в таких работах нет cредств изучения, исследования модели.
Одной из целей автора являлось стремление использовать, вскрыть закономерность появления
простых чисел, сделать ее наглядной и удобной для дальнейшей работы с моделью.
Введение координатной системы. Для практической работы с моделью и ее элементами желательно иметь возможность выделения любой отдельной клетки двумя координатами (х1, х2) или их группы (контура), и установления в клетке с заданными координатами приписанного ей из НРЧ числового значения N(х1, х2), как функции этих координат. Также желательно иметь возможность решать и обратную задачу — по заданному значению N(х1, х2) натурального числа в произвольной клетке иметь возможность определять ее положение в модели, т. е. ее координаты.
Покажем здесь как решаются подобные задачи. Модель в целом представляет собой дискретную плоскость. Ее хорошо различимыми элементами (точками, группами точек) будем рассматривать отдельные клетки и контуры из клеток, горизонтальные (Г), вертикальные (В), диагональные (Д) линии и лучи.
Заметим, что каждый контур всегда содержит пару клеток, заполненных квадратами разной четности. Примем за начало контура его клетку с нечетным квадратом. Этот квадрат назовем левой границей k-го контура — наименьшее число в контуре. Обозначим границы контура символами Гл(k) = (2k — 1)²- левую (меньшую) и
Длиной контура L(k) будем называть число клеток в нем. Длина контура вычисляется как L(k) = 8∙k, либо как разность значений нечетных квадратов — границ контуров, начинающих пару смежных контуров и всегда кратна 8. Это легко показать, так как следует из того, что квадрат любого нечетного числа 2n+1 имеет вид
Длины всех последовательных контуров модели образуют бесконечно возрастающую арифметическую прогрессию с разностью d = 8 и начальным членом а = 8.
Система координат модели. За начало координат примем центральную клетку с единицей. В плоскости положение каждой точки однозначно описывается двумя координатами. Назначение координат — локализация точки. Удобно такую локализацию точки выполнить вначале с точностью до контура, а затем в пределах фиксированного контура — с точностью до клетки. Координаты не обязательно должны быть декартовыми. При таком подходе роль первой координаты отведем номеру контура (х1 = k). Роль второй координаты х2, определяющей положение клетки в контуре, — отведем расстоянию (удаленности) клетки от начала контура.
Рисунок 2 -Модель НРЧ и увеличеный фрагмент центральной части спирали
На рисунке 2 просмотр большего фрагмента НРЧ (399х399 клеток), представленного в уменьшенном виде, дает возможность убедиться в том, что расширение границ модели в сущности мало меняет общую картину. Из этого рисунка вырезается центральная часть с числом клеток 19х19 = 361 и приводится справа увеличенный фрагмент с заполнением клеток числами. На рисунке (с числами) даже в ограниченном объеме хорошо просматриваются полосы (магистрали), не содержащие закрашенных клеток.
Это наблюдение над магистралями приводит к определенному выводу относительно простых чисел близнецов. В каждом контуре существуют позиции (клетки), которые не могут быть заняты простыми и числами близнецами. Например, пара простых близнецов не может быть в клетках обочин двойной магистрали, а это четыре подряд следующие клетки и две из них нечетные. Между близнецами (Р >7) всегда должна быть клетка с четным числом. Значения четверки таких чисел для любого контура определяются однозначно.
Пример 1. Пусть задано число N = 39. Требуется определить его положение в модели, т. е. (х1, х2) координаты клетки с этим числом.
Решение. Извлекаем квадратный корень из числа N и округляем его до меньшего нечетного числа. Значение извлеченного квадратного корня равно 6,244. Меньшее ближайшее целое 6 = 2k, четное число, меньшее него нечетное число 6 — 1 = 5. Это число нечетное и клетка, содержащая его квадрат 25 является начальной клеткой контура, содержащего число N = 39. Это самое меньшее число (25) в контуре. Квадрат удвоенного номера контура равен единственному четному квадрату в клетках контура, он получен из числа на единицу большего основания нечетного квадрата в контуре. Отсюда номер контура и первая координата
Решим обратную задачу. Пусть задана своими координатами клетка (х1, х2) = (3, 14). Найти число, вписанное в клетке. Первая координата — номер контура х1 = k = 3. Значение числа в начальной клетке контура находится как нечетный квадрат, определяемый по номеру k из формулы
Таким образом, в работе предложен метод, обеспечивающий выделение (локализацию) задаваемой числом N точки НРЧ на плоскостной модели НРЧ, двумя координатами. И решение обратной задачи — по заданным координатам числа N на плоскости находить его значение. Простое решение этих двух задач позволяет выполнять обработку данных в разнообразных задачах, формулируемых относительно натурального ряда чисел. В последующих постах некоторые из таких задач будут предложены вниманию читателей.
• ≠ ≢ ≡ ∄ ℕ ℤ ℝ ℙ ℒ ℂ ℚ ℍ ℘ ā ⊞ ∞ ∩ ∆ ℓ → ≤ ≥ & × Ø φ є ϵ ±
