В очередной работе из цикла статей о натуральном ряде чисел (НРЧ) используются понятия и обозначения Г^2± – модели НРЧ в форме дискретной (из клеток с координатами (х1, хо)) бесконечной плоскости (см.здесь), в которой составное четное или нечетное натуральное число (СННЧ) в каждой клетке модели описывается соотношением N =x1 ² ± xо ². Рассматривается очередное важное для решения задачи факторизации больших чисел (ЗФБЧ) свойство Натурального ряда чисел — кратность клеток модели модулю шифра RSA.

Об алгебраических кольцах и шифре RSA

Шифр RSA и ему подобные в своей основе имеет строгую математическую конструкцию – конечное числовое кольцо вычетов (КЧКВ) по модулю составного числа N = dмdб, где dм – меньший простой делитель, dб – больший делитель.

Требованием к ключу (в частности к модулю N) шифра является то, чтобы оба делителя были простыми числами очень большой разрядности (до 300 десятичных цифр). см.здесь

Другим важным требованием к ключу шифра является требование для разности делителей
|dб – dм| = ?. Она должна иметь столь же высокую разрядность как сами делители. Простым примером КЧКВ может служить начальный фрагмент натурального ряда чисел с добавлением нулевого элемента. Кольцо образуют все числа подряд от 0 до N – 1. Более подробно о кольцах можно прочитать в учебниках по высшей алгебре.

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

Публикуемые алгоритмы для реализации атак на шифр базируются в своей основе на концепции числового решета, предложенного Эратосфеном еще до новой эры. С каждой новой публикацией мы видим несколько улучшенную, усовершенствованную версию алгоритма, но, по-видимому, эти усовершенствования недостаточны для достижения успеха. Идея решета Эратосфена [1] была прогрессивной в его время, но сейчас это не срабатывает.

В сети Интернет имеется список RSA-чисел, которые фирма предлагается факторизовать. Список опубликован в 1991 году, и он пока далек от завершения. Анализ результатов мультипликативного разложения чисел из списка доступен, как и сами числа, открыт для всех.

Из анализа следует, чем больше цифр в описании числа, тем большее время требовалось для его разложения. Напрашивается вывод о том, что для разложения модуля N используются алгоритмы весьма чувствительные к разрядности чисел, т. е. алгоритмы используют свойства чисел, сильно зависящие от их разрядности. Я же имею в виду свойства подобные «признакам делимости» чисел. Они практически от разрядности факторизуемого числа не зависят (см.здесь).

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

Авторы публикаций и владельцы фирмы, т.е. алгоритмов шифрования не отрицают других новых подходов, и не исключают возможности создания новых алгоритмов на новых идеях, перед которыми задача факторизации больших чисел не устоит и ее решение будет успешным. Меня как автора настоящей публикации привлекают как раз новые оригинальные разработки в области решения ЗФБЧ.

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

Вертикали (столбцы) Г^2± – модели НРЧ

Примером такого нового подхода может служить использование сумм пар квадратов чисел. Эти числа берутся из НРЧ и должны удовлетворять требованиям: два числа смежные и их сумма равна составному числу N, которое хотим факторизовать, еще два числа квадраты, удовлетворяющие уравнению N + x1 ² = xо ².

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

Рассмотренная схема оригинальная, отличается от предложенной Л. Эйлером и другими математиками более простым и прозрачным для понимания содержанием.

Пример 1. (Сумма квадратов). Задано составное число N = dмdб = 209723. Требуется найти его мультипликативное разложение, т. е. значения множителей dм и dб.
Решение. Воспользуемся свойствами сумм квадратов в Г²⁺ – гиперболо-круговой модели.

Извлекаем квадратный корень из N, v209723 = 457,955 = 458 и округляем до большего целого.
Далее находим разности последующих квадратов и числа N с проверкой равенства этой разности полному квадрату: 458 ² – 209723 = 41 ? ?, 459 ² – 209723 = 958 ? ?, 460 ² – N ? ?,
461 ² – N ? ?,

462 ² – 209723 = 3721 = 61 ² = ?. На 5-м шаге искомая разность равна полному квадрату. Находим аддитивное разложение N = 209723 = sм + sб = 104861 + 104862 на смежные слагаемые. Проверяем равенство сумм квадратов в клетках модели
N (х11, хо) = N (х11, sм), N (х12, хо2) = N (х12, sб),
где sм, sб – номера столбцов, а х11 и х12 – номера строк, модели. Эти номера определяются из соотношений равенства сумм квадратов.

sм² + 462 ² = 104861 ² + 213444 = 10995829321 + 213444 = 10996042765;
sб ² + 61 ² = 104862 ² + 3721 = 10996039044 + 3721 = 10996042765. Суммы в клетках, как и ожидалось, оказались равными между собой.

