Существующие подходы к решению задачи факторизации больших чисел (ЗФБЧ), интенсивно используемые в мире математики последние 20-30 лет свидетельствуют, что для них эта задача достаточно сложная, она упорно сопротивляется внешнему натиску специалистов и позиций не сдает. Вместе с тем, не могу упомянуть работ, авторы которых предложили бы глубокий анализ проблемы, состояния вопроса или выступили бы с критикой используемого подхода. Основной принцип в подходе — просеивание множества чисел (принцип решета) доминирует в этой области, но думается это не единственный путь [7,8] и возможно не лучший. Большие надежды исследователями ЗФБЧ возлагаются на вычислительные средства новых типов, на новых физических принципах (квантовые, молекулярные и др.), но о смене подхода речь не идет [10,11]. Тем не менее, некоторые выводы уже сегодня как бы напрашиваются сами собой.
Таблица тестовых RSA-чисел, опубликованная в 1991 году, пока далека от завершения. Опубликованные результаты факторизации части RSA-чисел из таблицы позволяют заключить, что применяемые методы решения ЗФБЧ построены с использованием свойств чисел, непосредственно зависящих от разрядности (длины) чисел. Чем короче было число, тем меньшим оказалось время (в годах), затраченное на факторизацию. Второе, что обращает на себя внимание — это изолированное, автономное рассмотрение факторизуемого числа. Ситуация сейчас воспринимается так, что число N существует как бы само по себе, а не выбрано из стройной, хорошо организованной структуры, его связи со средой оборваны, что свойства, присущие числу, не наследуют свойств среды окружения и местоположения числа в среде.
Маленький пример демонстрирует наличие таких связей ближнего действия. Для произвольных трех смежных чисел одно из них всегда кратно трем, а произведение крайних чисел всегда равно квадрату среднего без единицы х =24963 = 157∙159. Положение числа 158 между 157 и 159 позволяет легко факторизовать число х. Чтобы успешно преодолеть кризис в области факторизации необходимо рассматривать и другие подходы, методы решения ЗФБЧ в которых базировались бы на свойствах чисел, слабо зависящих или вообще не зависящих от разрядности числа. Эти подходы связаны с разработкой моделей числовых систем в целом и моделей отдельных чисел в таких системах.
Среди известных моделей НРЧ [1-4,12] спираль (рис. 1) математика Станислава Улама (1909 -1984) занимает заметное место Она замечательна простотой своего строения и оставляет незабываемое впечатление от первого знакомства с ней и ее восприятия. По существу модель — это клетки, оцифрованные числами натурального ряда, располагаемые витками в следующем порядке. На середине бумажного листа (см. рис. 2) в клетку вписывается 1, справа от нее 2, сверху 3, влево 4, 5, вниз 6,7, вправо 8,9 и число 10, которое начинает новый виток спирали. Каждый новый виток назовем его "контур" увеличивает свою длину на 8 клеток по отношению к предшествующему. Дальше как бы продолжая ленту шириной в клетку впритык виток за витком против часовой стрелки накручиваются геометрические квадраты — контуры модели. Каждый контур (квадрат) будем снабжать порядковым номером k, начиная от центра, k = 1,2,3,… Клетки с четными и нечетными числами располагаются в спирали подобно клеткам шахматной доски. Диагонали четных и нечетных чисел чередуются друг с другом.
Удивительно, но такая простая закрутка спирали вводит весьма жесткий порядок в организацию чисел, размещаемых в клетках модели. Внешние признаки такого порядка обращают на себя внимание сразу, а что внутри ...?
Замечательными особенностями модели являются, во-первых, то, что модель полная — все числа натурального ряда отображены в клетках спирали, во-вторых, все клетки, содержащие числовые квадраты, выстраиваются вдоль одного направления (вдоль одной линии, проходящей через центр), в-третьих, все числовые квадраты еще и разделяются на четные квадраты по одну сторону от центра, нечетные — по другую; в-четвертых, от центрального контура k = 1 отходят вертикальные и горизонтальные лучи, а также нечетные диагонали, образованные клетками, в которых не содержатся простые числа. Эти лучи уходят в бесконечность и содержат только составные числа.
Сам С. Улам отметил темной заливкой клетки, содержащие простые числа, и получил картину (рис.1) весьма похожую с космической высоты на многомиллионный город с его кварталами и проспектами. Кому-то, возможно, картина представляется похожей даже на звездное небо, но обилие отрезков прямых линий и фигур с прямыми углами несколько нарушают такое сходство. При разглядывании спирали напрашивается вывод, что простых чисел не так уж и мало, а их плотность на единицу площади, если и убывает с удалением от центра, то убыль визуально не ощущается
-spiral-ulama.png "МОДЕЛЬ НАТУРАЛЬНОГО РЯДА ЧИСЕЛ (НРЧ). СПИРАЛЬ УЛАМА")
Рисунок 1 — Представление спиралью фрагмента натурального ряда с закрашенными клетками для простых чисел (200х200 клеток)
Разными авторами в разное время предпринимались попытки модифицировать внешний вид спирали Улама. В центр спирали встраивался нуль, в частности, проводились исследования шестиугольной числовой спирали. Кроме того, предпринимались попытки представить трехмерный аналог спирали Улама. Так демонстрировалась числовая «спираль» в виде плоского треугольника, вдоль высоты, которого выстроились целые квадраты. Иллюстрировался конус, как результат «склеивания» боковых сторон треугольника, имеющих одинаковые числовые значения. Отметим, что такой способ представления усиливает наглядность, то есть позволяет единым взглядом охватить чисел больше, чем просто на числовой прямой.
При манипулировании [5-6] с простыми числами полезно располагать сведениями о некоторых их свойствах и зависимостях. Например, то что квадраты простых, например p и q чисел, кроме 2, при сравнении по модулю 8 имеют всегда вычет 1, р² ≡ 1(mod8), а по модулю 30 таких вычетов может быть только два: р² ≡ 1(mod30) или q² ≡ 19(mod30). Приведем более подробные сведения о числе 30, которые кое-что проясняют относительно загадочности в поведении простых чисел и их квадратов Это число 30 = 2•3•5 играет заметную роль при изучении простых натуральных чисел.
Натуральные числа могут быть представлены такой моделью:
30k, 30k±1, 30k±2, 30k±3,...,30k±15, k=1(1)∞ из них простые числа представляются только в виде 30k±1, 30k ±7, 30k±11, 30k±13.
Число 30 самое большое число, для которого все взаимно простые с ним и меньшие его числа являются простыми. Числу 30 предшествует с таким же свойством число 24, которое также играет в теории существенную роль.
Так, Евклид доказал, справедливость соотношения для простых чисел р(n+1) < p(1)•p(2)•p(3)•...•p(n), где величины в скобках обозначают порядковые номера простых чисел. Это достаточно грубая оценка. Позже было показано, что при n > 4, p(n+1)² < p(1)p(2)p(3)...p(n), т.е. уже для p(5)² = 11² = 121< p(1)p(2)p(3)p(4)=2•3•5•7 =210;
p(5) =11< √(p(1)p(2)p(3)p(4))=√(2•3•5•7) =√210. Это существенно улучшенная оценка.
Теперь о числе 24. Покажем, что при простых числах p, q > 3 разность квадратов двух простых p² — q² всегда делится на 24. Рассмотрим две тройки смежных чисел (р-1)р (р+1) и тройку (q-1)q(q+1), где р и q простые. В каждой тройке одно из чисел кратно трем и это не р и не q. Следовательно, кратны трем оба произведения (р -1)(р+1) и (q -1)(q+1), которые образованы парами последовательных четных чисел. Но для таких чисел известно, что одно из них кратно двум, а другое четырем. Отсюда следует, что произведения делятся на 8. Но они делятся и на три. Тогда каждое из произведений делится на 24. Разность скобок (р -1)(р+1) — (q -1)(q+1) также должна делится на 24, а это и есть разность квадратов p² — q². Знание этого факта позволяет при одном известном квадрате тестировать другой. Это не исключает кратности разности квадратов обычных нечетных чисел числу 24, например, 225 — 81 =144 = 6•24, но не гарантирует ее 1225 — 441 = 484 ≠ 24k, для разности квадратов обычного нечетного и простого чисел 225 — 49 = 176 ≠ 24k. Для квадратов простых это гарантируется.
Введение координатной системы. Для практической работы с моделью и ее элементами желательно иметь возможность выделения любой отдельной клетки двумя координатами (х1, х2) или их группы, и установления в клетке приписанного ей из НРЧ числового значения N(х1, х2), как функции этих координат. Также желательно иметь возможность решать и обратную задачу — по заданному значению N(х1, х2) натурального числа в произвольной клетке иметь возможность определять ее положение в модели, т. е. ее координаты.
Покажем здесь как решается подобная задача. Модель в целом представляет собой дискретную плоскость, ее хорошо различимыми элементами (точками, группами точек) будем рассматривать отдельные клетки и контуры из клеток. Заметим, что каждый контур всегда содержит пару клеток, заполненных квадратами разной четности. Примем за начало контура его клетку с нечетным квадратом. Этот квадрат назовем левой границей k-го контура — наименьшее число в контуре. Обозначим границы контура символами Гл(k) — левую (меньшую) и Гп(k) — правую (большую). Длиной контура 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.
Длины всех последовательных контуров модели образуют геометрическую прогрессию с разностью d = 8 и начальным членом а = 8.
Система координат модели. За начало координат примем центральную клетку с единицей.В плоскости положение каждой точки однозначно описывается двумя координатами. Назначение координат — локализация точки. Удобно такую локализацию точки выполнить вначале с точностью до контура, а затем в пределах фиксированного контура — с точностью до клетки. Координаты не обязательно должны быть декартовыми. При таком подходе роль первой координаты отведем номеру контура (х1 = k). Роль второй координаты х2, определяющей положение клетки в контуре, — отведем расстоянию (удаленности) клетки от начала контура.
Пример 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.
  Теперь более внимательно присмотримся к лучам, выходящим из центральной части и другим которые упоминались ранее и не содержащим клеток с простыми числами
