Содержание к диссертации
Введение
Глава 1. Основные алгоритмические этапы методов факторизации модулей RSA и оценка их сложности 15
1.1 Квадратичное решето 15
1.2 Алгоритм решета числового поля 24
1.3 Экспериментальная оценка сложности алгоритма РЧП . 29
Глава 2. Методика просеивания по подинтервалам и ее оценка 37
2.1 Просеивание по подинтевалам в КР 37
2.1.1 Пример просеивания по подинтервалам в КР 39
2.1.2 Оценка эффективности просеивания по подинтервалам. 41
2.1.3 Экспериментальная оценка эффективности АПП . 44
2.2 Просеивание по подинтервалам в модификации Занга 49
2.2.1 Оценка эффективности просеивания по подинтервалам в модификации Занга 52
Глава 3. Методика просеивания по особой области и ее оценка . 56
3.1 Просеивание по особой области в гибридном методе 56
3.1.1 Оценка сложности гибридного метода 61
3.2 Эффективный выбор полинома и просеивание по особой области в РЧП 64
3.2.1 Экспериментальная оценка эффективности просеивания по особой области в РЧП 67
Глава 4. Состав программного комплекса и методика численных экспериментов 70
4.1 Общие проблемы программной реализации 70
4.1.1 Генерация полиномов просеивания 74
4.1.2 Статистическая обработка данных 75
4.1.3 Некоторые алгоритмы 75
4.2 Метода Гаусса для систем линейных уравнений большой размерности 78
4.2.1 Оценки производительности 80
4.2.2 Пример 83
4.3 Методика экспериментов 85
Заключение 87
Публикации автора 88
Использованная литература 88
Приложение А. Дополнительные таблицы и графики 95
А.1 Просеивание по подинтервалам для КР 95
Приложение Б. Некоторые исходные тексты программ 101
Б.1 Генерация сильных чисел RSA 101
Б.2 Программа для быстрого поиска корней полинома по модулю простых чисел 103
Б.3 Программа для просеивания по подинтервалам для модификации КР Занга 109
- Алгоритм решета числового поля
- Экспериментальная оценка эффективности АПП
- Эффективный выбор полинома и просеивание по особой области в РЧП
- Оценки производительности
Введение к работе
Актуальность темы:
Задача целочисленной факторизации состоит в разложении произвольного натурального числа п на простые множители. Она относится к классу трудных задач, но на сегодняшний день теоретически не доказана принадлежность факторизации ни к классу сложности Р, ни NP (см., например, [24], с.336). Напомним, что в недавней работе [6] показано, что задача определения простоты числа лежит в Р, а значит существует детерминированный алгоритм, за полиномиальное время от длины поданного на его вход целого числа определяющий, является ли оно простым или нет. В то же время на практической трудоемкости решения задачи факторизации с помощью современных вычислительных средств в настоящее время основывается чрезвычайно широко распространенный метод шифрования с открытым ключом RSA, а также некоторые алгоритмы цифровой подписи.
Существование классического алгоритма, решающего задачу факторизации за полиномиальное время, заставило бы полностью отказаться от RSA в будущем, и скомпрометировало бы большое количество уже существующих систем. Однако, самый быстрый алгоритм факторизации произвольных натуральных чисел, известный на сегодняшний день, имеет субэкспоненциальную оценку времени работы. Это значит, что он работает медленнее полиномиального, но все-таки значительно быстрее экспоненциального. Благодаря этому приемлемый уровень безопасности в схеме шифрования RSA достигается при использовании ключей достаточно небольшого размера. Но прогресс в области компьютерных технологий и алгоритмов факторизации постоянно увеличивает нижнюю границу размера для ключа, который считался бы на текущий момент безопасным.
Согласно отчету о последнем достигнутом рекорде факторизации (см. (17J), который был установлен 12 декабря 2009 г., с помощью алгоритма решета числового поля на простые множители было разложено 768-битное 232-значное число RSA-768. Общее потраченное на выполнение этой работы время составило два с половиной года. При этом распределенные вычисления на сотнях компьютеров потребовали более 1020 операций, что эквивалентно 2000 годам вычислений на компьютере класса 2.2GHz AMD Opteron. Однако авторы исследования справедливо оценивают затраченные усилия по факторизации 768-битного модуля как достаточно малые, чтобы рекомендовать больше не использовать модули такого размера даже для кратковременной защиты данных. Кроме того, выдвигается предположение, что факторизация 1024-битного RSA модуля, хоть и будет примерно в тысячу раз более слож-
ной задачей, но ее решение, в рамках схожего академического проекта, может быть получено уже в течение следующего десятилетия.
Можно привести следующие аргументы в пользу дальнейшего использования и изучения алгоритмов RSA, а значит и решения задачи факторизации на классическом компьютере:
1. Высокая эффективность RSA на текущий момент, и низкая эффек
тивность альтернативных алгоритмов. Например, устойчивому к взлому с
помощью квантового компьютера алгоритму шифрования с открытым клю
чом Мак-Элис (см. [7]) требуется размер ключа порядка n2/4 « b2(log2b)2
бит. Поскольку допускается, что на момент взлома не существует лучшего
алгоритма факторизации, чем алгоритм решета числового поля, и реальный
уровень безопасности имеет выглядящий разумным на сегодняшний день по
рядок b = 128, размеры ключей RSA будут исчисляться тысячами бит, в
то время как размеры ключей Мак-Элис — миллионами. Также имеет зна
чение скорость работы алгоритма. Алгоритмы цифровой подписи, широко
распространенные на текущий момент, допускают подпись и верификацию
информации за полиномиальное время. Алгоритмы, устойчивые к возмож
ности взлома на большом квантовом компьютере, работают более медленно.
Использование их в настоящее время в сети Интернет повлекло бы за собой
существенное снижение производительности сети.
2. Более 20 лет поисков алгоритмов полиномиальной факторизации
и безуспешных попыток значительно улучшить асимптотическое время фак
торизации решета числового поля (см. [16], [14], [12]) позволяют надеять
ся, что этот алгоритм действительно представляет собой быстрейшую схему
факторизации произвольного составного числа на классическом компьютере.
Однако, поскольку невыгодно без необходимости увеличивать размер ключа
шифрования до бесконечности, а также поскольку алгоритм РЧП обладает
сложной структурой, мы полагаем, что все еще возможно локально улучшить
его производительность для некоторого класса практически разрешимых за
дач.
Таким образом, задача исследования классических алгоритмов факторизации является по-прежнему актуальной. Рассматриваемые в диссертации алгоритмы квадратичного решета (КР) и решета числового поля (РЧП) — сложные, состоящие из нескольких этапов, современные алгоритмы, наиболее эффективные для факторизации целых чисел размером от 50 десятичных знаков и более. Одним из важнейших этапов обоих алгоритмов является просеивание — процедура поиска достаточного количества так называемых гладких чисел для получения нетривиальной факторизации на последнем этапе.
Как показано в [12] (стр. 268-277, 294-300) эффективность алгоритма факторизации в целом разумно оценивать исходя из того, насколько эффективно возможно выполнить именно этап просеивания. Однако, особенно для алгоритма РЧП, очень важен еще и этап выбора полинома (см. докторскую диссертацию Б.Мерфи, 1999 г. [20] и статью 2004 г. Т.Кляйнюнга [18]).
Отметим, что на сегодняшний день не существует строгого математического обоснования для оценки эффективности работы КР и РЧП в общем случае, все имеющиеся оценки получены при условии ряда эвристических предпосылок. Тем не менее, алгоритмы КР и РЧП достаточно хорошо исследованы. Уже в публикации [23] 1984 г. предлагаются ряд значительных модификаций базового алгоритма КР, без которых эффективное его применение на практике становится уже почти невозможным. Прежде всего это так называемое мультиполиномиальное квадратичное решето (МПКР), позволяющее решать задачу факторизации в параллельных процессах. Подробная публикация [8] 1995 г. описывает важную стратегию просеивания, в результате которой для факторизации могут быть использованы не только найденные гладкие числа (которых в результате однократной работы базового алгоритма может быть найдено недостаточное количество), но и так называемые полугладкие. Такая же стратегия применима для алгоритма РЧП. Но еще большее значение имеет сформулированная для РЧП методика решеточного просеивания (см. [16], с.43-49), позволяющая, с помощью особым образом подобранных параметров р, просеивать только выборочные значения полиномов, и при этом получать лишь незначительно меньший выход гладких чисел относительно простого просеивания по всем элементам факторной базы.
В данной работе осуществляется теоретический вывод, обоснование и оценка эффективности одного из возможных алгоритмов просеивания, делающих процедуру факторизации более эффективной — алгоритма просеивания цо подинтервалам для КР, а также исследуется процедура выбора эффективного полинома для алгоритма РЧП, связанного с особой областью просеивания. Кроме того исследуется гибридный алгоритм факторизации, полученный с помощью объединения идей КР и РЧП, обнаруживающий при ближайшем рассмотрении большое сходство с алгоритмом, известным как модификация КР Занга (см. [26]). Подобные теоретические обоснования вместе с некоторыми подтверждающими их экспериментальными оценками позволяют получить лучшее представление о границах эффективности процедуры просеивания в алгоритмах КР и РЧП, а значит, в определенном смысле, и об эффективности процедуры факторизации в целом.
Основной целью работы является исследование алгоритмов просеивания в методе квадратичного решета и решета числового поля и оценка их
эффективности, построение оценок для сходимости алгоритма просеивания по подинтервалам.
Для достижения поставленной цели были решены следующие основные задачи:
-
Исследованы современные алгоритмы целочисленной факторизации квадратичного решета и числового поля;
-
Построены оценки для частот появления гладких чисел для алгоритма просеивания по подинтервалам, оценена его эффективность относительно стратегии расширения интервала просеивания;
-
Исследованы процедуры выбора эффективных полиномов просеивания для алгоритма решета числового поля;
Основные положения, выносимые на защиту:
-
Разработка алгоритма просеивания по подинтервалам (АПП);
-
Получение оценки выигрыша для выхода гладких при использовании АПП;
-
Разработка программного комплекса для численной проверки полученных оценок;
-
Исследование метода Занга и оценка его эффективности;
-
Разработка алгоритма выбора эффективного полинома для алгоритма решета числового поля и проверка его эффективности;
Методы исследования. При выполнении работы использовались методы теории чисел, теории алгоритмов и компьютерного моделирования; Научная новизна состоит в решении следующих задач:
-
Разработка и оценка эффективности алгоритма просеивания по подинтервалам, обеспечивающего более эффективный поиск гладких пар в методах целочисленной факторизации квадратичного решета и решета числового поля;
-
Анализ и развитие специального метода Занга целочисленной факторизации;
-
Разработка алгоритма выбора оптимального полинома просеивания в методе решета числового поля;
Практическая значимость: Разработка и анализ алгоритмов просеивания, которые могут быть использованы для построения более эффективных алгоритмов факторизации.
Достоверность изложенных в работе результатов обеспечивается строгостью постановки задач и математических методов их решения, а также системным подходом к разработке и тестированию программного комплекса, экспериментально подтверждающего теоретические оценки.
Апробация работы. Основные результаты работы докладывались на конференциях:
-
Конференция аспирантов и молодых преподавателей КГУ, 2009, Казань
-
7-я международная научно-практическая конференция «Инфокоммуни-кационные технологии глобального информационного общества» Казань, 2009;
-
международная школа-конференция молодых ученых - Турку, Финляндия, июнь 2009;
-
научно-практическая конференции и выставка «Инновации РАН - 2010;
-
III Всероссийской научно-практической конференции «Информационные технологии в системе экономической безопасности России и ее регионов», Казань, 2010.
Личный вклад. Автор принимал активное участие в теоретических разработках и анализе предложенных методик, а также разработал и реализовал программные средства, необходимые для получения статистически достоверных численных оценок рассматриваемых в работе алгоритмов.
Публикации. Основные результаты по теме диссертации изложены в 5 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК, 2 — в тезисах докладов.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложения. Основной текст диссертации изложен на 86 страницах с 12 рисунками и 10 таблицами. Список литературы содержит 74 наименования.
Алгоритм решета числового поля
Опишем кратко метод решета числового поля . Пусть опять мы хотим факторизовать произвольное большое натуральное число п. На первом шаге выберем полином Р(х), обладающий свойством: п = Р{т), для некоторого m G Z. В простейшем случае выбор полинома происходит следующим образом. Во-первых задаются степенью г многочлена Р{х)\ т = 4 или и = 5 (см. [15] о рекомендуемых значениях г для эффективной работы алгоритма). Затем подбирается натуральное число т, близкое к п1/7", и выполняется обыкновенное разложение числа п в ш-й системе исчисления: п = тг + а1тГ-1 + + «г (1-7)
Очевидно, многочлен Р(х) = хг + сцж7"-1 + + аг, обладает требуемым свойством п = Р{т).
Далее, работа алгоритма происходит в кольце Z[x]/P(x), являющемся фактор-кольцом кольца Z[x] (кольцо многочленов в х с целыми коэффициентами) по идеалу, порождаемому многочленом Р(х). К свойствам этого кольца относится то, что мы можем рассмотреть гомоморфизм у : ж — т, преобразующий выражения в х из Z[x]/P(x) в выражения в т (mod п) из Z/nZ. Таким образом, если нам удастся найти многочлен а(х) = 2(х), являющийся квадратом в Z[x]/P(x), и одновременно а(т) будет квадратом в Z/nZ, то мы сможем достаточно просто получить пару (А, В) для выражения (1.3), исходя из того, что будет выполнятся: А2 = а(т) = 7(а(ж)) = 7( (ж)) = і Ш) s /?2Н = 52 (mod п)
(1.8) Проблема поиск квадрата, как и раньше, решается с помощью процедуры просеивания, выявляющий гладкие элементы. Просеивание в кольце целых чисел происходит точно так же, как и в алгоритме квадратичного ре Подробнее об алгоритме РЧП см. в [17], 19], [29[ шета. Для просеивания в кольце многочленов Z[x]/P(x), сначала выбирается алгебраическая факторная база AF, состоящая из идеалов, порождаемых примитивными элементами этого кольца специального вида a + bx,a,beZ (1.9)
Алгоритм решета числового поля работает только с элементами вида (1.9), так как они невелики по размеру, их норма легко вычисляется по формуле Norm(a + Ъх) = (-6)rP(f) и является целым числом. Необходимым условием для разложения любого многочлена Q(x) G Z[x]/P(x) на множители из алгебраической факторной базы AF является условие разложимости его нормы в произведение норм многочленов из AF. Этот простой факт позволяет сложно формализуемую задачу разложения многочленов в произведение простых идеалов в Z[x]/P(x) свести к более легкой задаче факторизации норм этих многочленов в кольце целых чисел .
Итак, просеивание в методе NFS выполняется для множества пар целых чисел (а, Ь), таких что двучлен а + Ъх разложим по алгебраической факторной базе AF, и одновременно, число а + bra разложимо по рациональной факторной базе F. Накопив достаточное количество таких пар, можно решить соответствующую систему линейных уравнений, получив в результате многочлен а{х) = /32(ж) и число а{т) = А2. Связывая многочлены кольца Z[x]/P(x) с целыми числами с помощью гомоморфизма j, согласно (1.8), можно найти пару (Д В), удовлетворяющую условию (1.3), полагая В = /3(т). Заметим, что процедура извлечения квадратного корня из а(х) в Z[x]/P(x) не является тривиальной11.
На сегодняшний день существует две основные стратегии просеивания по методу решета числового поля. Первая из них называется линейным просеиванием (Line Sieve) и заключается в том, что фиксируется значение. Подробное описание и обоснование всех этапов, необходимых для такого перехода, см. например в диссертации [15], а также в книге Крэндалла и Померанца [28], с. 278.
Из дальнейшего описания методики просеивания по подинтервалам в КР будет видно, что эта методика имеет большое сходство со стратегией решеточного просеивания, а значит полученные результаты экспериментов с просеиванием по подинтервалам в КР в какой-то мере могут быть применены и к алгоритму РЧП.
Как уже было сказано, сложность алгоритма решета числового поля оценивается формулой L[l/3,Cl=expf(C + o(l))(lnn)5(lnlnn) (1.10) гдес= f «1.92.
Значительный интерес в этой формуле для уточнения оценки эффективности решения задачи факторизации представляют значения константы с и даже величины о(1), стремящейся к нулю при условии, что п —сю. Действительно, как бы велико ни было п на практике, все-таки нельзя сказать, что оно стремится к бесконечности, а значит формула (1.10) требует уточнения.
Ниже приводятся теоретические результаты, из которых следует приведенная выше оценка, а также результаты проведенного численного эксперимента, уточняющего ее для небольших входных целых п. В результате, такая уточненная оценка будет несколько хуже оценки (1.10), но форма зависимости сложности факторизации от длины входного числа сохранится. в некотором смысле это говорит о том. что, при условии, что не существует более быстрого алгоритма факторизации, чем решето числового поля, невозможно факторизовать произвольное большое целое п быстрее, чем за субэкспоненциальное время от его длины.
Оценка времени работы алгоритма решета числового поля
Теорема, (см. [28], с. 286 и [53], с. 703-711) утверждает: Пусть mi, т22,.. - последовательность целых, равномерно распределенных независимых случайных величин на отрезке [1..Х], N — наименьшее целое, такое что в m\,vcii, тдг существует подпоследовательность, произведение элементов которой является квадратом. Тогда ожидаемое значение N выражается формулой: L(X) +W, где L(X) = exp(VlnXlnlnX). Кроме того, ожидаемое значение N не изменится, если потребовать, чтобы каждое из чисел rrij в произведении обладало В-гладкостью, где В = L{Xfl .
Для оценки времени работы алгоритма решета числового поля можно воспользоваться этой теоремой, если представить задачу отыскания гладких пар, как задачу отыскания такой последовательности пар (а, 6), чтобы произведения норм полиномов Л и /г, соответствующих этим парам, образовывало последовательность (рациональных) В-гладких чисел, в которой существует подпоследовательность, произведение элементов которой является квадратом.
Как уже говорилось выше, при решении задачи факторизации на практике возникают дополнительные факторы, которые могут повлиять на теоретическую оценку. Во-первых, п хоть и является очень большим числом, в действительности никогда не бесконечно, а значит значение величины, обозначенной о(1), может оказаться существенным. Не менее важным фактором может оказаться и выбор оптимального полинома f\ (и Д соответственно, если он не тривиальный) среди всех возможных полиномов факторизации, а также методики просеивания. Могут ли эти факторы значительно ухудшить или улучшить оценку (1.13)? Для частичного ответа на этот вопрос, рассмотрим некоторый замкнутый, доступный для быстрой численной обработки класс целых чисел п и полиномов /, чтобы вывести, если это возможно в рамках такой модели оценку лучшую чем (1.13) при условии использования только оптимальных (в этом классе) полиномов.
Экспериментальная оценка эффективности АПП
Теперь оценим эффективность алгоритма просеивания по подинтерва-лам на практике. Для этого была проведена серия численных экспериментов с помощью специально разработанной программной системы. Мы полагаем, что на основании полученных данных можно сделать вывод о том, что методика просеивания по подинтервалам существенно ускоряет поиск достаточного количества гладких чисел в алгоритме квадратичного решета, а значит, в целом, процедура факторизации с помощью КР становится более эффективной.
Итак, были рассмотрены числа длины порядка 30, 60, 90,120 и 150 бит, являющиеся сильными модулями RSA. Затем параметры В и L подбирались таким образом, чтобы в интервале просеивания была найдена некото рая разумная доля от необходимого числа гладких, притом чтобы радиус просеивания L оставался как можно меньше. И выигрыш от методики просеивания по подинтервалам, в таком случае, можно оценить как прирост гладких при просеивании по подинтервалам, относительно прироста гладких при увеличении радиуса просеивания в два, три и четыре раза.
Исходный полином подбирался как квадратичный полином д(x) = {т + ж)2 - п = х2 + 2тх + {т2 - п)) где т « [у/п\, модифицированный таким образом, чтобы каждый коэффициент полинома был меньше т/2.
Эксперимент заключался в выполнении процедуры просеивания с исходными параметрами, а затем по подинтервалам для 50 простых чисел р В, которые можно было бы включить в исходную факторную базу.
Для каждой заданной длины к эксперимент повторялся для 100 к-битных чисел, при этом подсчитывалось среднее значение новых гладких на подинтервалах, а также мера их разброса. Получившиеся результаты были поделены на две группы в зависимости от того, какую долю гладких чисел удалось найти на исходном интервале: "хорошие" полиномы и "плохие" полиномы. Граница — доля гладких UJQ — разделяющая эти два класса случаев полиномы подбиралась таким образом, чтобы тех и других полиномов, участвующих в эксперименте, было примерно поровну. А значит, при случайном выборе полинома, вероятности выбрать "хороший" или "плохой" примерно одинаковая.
В дальнейшем, говоря о доле гладких, будет иметься в виду доля гладких от необходимого количества для успешного завершения факторизации. Например, если найдено 5 5-гладких чисел, то найденная доля соответствует и) = у? 100%.
На графике 2.2 продемонстрировано соотношение найденной доли гладких на исходном, двойном, тройном, четверном интервале и подинтер-валах для 90-битных чисел, которые попали в группу "хороший исходный полином", а именно полиномы, для которых доля гладких на исходном интервале соответствует и) со о, где UJQ = 6.5%. Также на графике отмечен "оптимистически" прогноз удвоения количества гладких, который на практике, при удвоении интервала, конечно, не оправдывается, так как с увеличением интервала просеивания значения Q(X) значительно возрастают. Легко увидеть что алгоритм просеивания по подинтервалам дает преимущество и практически сближается с оптимальным прогнозом.
Остальные графики такого типа для чисел, которые участвовали в эксперименте, приведены в приложении 1.
Теперь для того, чтобы сделать вывод об эффективности методики просеивания по подинтервалам необходимо учесть следующее.
1. Чем хуже будет исходный полином q(x) в алгоритме, тем, скорее всего, хуже окажутся полиномы qv{x) для просеивания по подинтервалам. Сравнивая графики 2.2 и 2.2 можно убедиться, что численный эксперимент вполне подтверждает такое предположение. Однако для плохих полиномов посчитанная эффективность подиптервалов оказывается выше, чем для хороших. Поэтому, а также потому, что в действительности факторизация никогда не происходит с помощью первого попавшегося полинома, основное внимание в дальнейшем будет уделяться классу "хороших" полиномов.
2. Выход гладких для полинома qp(x) для различных р будет различным. Тем не менее, в дальнейшем мы будем считать, что разумно оценивать именно выигрыш для подинтервалов в среднем. Из рис. 2.4, отображающего кроме среднего значения доли гладких на подинтервалах, область трех сигм, видно что в действительности выход гладких на подинтервале может оказаться как значительно лучше усредненного значения, так и значительно хуже, однако почти наверняка не будет хуже значения на исходном интервале. Таким образом, выигрыш в среднем будет давать представление о том, какой именно выигрыш от методики просеивания по подинтервалам следует ожидать скорее всего.
3. Технически детали реализации просеивания по исходному интервалу и по подинтервалам могут как существенно снизить, так и существенно увеличить рассчитанную здесь эффективность. В данном случае важно использовать все возможности для оптимизации, и в первую очередь — не вычислять факторную базу для qv{x) заново, но использовать уже известную базу для д(ж) для быстрых расчетов.
4. На основе полученной статистики можно сделать вывод не только о числах рассмотренной размерности, но и, предположительно, обо всех числах, для которых как правило применяется на практике алгоритм КР (порядка 300-400 бит).
Итак, проведенный эксперимент показывает следующий выигрыш от методики просеивания по подинтервалам. При условии, что исходный полином q(x) обладает достаточно хорошими свойствами для факторизации, просеивание по подинтервалам дает стабильный прирост в выходе гладких относительно альтернативы, заключающейся в расширении исходного интервала просеивания в два, три и четыре раза.
Как видно из рис. 2.5, средний выигрыш в выходе гладких в результате использования методики просеивания по подинтервалам, таким образом, относительно выхода гладких, достигнутого за счет расширения интервала просеивания в два раза составляет 20% от доли гладких, найденной при исходных параметрах. Относительно расширения интервала просеивания в три и четыре раза, выигрыш приближается к 50% и, следует ожидать, что уже не будет значительно увеличиваться.
Эффективный выбор полинома и просеивание по особой области в РЧП
На основе проведенных исследований, была предложена новая методика для выбора полинома в алгоритме решета числового поля, которая позволяет находить полипомы, дающие большое количество гладких при просеивании по особой области.
В статье Кляйнунга [37] предложен метод построения пары полиномов для алгоритма РЧП с целыми коэффициентами Fi(x) = pd(adxd+ad xd l-{-... + а\х + ао) и Fi{x) = рх — т, имеющих общий корень т/р по модулю п, где п - это число, которое требуется факторизовать, р - целое число. В указанной статье на выбор числа р не накладывается никаких условий, кроме: 1. р ш; 2. р представляет собой произведение нескольких небольших простых чисел.
Выбор пары полиномов в методе Кляйнунга выполняется неоднозначно, а критерием оценки качества полинома является некоторая мера, представляющую собой функционал, значение которого определяется коэффициентами полинома и действительным числом к, называемым skewnes8. В результате выбор полиноминальной пары сводится к перебору всевозможных полиномов F\(ж), удовлетворяющих условию (3.7), и выбору среди них полинома с наименьшей мерой. Второй полином определяется однозначно параметрами рит. Такой подход не оптимален и обладает тем недостатком, что время его работы для больших п слишком велико (полгода для подбора подходящего полинома в рекордном разложении 768-битового числа п, см [35]).
В диссертации предлагается другой подход к выбору полинома F\ (ж). Наша идея заключается в том, чтобы выбирать полином Fx{x) так, чтобы его производная F[{x) имела два действительных корня а\ и а2, расположенных недалеко друг от друга, причем полином F\{x) в точках ct\ и а2 имел противоположные значения, тогда F\(ж) имеет действительный корень между а.\ и а2:
Пусть М = max(Fi(ai),Fi(a2))- Рассмотрим наибольший непрерывный интервал [с, е], содержащий точки а\ и а2 на котором выполнено неравенство (ж)[ М (см. рис. 3.2). Обозначим через хо корень Fi(z), находящийся между точками а\ и «2- По теореме Лагранжа для некоторого i в окрестности точки хо выполняется F1 (ж) F{(i)ix-xo) Ь- (6),гдеЬ — длина интервала [с, е]. Поскольку точка i также находится в окрестности нулей производной F{{X),TO опять, по теореме Лагранжа, F[( ) { (&), и следовательно F ж) F[ {2) L2.
Предположим теперь, что полиномиальная пара Fi(ж), F2(x) выбрана. Для эффективности работы метода РЧП необходимо обеспечить сравни тельно небольшие значения нормы линейных полиномов а — Ъ9 в числовом поле Z[0] : при изменении параметров а и 6 в некоторой области SR (от англ. sieve region). Норма полинома Nr(a - Ъв) может быть вычислена по формуле Nr{a - Ъв) = Ь ().
Предположим теперь, что полином Fi(z) имеет свойства, сформулированные выше, и оценим значения нормы Nr(a-bd) в специальной области SR, описываемой неравенствами.
Оценка (3.9) показывает, что при увеличении площади W сектора SR рост нормы происходит пропорционально Wd2. При изменении ширины L сектора 5R без изменения W рост нормы Nr(a - Ьв) будет пропорционален росту полинома Fi(L), т.е. пропорционален Ld.
Значит, в первичном приближении рост нормы будем наименьшим в направлении увеличения высоты Q сектора SR, а не его ширины L.
В следующем разделе приведено описание эксперимента, показывающего эффективность описанной методики на примере числа п размерности порядка 100 бит.
Оценки производительности
Вариант 1, Стандартный метод Гаусса.
Память - SysRow SysCol бит для хранения матрицы системы.
Прямой ход (переменная цикла к изменяется от 1 до SysRow):
1. Поиск ненулевого элемента в строке — О (SysCol) операций для каждого к,
2. Перестановка столбцов - всего O(SysCol) операций,
3. Поиск ненулевого элемента в столбце - О (SysRow) операций,
4. Сложение строк - O(SysCol) операций, выполняется O(SysRow) раз для каждого к.
Обратный ход:
5. Поиск ненулевого элемента в столбце - O(SysRow),
6. Сложение строк - 0{SysCol) операций,
Всего: 0{SysRow SysCol) + О {SysRow2) + 0{SysRow2 SysCol) = 0(h3), где h = SysRow и SysCol
Вариант 2. Метдд Гаусса с сортировкой столбцов и строк с помощюю дополнительных массивов.
В этом варианте для сокращения общего времени вычисления введем дополнительные массивы OrdRow[l..SysRow] и OrdCol[l..SysCol], определяющие порядок перебора строк и столбцов, первоначальные значения которых задаются формулами: OrdRow[i] = i,OrdCol[j] = j. Теперь вместо перестановок строк или столбцов будем просто переставлять элементы массивов OrdRow и OrdCol, что сократит выполнение пунктов 1, 3, 5 от О(h) до трех операций.
Время остальных операций не изменится. Объем требуемой памяти увеличится на SysRow + SysCol байт. Общая производительность метода останется той же О //г3), но константа С в неравенстве L С /г3 станет значительно меньше.
Вариант 3. Метдд Гаусса варианта 2 с хранением ммтрицы в виде таблиыы ненулевых элементов.
Обозначим через t максимальное число ненулевых элементов в строке матрицы. Будем хранить каждую строчку г матрицы системы в виде вектора, содержащего номера ненулевых элементов, тогда общий объем занимаемой памяти сократится до SysRow t байт.
Оценим время выполнения остальных операций:
Прямой ход (каждая операция выполняется в цикле О (SysRow) раз):
1. Поиск ненулевого элемента в строке — 0(t) операций для каждого к,
2. Перестановка столбцов - 3 операции,
3. Поиск ненулевого элемента в столбце: для проверки условия SysMatr[k,j] ф О придется в каждой строке вычислять значение SysMatr[k,j], что потребует просмотра вектора номеров ненулевых элементов строки длины t. Число операции будет иметь порядок 0{SysRowt),
4. Сложение строк - 0(t) операций, выполняется O(SysRow) раз для каждого к.
Обратный ход:
5. Поиск ненулевого элемента в столбце - 0(SysRow t),
6. Сложение строк - О(t) операций.
Общая производительность метода улучшилась. Оценка числа операций составляет теперь 0(h2t). Объем требуемой памяти также уменьшился и составляет теперь 0(ht) байт.
Таким образом, общий объем памяти и время выполнения алгоритма становятся не хуже, чем в алгоритме Ланцоса [38], который считается лучшим на сегодняшним днем алгоритмом решения систем линейных уравнений для факторизации целых чисел методом решета числового поля. В статье Монтгомери [42], с, 118, приводится оценка производительности блочной реализации метода Ланцоса, равная 0{h2k/N), где за N обозначена разрядность процессора, на котором выполняется вычисление, поскольку на N-разрядном процессоре можно за 1 раз обработать N бит информации. Однако, поскольку описанная здесь реализация также допускает такую блочную обработку, то, в целом, наш алгоритм является более простым, надежным и способным к масштабированию, чем алгоритм Монтгомери, приведенный в [421.