Для таких сумм записываем равенство sм² + 462 ² = sб ² + 61 ² и преобразуем его в равенство разностей квадратов 462 ² – 61 ² = sб ² – sм². Справа разность квадратов всегда равна N, а левая разность преобразуется в произведение
462 ² – 61 ² = (462 – 61)(462 + 61) = 401·523 = 209723 = N.

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

Горизонтали (строки) Г^2- – модели НРЧ

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

Одним из свойств строк (горизонталей) Г ^2- – модели НРЧ является линейная зависимость значений каждой клетки последующей строки модели от значений в клетках предыдущей, что выражается простым суммированием значений из клеток верхней из двух смежных строк с постоянным значением из последней клетки нижней строки, то есть
N(х1, хо) = N(х1-1, хо) + N(х1, х1 — 1), хо пробегает при этом всю нижнюю строку (Табл.1)


_{Кликабельно}
Рисунок 1-Значения кратные составным нечетным числам в первой 100 (выделены заливкой)
На рисунке выделены заливкой клетки с числами равными произведению номеров диагоналей.

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

Первое число в качестве модуля N =15. Для него кратная клетка содержит произведение номеров диагоналей 10·6 = 60 = 15·4 кратное модулю с коэффициентом k = 4. Для номеров диагоналей выполняется: 6 ² ? 6(mod15);10 ² ? 10(mod15).

Возьмем второе число в качестве модуля N =35. Для него кратная клетка содержит произведение номеров диагоналей 21·15 = 315 = 35·9 кратное модулю с коэффициентом k = 9. Для номеров диагоналей выполняется: 15 ² ? 15(mod35);
21 ² ? 21(mod35). Так будет для всех чисел N, принадлежащих длинной диагонали Д1, в строке которых указана заливкой кратная N клетка.

Пример 2.(Вычисление кратной клетки). Задан составной модуль КЧКВ N =77. по свойствам 1,2 значение в клетке N(х1 = 39, хо = 17) вычисляется как сумма значений в клетке сверху над заданной и в последней клетке строки х1 = 39 равная модулю КЧКВ.
N(х1, хо) = N(х1 = 39, хо = 17) = N(38, 17) + N(39, 39 – 1) => 1232 = 1155 +77.
N(х1, хо)=N(х1 = 39, хо = 17)=N(38, 17)+ N(39, 39 –1) = 38 ² – 17 ² + 39 ²–38 ² => 1232 = 1155 +77.

С другой стороны, значение в каждой клетке произвольной строки вычисляется как разность квадратов координат клетки или как произведение разности координат клетки на их сумму
N(х1, хо) = N(х1 = 39, хо = 17) = 39 ² — 17 ² = (39 – 17)(39 + 17) = 22·56 = 1232 =16·77.

Существуют и другие менее наглядные способы вычислений значения в клетке.

Рассмотренный пример замечателен тем, что устанавливает формализованную связь рассматриваемой модели с конечным числовым кольцом вычетов по составному модулю.

Известно, что длинная первая диагональ Г^2± – модели НРЧ. содержит в своих клетках все нечетные подряд следующие числа, которые могут рассматриваться как модули приведения алгебраических структур. Сами структуры образованы из элементов – натуральных чисел. Здесь не будем углубляться в понятия высшей алгебры, а укажем только факты интересные с позиций их отображения в Г^{2 -} – модели НРЧ.

Среди всех элементов структуры КЧКВ по модулю N имеется множество И= {x}, которые называются идемпотентами, и квадраты которых после редукции (приведения их по модулю) сохраняют свои значения х ²? х(mod N). Такие элементы называются в теории отображений – неподвижными. Далее будем обозначать идемпотенты символами И1, И2,…

Другой класс элементов множество Н = {x} КЧКВ, называемых инволюциями, обладает следующим свойством х ²? 1(mod N). Далее будем обозначать инволюции символами Н1, Н2,…

Роль таких элементов колец весьма велика при решении прикладных задач и здесь мы рассмотрим отдельные интересные и полезные для решения ЗФБЧ факты. Дело в том, что теория колец не отвечает на вопрос, какие конкретно из элементов кольца являются идемпотентами, какие инволюциями. Как установить эти элементы, как определить их значения, при заданном модуле N кольца.

Оказывается, идемпотенты являются, к тому же, элементами кратными разным делителям модуля N. Их произведение по модулю равно нулю, так как кратно N, но сумма двух идемпотентов равна N + 1. Располагая значением идемпотента, можно решить задачу нахождения наибольшего общего делителя (общего как для модуля, так и для идемпотента).

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

Рассмотренный пример с клеткой, имеющей значение кратное значению в крайней правой клетке строки (кратной клеткой) имеет особенность, состоящую в том, что произведение диагоналей в кратной клетке – это произведение идемпотентов кольца.

Факторизация N с использованием идемпотентов конечного числового кольца