Назовем вертикальные и горизонтальные линии спирали «магистралями», а простые числа в их клетках «светофорами», ограничивающими скорость движения вдоль линий. Тогда на спирали можно указать специфические «скоростные» магистрали, идущие в направлении от центра в четырех направлениях: «Север – Юг» и «Запад – Восток», совсем не содержащие светофоров. Клетки этих магистралей заполняются только составными числами, т. е. не содержат простых. Сам по себе факт достаточно замечательный и даже удивительный, возможно, содержит «намек» на природу и распределение простых чисел в НРЧ. Еще более удивительно то, что на Юг и Восток магистрали содержат по две смежные полосы, а на Север и Запад по одной. В пределах k-го контура обозначим клетки, принадлежащие магистралям символами сторон света: С(k) — северная магистраль; З(k) — западная магистраль; Ю1(k) — южная первая магистраль и Ю2(k) — южная вторая магистраль; B1(k) — восточная первая магистраль и B2(k) — восточная вторая магистраль.
-spiral-ulama-2.png "МОДЕЛЬ НАТУРАЛЬНОГО РЯДА ЧИСЕЛ (НРЧ). СПИРАЛЬ УЛАМА")
Рисунок 2 -Модель НРЧ и увеличеный фрагмент центральной части спирали
На рисунке 2 просмотр большего фрагмента (399х399 клеток) представления в уменьшенном виде дает возможность убедиться в том, что расширение границ модели в сущности мало меняет общую картину. Из этого рисунка мы вырезаем центральную часть 19х19 = 361 число и приводим справа увеличенный фрагмент с заполнением клеток числами. На рисунке (с числами) даже в ограниченном объеме хорошо просматриваются полосы (магистрали), не содержащие закрашенных клеток.
Это наблюдение над магистралями приводит к определенному выводу относительно простых чисел близнецов. В каждом контуре существуют позиции (клетки), которые не могут быть заняты числами близнецами. Например, пара простых близнецов не может быть в клетках обочин двойной магистрали, а это четыре подряд следующие клетки и две из них нечетные. Между близнецами (Р >7) всегда должна быть клетка с четным числом. Значения четверки таких чисел для любого контура определяются однозначно.
Теоретически магистрали из трех полос маловероятны, так как полоса перпендикулярного к магистралям направления (как и все другие) в трех смежных клетках содержит смежные натуральные числа. Среди таких чисел одно из трех всегда кратно трем, т. е. составное, а два из них либо четные, либо нечетные. Пусть кратное трем число в клетке на обочине двухполосной магистрали. Тогда четвертое число в контуре через две клетки также будет кратно трем.Следовательно, через две клетки от числа клетка на другой обочине содержит также составное число, которое в каком-то положении может оказаться простым. Четные и нечетные числа в клетках двухполосной магистрали размещаются в шахматном порядке и, видимо, существует закон управляющий заполнением нечетных клеток магистралей, исключающий появление в них простых чисел.
Пары нечетных чисел в смежных клетках разных магистралей оказываются кратными последовательно возрастающим 3,5,7,9,… нечетным числам:
(27,51):3; (85,125):5; (175,231):7 ;(297, 369 ):9......(восточное направление); 51 =27 + 24; 125 = 85 +40; 231 = 175 + 56; 369=297 +72 прирост значений кратен числу 8 с кратностью-делителем чисел.
(21,45):3;(75,115):5; (161,217):7; (279,351): 9; …(южное направление).
Описание всего бесконечного множества клеток магистралей оказывается более простым, чем для клеток вне магистралей. Одной координаты – номера контура k спирали достаточно, чтобы определить число в клетке магистрали, принадлежащее заданному номером k контуру. При этом используются следующие зависимости (см. таблицу).
Таблица. Расчетные характеристики клеток магистралей спирали Улама
-spiral-ulama-3.bmp "МОДЕЛЬ НАТУРАЛЬНОГО РЯДА ЧИСЕЛ (НРЧ). СПИРАЛЬ УЛАМА")
Формулы, приведенные в таблице, гарантируют при задании номера k контура неограниченное продолжение полос с сохранением отмеченных свойств полос и чисел в них. Особенно важным свойством представляется свойство делимости нечетных чисел в клетках, формирующих полосы. В каждом контуре при заданном его номере k по формулам из таблицы определяются значения чисел в шести клетках пересечения магистралей с контуром. Все эти числа, назовем их реперами , составные и их делители известны. Формулы, приведенные в таблице уже содержат описания каждого делителя. Другие числа k-го контура также можно подвергнуть процедуре факторизации при выполнении некоторых условий.
К таким условиям отнесем следующие. Испытуемое число отличается от репера на величину кратную меньшему или большему делителю. Для таких чисел факторизация выполняется без проблем. Важным представляется свойство делимости нечетных чисел в клетках, формирующих полосы.
Помимо рассмотренных магистралей существуют линии (диагонали) нечетных чисел также не содержащие простых чисел. Во-первых, такая нечетная диагональ — диагональ нечетных квадратов. К ней до и после нее прижаты четные диагонали, которые с очевидностью простых чисел не содержат. В каждом контуре при этом появляются по три смежных клетки без простых чисел. Во-вторых, еще три смежные клетки без простых чисел в каждом контуре появляются по соседству с диагональю четных квадратов. Этой диагонали предшествует нечетная диагональ, в которой как мы сейчас покажем все клетки заняты составными числами. Значения в клетках этой диагонали равны четному квадрату (2k)² — 1 без единицы. Но такое соотношение всегда раскладывается в произведение двух скобок — сумма с единицей на разность с единицей первой степени четного квадрата контура, (2k +1)(2k — 1 )
Пример 2 . Пусть задано число N = 4294967297 = F5. Требуется определить его положение в модели, т. е. (х1, х2) координаты клетки с этим числом, а также значения шестерки чисел на магистралях: С =; В1 =; В2 =; Ю1 =; Ю2 =; З =;
Решение. Извлекаем квадратный корень из числа N и округляем его до меньшего нечетного числа. Значение извлеченного квадратного корня равно 65536,0000076 Меньшее ближайшее целое число 65536 = 2k, (отсюда x1 = k = 32768) четное число, меньшее него нечетное число 65536 — 1 = 65535. Это число нечетное и клетка, содержащая его квадрат 4294836225 является начальной клеткой контура, содержащего число
N = 4294967297. Вторая координата х2 = 4294967297 — 4294836225 = 131072.
Клетки магистралей С = 4294934528; З = 4295000064; Ю1 = 4295065599; Ю2 = 4295065600;
В1 = 429 486 8991; В2 = 4294868992.
Число перед четным квадратом (2k)² — 1 = (2k +1)(2k — 1 ) = 65535х65537 = 4294967295; число за четным квадратом составное (2k)² + 1 = 641х6700417.
Список публикаций
1. Василенко О.Н. Теоретико-численные алгоритмы в криптографии.-М.: МЦНМО,2003.-326с.
2. Ваулин А.Е. Новый метод факторизации больших чисел в задачах анализа и синтеза двухключевых криптографических алгоритмов. Ч.1.// Информация и космос, 2005, №3. – С. 74 –78.
3. Ваулин А.Е. Новый метод факторизации больших чисел в задачах анализа и синтеза двухключевых криптографических алгоритмов. Ч.2.// Информация и космос, 2005, №4. – С. 108 – 113.
4. Стечкин Б.С., Матиясевич Ю.В. Сито Эратосфена // Труды международной школы С.Б. Стечкина по теории функций. — Екатеринбург, 1999. – с. 148.
5. Трост Э. Простые числа. — М.: ГИФМЛ,. 1959. — 136с.
6. Карпенко А.С. Логика Лукасевича и простые числа.- М.: Наука, 2000.-319с.
7. Касселс Дж. В. С. Введение в геометрию чисел. – М.: МИР, 1965. – 430 с.
8. Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы. – М.: Виль-ямс, 2000. 3-е издание. – 280 с.
9. Коблиц Н. Курс теории чисел и криптографии. — М.: Научное издательство ТВП, 2001. — 254 с.
10. Коваленко Д.В., Сидоров Д.П. Факторизация больших чисел распределенными вычислениями // Материалы научной конференции «XXX Огаревские чтения» (естественные и технические науки), Саранск, 2001. — С. 230-232.
11. Коваленко Д.В., Сидоров Д.П., Федосин С.А. Применение распределенных вычислительных систем для факторизации больших чисел // Тезисы международного семинара «Супервычисления и математическое моделирование», Саров, 2002. – С. 53-56.
12. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. Казань: Казан. ун-т,2011.-190с.
Автор: VAE
