НОВОСТИ Факторизация чисел и методы решета. Часть II

[NewsBot]

Прочие статьи цикла

You must be registered for see links

Факторизация чисел и методы решета. Часть II

Задается N — большое составное нечетное натуральное число (СННЧ), которое требуется факторизовать. Математическая теория метода решета числового поля (NFS) строится на основе теории делимости в алгебраических числовых полях. Перед любым автором, как и передо мной, возникает трудность сжатого изложения весьма обширного материала, касающегося методов SNFS и GNFS. Так как 2-й возник из 1-го я не привожу их отличий, хотя об этом много сказано.

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

Можно сказать читатели принудили меня доносить до них чужие идеи, которые я не разделяю, так как свои считаю более обоснованными и прогрессивными, более здравыми. Они пока не получили завершенного вида, но время еще есть. Хочу изменить у читателей отношение к своим идеям и получить поддержку, а не минусы в комментариях, не подкрепляемые доводами. Личную неприязнь или «ничего не понял» доводом для минусования публикации считать не могу.

Неоправданное усложнение (матрица СЛАУ для

имеет размер 6000000×6000000) задачи факторизации больших чисел (ЗФБЧ) подвигло меня серьезно заняться этой проблемой. Уже удалось

You must be registered for see links

, т.е. понять где и как прячутся делители в натуральном ряде чисел, что конечно же упростит их поиск и обнаружение.

Метод решета числового поля


Самый быстрый на сегодняшний день метод факторизации натуральных чисел (10 лет — одно число). Отличие этого метода решета числового поля (как специального Special Number Field Sieve SNFS) так и общего (General Number Field Sieve — GNFS)) от алгоритма QS — квадратичного решета, прежде всего, состоит в разных процедурах просеивания, которая проводится в GNFS не в кольце целых чисел Z, а в алгебраическом числовом поле, что отразилось в названии метода.

Как и в методе

You must be registered for see links

в основу формирования множества чисел для просеивания положен многочлен

не 2-й, а произвольной степени d>2, в точке x=m удовлетворяющий условию

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

Определение. Пусть К числовое поле. Элемент θ называется алгебраическим над полем К, если он является корнем какого-нибудь многочлена f(x) с коэффициентами из поля К.
Определение. Многочлен наименьшей степени со старшим коэффициентом 1, имеющий θ своим корнем, называется минимальным многочленом для θ.Степенью алгебраического элемента θ называется степень его минимального многочлена. Числами, сопряженными с θ, называются все остальные корни этого минимального многочлена.

Проверка делимости при просеивании выполняется с использованием нормы алгебраического числа. Как и в методе QS этот метод отыскивает гладкие числа порядка корня квадратного из N. Размер чисел с ростом N экспоненциально растет. Рост же эффективности метода обеспечивается тем, что сами числа в числовом поле меньше, чем в кольце, и вероятность для них стать гладкими несколько выше чем в методе QS, но сами алгоритмы в NFS существенно сложнее.

Так, например, автор [3] считает неправомерным называть этот метод алгоритмом, так как в нем на разных этапах используется несколько отдельных самостоятельных алгоритмов. Другие авторы не вполне поддерживают такую позицию.

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

Исходные математические структуры, используемые в GNFS
1. Пусть задано N – большое составное нечетное число, которое требуется факторизовать.
Выберем неприводимый многочлен, степень которого d>3 (при d=2 не будет выигрыша в сравнении с методом квадратичного решета).

2. Выберем целое m такое, что

, и разложим N по основанию m:

. (1)

3. Свяжем с разложением (1) неприводимый многочлен от х в кольце Z[x] многочленов с целыми коэффициентами

. В точке m

.

4. Определим многочлен просеивания

как однородный многочлен от двух переменных

:

. (2)

5. Определим второй многочлен

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

.

6. Выберем два положительных числа

, определяющих область просеивания (англ. sieve region): SR = {$inline$1≤b≤ L_1, - L_2 ≤a≤ L_2$inline$} в форме прямоугольника.

Формирование факторных баз
7. Пусть θ — корень

. Рассмотрим кольцо полиномов Z[θ]. Определим множество кольца, называемое алгебраической факторной базой FB1, состоящее из многочленов первого порядка вида

с нормой (2), являющейся простым числом. Эти многочлены —простые неразложимые в кольце алгебраических целых поля K= Q[θ]. Ограничим абсолютные значения норм полиномов из FB1 константой B1.