Схемы факторизации СННЧ N. Использование идемпотентов КЧКВ
Все (х1, хо) клетки Г^{2 -} – модели уникальны и объединяются в линии: горизонтали с номерами х1 (они содержат число х1 клеток), вертикали с номерами хо, диагонали: короткие (K) с номерами х1 + хо и длинные (Д) с номерами х1 – хо.

В каждой клетке (х1, хо) модели пересекаются линии названных типов, номера которых определены координатами клетки. В клетках модели могут находиться не любые числа, а только представимые разностями квадратов других чисел (координат).

Горизонталь модели может быть задана ее номером х1, а вертикаль соответственно номером хо. В каждую клетку вписано число N (х1, хо) = х1 ² – хо ². Последние клетки горизонталей образуют длинную диагональ Д1 и содержат значения

N(х1, х1 – 1) = х1 ²– х1 ² + 2х1– 1= 2х1 – 1,

зависящие от номера горизонтали. В клетках этой диагонали содержатся все следующие подряд нечетные числа. Для диапазона чисел [d1min, d1max], d1min, d1max ? Д1, сумма их значений задает аддитивную форму числа N.

Пример 3 (Вычисление значения kN кратной клетки как суммы элементов фрагмента диагонали Д1 )

= 77+75+ 73+ …+ 37+35 = 1232 = 16·77= 22·56,,
где i= 1(1)22.

Последнее означает, что количество слагаемых (22) в сумме равно меньшему делителю
N (х1, хо), а среднее слагаемое (56) – большему делителю N (х1, хо).

Если клетки главной До диагонали Г^{2 ±} – модели с уравнением х1 = хо включить в Г^{2 -} — модель, то значение в них будет равно нулю. Тогда при порождении значений в клетках строки с номером х1 в ее последней клетке получим значение 2х1–1, так как оно суммируется со значением из клетки строки с номером х1–1, находящейся сверху над ней и это значение равно 0. Важными свойствами Г^{2 -} — модели и ее клеток являются следующие.

Свойство 1. Все числа в клетках текущей горизонтали х1 могут быть получены из чисел в соответствующих клетках предшествующей (верхней) горизонтали с номером х1 – 1 путем суммирования их значений с постоянным значением 2х1 – 1.

Таблица 1 – Фрагмент Г^{2 -} — модели из 2-х строк 38-й и 39-й, N = 77



Действительно, N (х1, хо) = N (х1 –1, хо) + 2х1 – 1 = х1 ² – 2х1 + 1+ 2х1 – 1– хо ² = х1 ² – хо ².

Свойство 2. Второе свойство вытекает из первого. Любое число N (х1, хо) в клетке горизонтали с номером х1 может быть получено как сумма значений в клетках фрагмента длинной диагонали Д1, из которых большее d1max – число в последней клетке горизонтали х1, а меньшее d1min – число лежит в клетке пересечения диагонали Д1 с вертикалью хо.

Свойство 3. Для бесквадратного СННЧ N, помещенного в крайнюю правую клетку горизонтали х1, в этой горизонтали найдется клетка, в которой будет помещено число кратное N, т. е. число kN, k > 1. Поиск такой клетки нетривиальная трудно решаемая задача.

Иллюстрацией этого свойства являются данные таблицы 2. Для чисел первой сотни, которые бесквадратные и составные N, размещенные в клетках d1? Д1 со значением 2х1 – 1 указывается другая клетка (х1, хо), содержащая значение N (х1, xо) = kd1 кратное d1.

Таблица 2.


К·Д — произведение диагоналей, пересекающихся в клетке со значением kN.

Свойство 4. Все числа N (х1, хо) в клетках текущей горизонтали х1 могут быть получены как произведения номеров диагоналей а = х1+хо короткой и b = х1 – хо длинной, пересекающихся в этих клетках.

Иллюстрацию свойств удобно выполнить на числовом примере
Пример 4. Будем рассматривать Г^{2 -} – модель. Зададим для факторизации СННЧ N = pq = 7·11 = 77. Это нечетное число и для него в длинной диагонали Д1 имеется клетка, которая лежит в горизонтали с номером х1 = ? (N + 1) = 39.

Само число 77 помещено в последней клетке этой горизонтали, содержащей, как и все другие клетки, разность квадратов координат х1 ² – хо ².

Первая клетка этой горизонтали в вертикали хо = 0 занята числом
х1 ² = 39 ² = 1521. Значение числа в любой промежуточной клетке горизонтали х1 равно, с одной стороны, произведению номеров b = х1 – хо длинной и короткой a = х1 + хо диагоналей, пересекающихся в ней ab = (х1 + хо)( х1 – хо).

С другой стороны – равно разности квадратов номеров горизонтали (для всех клеток горизонтали этот квадрат х1 ² одинаков) и вертикали хо ², также пересекающихся в этой промежуточной клетке, т.е.
N(х1, хо) = х1 ²– хо ².

Кроме этого, все значения в клетках горизонтали х1 (по свойству 1) равны сумме значений N(х1, хо) = N(х1 – 1, хо) + 77 из соответствующих клеток горизонтали с номером х1 – 1, т.е. из верхней над ней и константы, равной N = 77.

Допустим, что в качестве номеров диагоналей выбраны у короткой значение х1 + хо = И1= 56 и для длинной значение х1 – хо = И2 = 22, т.е. значения нетривиальных идемпотентов кольца вычетов по модулю N.

При перемножении нетривиальных идемпотентов в роли диагоналей Г^{2 -} – модели получаем в некоторой клетке горизонтали (с номером х1 = 39) в качестве их произведения число, кратное модулю (77) кольца вычетов, который размещается в последней клетке этой горизонтали, т. е. И1·И2 = 56·22 = kN = 16·77 = 1232.

Также из теории колец известно, что сумма нетривиальных идемпотентов равна И1+ И2 = N+1. Таким образом, относительно неизвестных идемпотентов получаем алгебраическую систему уравнений, которая кроме двух неизвестных идемпотентов содержит еще и третью неизвестную – коэффициент кратности k>1.



К счастью коэффициент k может быть определен вне системы алгебраических уравнений. Допустим, что коэффициент k нами уже определен k = 16.Тогда решаем систему уравнений.



Последнее слагаемое в квадратном уравнении необходимо сделать квадратом числа 39. Для этого добавим в левую и правую части уравнения число 289 = 17 ². Тогда получаем
(И2 — 39) ² = 17 ² или И2 – 39 = ±17 и окончательно, И2 = 17 + 39 = 56 или И2 = 39 – 17 = 22.
Ответ: Идемпотенты равны И2 = 22; И1 = 56 или наоборот: И2 = 56 и И1 = 22.

Теперь вернемся к вопросу определения значения коэффициента кратности k.
Рассмотрим следующий алгоритм определения коэффициента кратности модуля N.

Алгоритм

1. Задано составное число N = 77 – модуль кольца вычетов;

2. Определяем по N значение номера горизонтали x1 = ? (77+ 1) = 39, в первую клетку
которой помещаем квадрат 39 ² = 1521, а в ее последнюю клетку помещаем N = 77;

3. Произведение идемпотентов появляется в промежуточной клетке горизонтали x1 = 39; для этой клетки выполняется то условие, что число в ней равно kN, и оно представимо разностью квадратов натуральных чисел.

4. Следовательно, вычитая многократно из квадрата числа первой клетки горизонтали 39 ² = 1521 последовательно значения хо = 1,2,3,..., определяем каждый раз значение k, и является ли оно целым числом? Как только разность становится кратной N, задача решена: найдено kN.

Рассмотрим также другой алгоритм определения коэффициента кратности модуля N.

1. Задано составное число N = 77 – модуль кольца вычетов;

2. Определяем по N значение номера горизонтали x1 = ? (77+ 1) = 39, в первую клетку
которой помещаем квадрат 39 ² = 1521, а в ее последнюю клетку помещаем N = 77;

3. Произведение идемпотентов появляется в промежуточной клетке горизонтали x1; для этой клетки выполняется то условие, что число в ней равно kN, и оно представимо разностью квадратов натуральных чисел.

Используя свойство 2, число kN можно находить указанным там путем, а именно, суммированием монотонно убывающих нечетных чисел из фрагмента диагонали Д1, начинающегося числом d1max = 77, и завершающегося числом d1min, значение которого априори неизвестно, d1min, d1max ? Д1.

4. Для установления последнего слагаемого после каждого шага суммирования проверяется делимость полученной суммы на N = 77. Решением будет сумма, делящаяся нацело на 77.

Таблица 3 – Числа N кратные 3 на осевой линии (заливкой выделен прогноз)



В этой таблице составные числа (кратные трем) следуют с чередующимися пропусками величиной 6 и 12. Действительно, в строке N имеем 21 – 15 = 6, а 33 – 21 = 12 и далее в таком же порядке. Предположительно пропуски между табличными значениями N вызваны тем, что в шестерке смежных чисел встречаются простые числа-близнецы, например, 16, 17, 18, 19, 20.

Следующее число кратное трем 21 как раз шестое по счету после 15. Либо в 12 подряд следующих чисел возможны пары простых чисел-близнецов, например, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, либо к простым близнецам подмешиваются квадраты 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50. В общем, выбор осуществляется с гарантией не cтолкнуться на не составное число в позиции, соответствующей числу кратному трем.

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

Список публикаций

1.Стечкин Б.С., Матиясевич Ю.В. Сито Эратосфена // Труды международной школы С.Б. Стечкина по теории функций. — Екатеринбург, 1999. – с. 148.