8. Определим рациональную факторную базу FB2, состоящую из всех простых чисел, ограниченных сверху константой B2.

9. Определим множество FB3, называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка

, норма которых — простое число. Должно выполняться условие FB1∩FB3 =∅.

Просеивание исходного множества
10. Выполним просеивание многочленов
{

} по факторной базе FB1 и целых чисел
{

} по факторной базе FB2. В результате получим множество M, (табл. Г) состоящее из гладких пар (a, b), то есть таких пар (a, b), что НОД(a,b)= 1, многочлен и число

и

раскладываются полностью по базам FB1 и FB2 соответственно.

11. Найдём (как и в методе QS) такое подмножество S ⊆M, что

; здесь Nr — обозначение нормы многочлена;

.

Формирование полных квадратов из пар гладких элементов
12. Определим многочлен

,
где

— производная

.
13. Многочлен g(θ) является полным квадратом в кольце многочленов Z(θ). Пусть тогда α(θ) есть квадратный корень из g(θ) и B — квадратный корень из

.

14. Строим отображение ф: θ → m, заменяя полином α(θ) числом α(m). Это отображение является кольцевым гомоморфизмом кольца алгебраических целых чисел

в кольцо Z, откуда получаем соотношение:
$inline$A^2 =g(m)^2≡ф(g(α))^2≡ф(f^{'2}_1(θ)·П_{(a,b)є S}(a - bθ))≡$inline$

.

Завершение ЗФБЧ
15. Пусть B=f '(m)·C. Найдём пару чисел (A, B) таких, что

Тогда найдём делитель числа N, вычисляя НОД(N, A ± B), как это делается, например, в методе квадратичного решета.

Это множество пунктов можно укрупнить до трех этапов
I. Как и в методе QS вначале формируется массив исходных значений, среди которых ожидаются гладкие, факторная база из обратимых элементов в Z/nZ, включающая элементы

, где р пробегает некоторое конечное множество индексов

. Символом

обозначим векторы |

|;

= {

}.

Далее рассматривается отображение

;

.
Это отображение на — сюръекция, если {

} порождают (Z/nZ)*; обычно так и бывает.

II. Поиск и установление соотношений. Отыскиваются векторы

, т.е. такие

, для которых

.Множество векторов V ={

} должно быть намного больше |

|

III Нахождение зависимостей и завершение ЗФБЧ.
Отыскиваются нетривиальные линейные зависимости по модулю два, подобно методу QS, для найденных векторов ϑ ∊V; их количество больше чем их размерность, следовательно, такая зависимость существует. Она устанавливается на основе решения системы линейных уравнений.

Это очень большая разреженная система над полем Z/2Z. Ее решением будет непустое множество W ⊆ V. Это означает, что при

выполнено сравнение

После этого проверяется выполнимость неравенства

. Если оно выполнено, то делитель N найден и процесс завершается. Иначе возвращаемся либо на 2-й этап, либо на 1-й, где строится новая факторная база.

Метод факторизации чисел GNFS крупными мазками (с пропуском деталей)


Далее приводится небольшой пример применения метода GNFS. В рассмотрение вводится кольцо Z [α], где α – корень многочлена

, а поскольку при

, легко можно убедиться в морфизме φ колец,

, определяемом равенством

Пояснения будут даны чуть ниже, после примера.

Следующее предположение состоит в том, что каким-то способом удается найти пару целых чисел

таких, что одновременно выполняются соотношения вида (это одно из решений СЛАУ)

в кольце

и

в кольце Z[α]

Применение морфизма φ ко второму равенству дает

в кольце Zn, т.е. получаем сравнение типа

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

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

отыскиваются среди малых значений.

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

ПРИМЕР
Пусть требуется факторизовать число

Зададим d = 4 и найдем

. Принимаем

. Находим разложение числа N по основанию

:

Далее полагаем

. Пусть α – корень многочлена

. Пара

-та самая «чудесная» пара. Действительно, с одной стороны в кольце Zn,

с другой стороны $inline$10+α =α^ 4+6α^2+9(α^2+3)^2$inline$в кольце Z[α].

Следующее предположение состоит в том, что каким-то способом удается найти пару целых чисел

таких, что одновременно выполняются соотношения вида

в кольце Zn и

в кольце Z [α].

Применим морфизм φ к выражению

. Получаем

, т.е.

.
В итоге формируем квадратичное сравнение

, или

Решая его, с привлечением алгоритма НОД Евклида, получаем значение, делителя

т.е. нетривиального делителя числа N, элементарно находится и 2-й.
Действительно,

, т.е. разложение на множители получено.

Необходимая пара чисел

не может быть найдена случайным перебором.

Можно воспользоваться базисным разложением на множители. Вначале ищем такие пары целых чисел

, чтобы в соответствующих кольцах суммы

и

имели в разложениях малые простые числа (или их степени).

Формируются два базиса: базис FВ1 содержит простые числа, которые меньше М (М-гладкое число), и другой базис FB2, содержащий элементы из кольца Z[α].
Получаем пару равенств,

и

для которой применяем морфизм φ сформированных колец и получаем равенство

Когда накопится достаточное число #FВ1 +#FB2 + 1 равенств такого вида, формируется линейная комбинация показателей степени элементов факторной базы по mod2 и получаем сравнение

. В этом и состоит основная идея рассматриваемого метода.

Относительно второго базиса FB2 скажем следующее. В FB2 можно включить небольшие неразложимые элементы кольца Z [α]. Понятие небольшой в кольце Z [α] связывается с нормой, позволяющей придать этому термину точный смысл. В кольце существуют и единицы, т.е. обратимые элементы кольца.

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

Теперь вернемся собственно к методу GNFS для более детального анализа происходящих явлений.

Формирование исходного массива для просеивания
Пусть задано

. Вычислим

. Представим N в m-ичной системе счисления

. Большие коэффициенты (28 и 33) вообще нежелательны.

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

Вычтем m=35 из свободного члена и одновременно добавим 1 к коэффициенту при m в 1-й степени. Получим

.
Теперь вычтем m=35 из предпоследнего слагаемого одновременно добавляя 1 к коэффициенту при m в квадрате. Получим

.

Пример. Такой многочлен лучше с точки зрения меньшего роста значений

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

. Чтобы выполнялось равенство m =31.

Формирование факторных баз
Факторная база FBi — это множество элементов, каждый из которых не превышает границы Вi. В методе GNFS создается три факторных базы с разными свойствами.

В примере:FB1-алгебраическая факторная база. Ее границей гладкости устанавливается В1=103. Ее элементы —

. Она образована линейными многочленами вида (с — dθ), порождающими простые идеалы в кольце целых алгебраических чисел

. Построение базы в таком виде — трудная задача, но на основании теоремы М. Бриггса [2] удается перейти от неприводимых многочленов и порождаемых ими простых идеалов к парам натуральных чисел (р, r).

Теорема. Множество простых идеалов кольца Zk находится во взаимно-однозначном соответствии с множеством пар положительных целых чисел (p, r) таких, что р — простое число,

Таблица A — Алгебраическая факторная база FB1

FB2 -рациональная факторная база. Она используется для разложения чисел вида

из Z. Множество ее элементов определяется равным множеству простых чисел, ограниченных сверху константой В2 (на практике

). В примере FB2 ={2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, границей для элементов FB2 служит значение B2 =30.
Ее элементы —

FB3 — образована квадратичными характерами (это также пары чисел (p, r))

Таблица Х — Факторная база квадратичных характеров FB3

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

Оценим необходимое количество гладких пар
Суммарный объем трех факторных баз s = 23+10 + 5 = 38, следовательно, результирующий результат просеивания должен содержать не менее 38 + 2 =40 элементов, один столбец добавляется для хранения знака числа (а — bm) и еще один для того, чтобы матрица СЛАУ имела ненулевое решение.

Область просеивания в решете числового поля представляет собой прямоугольник вида
SR ={$inline$(a, b)| 1≤b≤L_2; -L_1≤a≤L_1$inline$}. В этой области осуществляется решеточное просеивание вдоль прямых вида

={

}.
Результаты просеивания приведены ниже (табл. Г).

Таблица Г — Гладкие пары чисел

, найденные на этапе предварительного просеивания

Располагая, как и в методе QS, множеством гладких чисел формируется СЛАУ и отыскиваются решения (табл. С), обеспечивающие в линейных комбинациях получение сравнимых по модулю квадратов. Выполнение завершающего просеивания находит множество гладких пар М (Табл.С).

Пример. Обрабатывается элемент таблицы Г. Для примера взят элемент из последнего столбца

для которого вектор показателей степеней простых из факторной базы получает вид
ϑ(8, 3) =(1,0,0,1,0,0,0,1,0,0,0). Первая единица соответствует знаку минус у числа 85.
Для алгебраической факторной базы имеем

вектор имеет длину 24 элемента.

Таблица С — Элементы множества М, дающие решение СЛАУ

Система линейных алгебраических уравнений и ее решение


Сама СЛАУ и ее решение ничем особенным не отличаются по сравнению с методом QS. Используется либо стандартная процедура исключения переменных методом Гаусса, либо можно воспользоваться методом Ланцоша. Будем считать, что для N = 45113 решение СЛАУ уже найдено (это множество S пар чисел (а,b) и оно представлено в следующей таблице:

Обозначим через

многочлен равный, произведению всех многочленов

, где каждая пара (a, b) принадлежит найденному множеству решений

.

Используется важная теорема.

Теорема. Пусть К =Q[θ] — алгебраическое числовое поле, полученное присоединением к Q корня неприводимого в Q многочлена f(x). Тогда для любого многочлена α(x), принадлежащего кольцу

, многочлен

принадлежит кольцу Z[α], где

— производная многочлена

.

Для устранения неполноты кольца Z[θ] в NFS достаточно домножить многочлен

на квадрат производной

Пример. Вычислим для решения СЛАУ значение многочлена g(x) нашего базового примера c
N =45113 (выполняется редукция по модулю неприводимого многочлена)

где

.

Теперь надо вычислить полное значение корня из g(m)(modN), используя значения g(m) по частичным модулям 9851,9907 и 9929 или, другими словами, надо решить систему сравнений
х ≡5694 (mod 9851);
х ≡4152 (mod 9907);
х ≡3077 (mod 9929).

Для решения задачи используется китайская теорема об остатках (КТО). Находим значение

, используемое в завершающем сравнении

Алгоритм Евклида


Мы подошли к завершению факторизации заданного числа N = 45113.

Пример. Завершение. Вычисляем следующее произведение (вспоминаем, что m = 31):

Откуда

Пара чисел

удовлетворяет сравнению

, откуда

. Дальше уже совсем просто — используем алгоритм Евклида поиска наибольшего общего делителя и находим делители

Проверка: 197·229 = 45113 = N.

Заключение


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

Хочу отметить, что первое впечатление (а оно не изменилось) — занятный огород удалось нагородить. Отправная точка авторами не критиковалась, не осмысливалась, другие пути не разыскивались. Привлечение теории эллиптических кривых — боковое направление. Дальше, что ожидать? Топосы, категории? Делители СННЧ разыскиваются совсем не там,

You must be registered for see links

их НРЧ.

You must be registered for see links

и натурального ряда напрочь игнорируются. Не удержался. Опять скатываюсь в критику.

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

Список используемой литературы


1. Брассар Ж. Современная криптология. М.: ПОЛИМЕД, 1999.
2. Briggs M. An Introduction to theGeneral Number Field Sieve, M.Briggs Master's Thesis, Virginia Polytechnic Institute and State University, Blacksburg,Virginia, 1998, p. 1-84.
3. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003
4. Д.Э. Кнут. Искусство программирования. Т.2. Третье издание. Москва-Санкт-Петербург-Киев: Изд-во Мир, 2000.
5. Е.Б. Маховенко. Теоретико-числовые методы в криптографии. М.: Изд-во Гелиос АРВ, 2006
6. Нестеренко А.Ю. Теоретико-числовые алгоритмы в криптографии. Москва 2012
7 Ноден П., Китте К. Алгебраическая алгоритмика. М.: Мир, 1999.
8. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002.
9. Rivest R. L., Shamir A., Adleman L. M. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. 1978. V. 21, P. 120–126.
10. The RSA Challenge Numbers // RSA Laboratories.

You must be registered for see links

11. Стренг Г. Линейная алгебра и её применения. М.: Мир, 1980.
12. Смарт Н. Криптография. М.: Техносфера, 2005.
13. Shanks D. Five number-theoretic algorithms // Proceedings of the Second Manitoba Conference on Numerical Mathematics (Winnipeg), Utilitas Math. 1973. P. 51–70. Congressus Numerantium, No. VII.