Разработка и оценка эффективности алгоритмов просеивания для факторизации натуральных чисел тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Зиятдинов, Дмитрий Булатович

• Зиятдинов, Дмитрий Булатович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Зиятдинов, Дмитрий Булатович

ОГЛАВЛЕНИЕ

Введение

ГЛАВА 1. Основные алгоритмические этапы методов факторизации

модулей RSA и оценка их сложности

1.1 Квадратичное решето

1.2 Алгоритм решета числового поля

1.3 Экспериментальная оценка сложности алгоритма РЧП

2.1 Просеивание по подинтевалам в КР

2.1.1 Пример просеивания по подинтервалам в КР

2.1.2 Оценка эффективности просеивания по подинтервалам

2.1.3 Экспериментальная оценка эффективности АПП

2.2 Просеивание по подинтервалам в модификации Занга

2.2.1 Оценка эффективности просеивания по подинтервалам

в модификации Занга

ГЛАВА 3. Методика просеивания по особой области и ее оценка

3.1 Просеивание по особой области в гибридном методе

3.1.1 Оценка сложности гибридного метода

3.2 Эффективный выбор полинома и просеивание по особой области в РЧП

3.2.1 Экспериментальная оценка эффективности просеивания

по особой области в РЧП

ГЛАВА 4. Состав программного комплекса и методика численных экспериментов

4.1 Общие проблемы программной реализации

4.1.1 Генерация полиномов просеивания

4.1.2 Статистическая обработка данных

4.1.3 Некоторые алгоритмы

4.2 Метода Гаусса для систем линейных уравнений большой размерности

4.2.1 Оценки производительности

4.2.2 Пример

4.3 Методика экспериментов

Заключение

Публикации автора

Использованная литература

ПРИЛОЖЕНИЕ А. Дополнительные таблицы и графики

А.1 Просеивание по подинтервалам для КР

ПРИЛОЖЕНИЕ Б. Некоторые исходные тексты программ

Б.1 Генерация сильных чисел RSA

Б.2 Программа для быстрого поиска корней полинома по модулю

простых чисел

Б.З Программа для просеивания по подинтервалам для модификации КР Занга

Список обозначений

В работе используются следующие обозначения:

7г(п) — Количество простых чисел, не превосходящих п

(р(п) — Количество натуральных чисел, взаимнопростых с п

Z/nZ — Кольцо вычетов, изоморфное целым числам по модулю п

р (и) — Функция Дикмана-Де Брюина (см. [28], стр. 49 и [32])

p\f(x + кр) — То же, что f(x + кр) = 0 mod р\ р делит f{x) в точках х + кр

КР — Алгоритм целочисленной факторизации «квадратичное решето»

РЧП — Алгоритм целочисленной факторизации «решето числового поля»

Введение диссертации (часть автореферата) на тему «Разработка и оценка эффективности алгоритмов просеивания для факторизации натуральных чисел»

ВВЕДЕНИЕ

Задача целочисленной факторизации состоит в разложении произвольного натурального числа п на простые множители. Общеизвестно, что эта задача относится к классу трудных, однако на сегодняшний день не доказана принадлежность факторизации к формальным классам сложности Р или NP1. Напомним, что в недавней работе [7] показано, что более простая задача определения простоты числа лежит в Р, а значит существует детерминированный алгоритм, за полиномиальное время от длины поданного на его вход целого числа определяющий, является ли оно простым или нет. В то же время на практической трудоемкости решения задачи факторизации с помощью современных вычислительных средств в настоящее время основывается чрезвычайно широко распространенный метод шифрования с открытым ключом RSA, а также алгоритмы цифровой подписи.

Напомним кратко, что в протоколе RSA сначала происходит выбор открытого ключа, представляющего собой пару целых чисел (е, п), где число п = pq называется модулем RSA и является произведением двух хранящихся в тайне больших простых чисел р и q, а также вычисляется секретный ключ d = е-1 mod f(n). Затем передаваемое по открытому каналу вместе с открытым ключом сообщение m шифруется как с = те mod п, и потом, согласно теореме Эйлера, расшифровывается с помощью секретного ключа: cd = m mod п. Если злоумышленнику станет известна факторизация п, то он легко сможет вычислить секретный ключ d и расшифровать сообщение. Подробнее о проблеме RSA см. [31], с. 14, а также книги [68] с. 101, [70], § 33.7, [73], с. 87 и работу [46].

Можно утверждать, что обнаружение классического алгоритма, решающего задачу факторизации за полиномиальное время, заставило бы полностью отказаться от RSA в будущем, и скомпрометировало бы большое

1Подробнее см. [55], стр 336, citeNosov, § 14, а также книги [72] и [64]

количество уже существующих систем. Однако, самый быстрый алгоритм факторизации произвольных натуральных чисел, известный на сегодняшний день, имеет субэкспоненциальную оценку времени работы (опять же, от длины числа п). Это значит, что теоретически оцениваемое количество шагов до завершения его работы хоть и уступает значениям полинома от п = ехр[1пп], все-таки значительно превышает значение полинома от Inn. Функция сложности работы такого алгоритма, как правило, выражается формулой (см. [50]):

Ln[a, с] = ехр [(с + о(1)) (lnnHlnlnn)1"0] , а > 1/3.

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

Согласно отчету о последнем достигнутом рекорде факторизации (см. [35]), который был установлен 12 декабря 2009 г., с помощью алгоритма решета числового поля на простые множители было разложено 768-битное 232-значное число RSA-768. Общее потраченное на выполнение этой работы время составило два с половиной года. При этом распределенные вычисления на сотнях компьютеров потребовали более 1020 операций, что эквивалентно 2000 годам вычислений на компьютере класса 2.2GHz AMD Opteron. Тем не менее, авторы исследования справедливо оценивают затраченные усилия по факторизации 768-битного модуля как достаточно малые, чтобы рекомендовать не использовать в дальнейшем модули такого размера даже для кратковременной защиты данных. Кроме того, выдвигается предположение (см. также [22] и [23]), что факторизация 1024-битного RS А модуля хоть и будет примерно в тысячу раз более сложной задачей, но ее реше-

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

Рассмотрим кратко основные исторические вехи в поиске более быстрых алгоритмов факторизации произвольных больших натуральных чисел, связанные естественным образом с атакой на протокол RSA. Согласно обзору, проделанному в книге [10], можно выделить:

• 1978 г. выходит статья Р. Ривеста, А. Шамира и Л. Адлемана, впервые описывающая новый алгоритм шифрования RSA. В этом же году алгоритм факторизации «Линейное решето» Ричарда Шроппеля, позднее преобразованный в метод квадратичного решета, раскладывает произвольный RSA-модуль п на простые множители, а значит взламывает RSA, используя порядка Ln[ 1/2,1] простых операций. Размер надежного ключа RSA начинает оцениваться из того соображения, что для экспоненциального времени работы линейного решета (2Ь операций) необходимо, чтобы размер модуля п составлял по меньшей мере (0,5 + o(l))b2/log2 Ъ бит. 2

• 1988 г. Дж. Поллард объявляет о новом алгоритме факторизации «Решето числового поля» для чисел специального вида. Этот алгоритм, впоследствии обобщенный Дж. Булером, X. Ленстрой и К. Померанцем, факторизует любой RSA-модуль п, используя уже только около L[ 1/3,1.9] простых операций. Для экспоненциального времени работы решета числового поля необходимо, чтобы размер п составлял по крайней мере (0, 016... + o(l))63/(log2 b)2 бит.

• 1994 г. Питер Шор описывает алгоритм, который факторизует любой RSA-модуль п, используя порядка Ln[0,2] простых операций на квантовом компьютере размера Ln[0,1]. Для экспоненциального времени

2Параметр b определяет уровень безопасности шифра. Значение о(1) при этом стремится к нулю,

только когда b —> оо. Для конкретных значений b необходим более детальный анализ алгоритма.

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

Отметим, что на текущий момент квантовые компьютеры, на практике способные факторизовать сколько-нибудь большие целые числа, так и не созданы (см., например, книгу [58]). Кроме того, полный переход на алгоритмы шифрования, не поддающиеся взлому на пока еще не существующем квантовом компьютере, связан со многими не до конца еще разрешенными трудностями. Можно привести следующие аргументы в пользу дальнейшего использования и изучения алгоритмов RSA, а значит и решения задачи факторизации на классическом компьютере:

1. Высокая эффективность RSA на текущий момент, и низкая эффективность альтернативных алгоритмов. Например, устойчивому к взлому с помощью квантового компьютера алгоритму шифрования с открытым ключом Мак-Элис (см. [74], гл. 19) требуется размер ключа порядка n2/4 « b2(log2b)2 бит. Поскольку мы допускаем, что на момент взлома не существует лучшего алгоритма факторизации, чем алгоритм решета числового поля, и реальный уровень безопасности имеет выглядящий разумным на сегодняшний день порядок b = 128, размеры ключей RSA будут исчисляться тысячами бит, в то время как размеры ключей Мак-Элис — миллионами. Также имеет значение скорость работы алгоритма. Алгоритмы цифровой подписи, широко распространенные на текущий момент, допускают подпись и верификацию информации за полиномиальное время. Алгоритмы, устойчивые к возможности взлома на большом квантовом компьютере, работают более медленно. Использование их в настоящее время в сети Ин-

тернет повлекло бы за собой существенное снижение производительности сети.

2. Более 20 лет поисков алгоритмов полиномиальной факторизации и безуспешных попыток значительно улучшить асимптотическое время факторизации решета числового поля (см. [28], [33], [34]) позволяют надеяться, что этот алгоритм действительно представляет собой быстрейшую схему факторизации произвольного составного числа на классическом компьютере. Однако, поскольку невыгодно без необходимости увеличивать размер ключа шифрования до бесконечности, а также поскольку алгоритм решета числового поля обладает сложной структурой, мы полагаем, что все еще возможно локально улучшить его производительность для некоторого класса практически разрешимых задач.

Таким образом, задача исследования классических алгоритмов факторизации является по-прежнему актуальной. Рассматриваемые в диссертации алгоритмы квадратичного решета (КР) и решета числового поля (РЧП) — сложные, состоящие из нескольких этапов-, современные алгоритмы, наиболее эффективные для факторизации целых чисел размером от 50 десятичных знаков и более. Одним из важнейших этапов обоих алгоритмов является просеивание — процедура поиска достаточного количества так называемых гладких чисел для получения нетривиальной факторизации на последнем этапе. Как показано в [28] (с. 268-277, 294-300) эффективность алгоритма факторизации в целом разумно оценивать исходя из того, насколько эффективно возможно выполнить именно этап просеивания. Однако, особенно для алгоритма РЧП, очень важен еще и этап выбора полинома (см. докторскую диссертацию Б.Мерфи, 1999 г. [48] и статью 2004 г. Т.Кляйнунга [37]).

Отметим особо, что на сегодняшний день не существует строгого математического обоснования для оценки эффективности работы КР и РЧП в общем случае, все имеющиеся оценки получены при условии ряда эври-

стических предпосылок. Тем не менее, алгоритмы КР и РЧП достаточно хорошо исследованы. Уже в публикации [51] 1984 г. предлагаются ряд значительных модификаций базового алгоритма КР, без которых эффективное его применение на практике становится уже почти невозможным. Прежде всего это так называемое мультиполиномиальное квадратичное решето (МПКР), позволяющее решать задачу факторизации в параллельных процессах. Подробная публикация [12] 1995 г. описывает важную стратегию просеивания, в результате которой для факторизации могут быть использованы не только найденные гладкие числа (которых в результате однократной работы базового алгоритма может быть найдено недостаточное количество) , но и так называемые полугладкие. Такая же стратегия применима для алгоритма РЧП. Но еще большее значение имеет сформулированная для РЧП методика решеточного просеивания (см. [34], с.43-49), позволяющая, с помощью особым образом подобранных параметров р, просеивать только выборочные значения полиномов, и при этом получать лишь незначительно меньший выход гладких чисел относительно простого просеивания по всем элементам факторной базы.

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

3См. [59].

просеивания в алгоритмах КР и РЧП, а значит, в определенном смысле, и об эффективности процедуры факторизации в целом.

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

Для достижения поставленной цели были решены следующие основные задачи:

1. Исследованы современные алгоритмы целочисленной факторизации квадратичного решета и числового поля;

2. Построены оценки для частот появления гладких чисел для алгоритма просеивания по подинтервалам, оценена его эффективность относительно стратегии расширения интервала просеивания;

3. Исследованы процедуры выбора эффективных полиномов просеивания для алгоритма решета числового поля;

Основные положения, выносимые на защиту:

1. Разработка алгоритма просеивания по подинтервалам (АПП);

2. Получение оценки выигрыша для выхода гладких при использовании АПП;

3. Разработка программного комплекса для численной проверки полученных оценок;

4. Исследование метода Занга и оценка его эффективности;

5. Разработка алгоритма выбора эффективного полинома для алгоритма решета числового поля и проверка его эффективности;

1. Разработка и оценка эффективности алгоритма просеивания по подин-тервалам, обеспечивающего более эффективный поиск гладких пар в методах целочисленной факторизации квадратичного решета и решета числового поля;

2. Анализ и развитие специального метода Занга целочисленной факторизации;

3. Разработка алгоритма выбора оптимального полинома просеивания в методе решета числового поля;

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

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

Апробация работы. Основные результаты работы докладывались на конференциях:

1. Конференция аспирантов и молодых преподавателей КГУ, 2009, Казань

2. 7-я международная научно-практическая конференция «Инфокомму-никационные технологии глобального информационного общества» Казань, 2009;

3. Международная школа-конференция молодых ученых - Турку, Финляндия, июнь 2009;

4. Научно-практическая конференции и выставка «Инновации РАН -2010»;

5. III Всероссийской научно-практической конференции «Информационные технологии в системе экономической безопасности России и ее регионов», Казань, 2010.

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

Публикации. Основные результаты по теме диссертации изложены в 5 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК, 2 — в тезисах докладов.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложения. Основной текст диссертации изложен на 86 страницах с 12 рисунками и 10 таблицами. Список литературы содержит 74 наименования.

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

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

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

Во второй главе описывается, анализируется и получает статистически достоверную численную оценку методика просеивания по подинтер-валам в методе КР. Также рассматривается возможность применения этой методики к модификации КР Занга и методу факторизации решета числового поля. Делается вывод высокой эффективности этой методики для метода квадратичного решета, работающего с квадратичными генерирующими полиномами д(ж), и низкой эффективности при степени генерирующего полинома г > 2.

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

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

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

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Зиятдинов, Дмитрий Булатович

Основные результаты работы заключаются в следующем.

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

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

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Зиятдинов, Дмитрий Булатович, 2012 год

ЛИТЕРАТУРА

1. Зиятдинов Д.Б. Об одной оценке метода решета числового поля // Труды международной научно-практической конференции «Инфо-коммуникационные технологии глобального информационного общества». — 2009. — Казань. — http://iktgio.mcrt.ru/rusiktgio/tezisy

2. Зиятдинов Д.Б. О проблеме выбора полинома в методе решета числового поля / Зиятдинов Д.Б., Ишмухаметов Ш.Т., Рубцова Р.Г. // Труды III Всероссийской конференции «Информационные технологии в системе социально-экономической безопасности России и ее регионов», Казань, 2010, С. 177-183

3. Зитдинов Д.Б Методы защиты информации с открытым ключом и математические проблемы / Зиятдинов Д.Б., Ишмухаметов Ш.Т. // Материалы ежегодной научно-практической конференции «Инновации РАН-2010». - 2010. - Казань: Изд-во «Слово». - С. 303.

4. Зиятдинов Д.Б. Об одной стратегии в процедуре просеивания для факторизации больших натуральных чисел / Зиятдинов Д.Б., Рубцова Р.Г.// Ученые записки Казанского университета. — 2011. —-вып. 153. - т. 1. - С. 231-239.

5. Зиятдинов Д.Б. Об одном подходе к проблеме факторизации натуральных чисел / Бойко A.A., Зиятдинов Д.Б., Ишмухаметов Ш.Т. // Известия вузов. Математика. — 2011. — №4. — С. 15-22.

6. Зиятдиов Д.Б. Об одном варианте метода Гаусса для систем линейных уравнений большой размерности. / Зиятдиов Д.Б., Ишмухаметов Ш.Т. // Исследования по прикладной математики и информатике, находится в печати.

ЛИТЕРАТУРА

7. Agrawal M., Kayal N., Saxena N. PRIMES is in P // Annals of Mathematics. 2004. Vol. 160. № 2. P. 781-793.

8. Bach E., Peralta R. Asymptotic semismoothness probabilities // Mathematics of computation. 1996. Vol. 65. P. 1701-1715.

9. Bernstein D. J. Arbitrarily tight bounds on the distribution of smooth integers // Number theory for the Millennium volume 1, edited by Michael A. Bennett, Bruce C. Berndt, Nigel Boston, Harold G. Diamond, Adolf J. Hildebrand, Walter Philipp. A. K. Peters. 2002. P. 49-66.

10. Bernstein D. J. Introduction to post-quantum cryptography. SpringerVerlag Berlin Heidelberg. 2009.

11. Boender H. The number of relations in the Quadratic Sieve Algorithm // NM-R9622, The Netherlands. 1996. 22 p.

12. Boender H., Te Riele H. Factoring Integers with Large-Prime Variations of the Quadratic Sieve // Centrum voor Wiskunde en Informática. No. NM-R9513. 1995.

13. Boneh D. Twenty years of attacks on the RS A Cryptosystem // Notices Amer. Math. Soc. 46. 1999. P. 203-213.

14. Brent R. P. Recent Progress and Prospects for Integer Factorisation Algorithms // In Proc. of COCOON 2000. Springer-Verlag. P. 3-22.

15. Briggs M. An Introduction to the General Number Field Sieve // Master's Thesis, Virginia Polytechnic Institute and State University, Blacksburg, Virginia. 1998. P. 1-84.

17. Buchmann J., Loho J., Zayer J. An Implementation of the General Number Field Sieve //In Proceedings of Crypto'93. Springer-Verlag. 1993. P. 159165.

18. Buhler J., editor. Algorithmic Number Theory. Proc. ANTS-III, Portland, OR, volume 1423 of Lecture Notes in Computer Science. Springer-Verlag. 1998.

19. Buhler J. P., Lenstra H. W., Pomerance C., Factoring integers with the number field sieve, The developement of the number field sieve. Springer Verlag. Berlin. 1993. P. 50-94.

20. Coppersmith D. Solving homogeneous linear equations over GF (2) via block Wiedemann algorithm // Math. Comp. 1994. Vol. 62 (205) P. 333-350.

21. Lenstra A. K., Manasse M. S. Factoring by electronic mail // Proceedings of Eurocrypt '89, Lecture Notes in Computer Science, Vol. 434. P. 355-371. 1990.

22. Cavallar S., Lioen W. M., te Riele H. J., Dodson B., Lenstra A. K., Montgomery P .L., Murphy B. et al. Factorization of 512-bit RSA-modulus // CWI Report MAS-R0007, Feb 2000.

23. Lenstra A. et al Factoring Estimates for a 1024-Bit RSA Modulus // Advances in cryptology - Asiacrypt 2003. LNCS. 2003. Vol. 2894/2003. P. 55-74.

24. Cohen H. A course in computational algebraic number theory. SpringerVerlag. 1993. 545 p.

25. Couveignes J.-M. Computing a square root for the number field sieve // in [16]. P. 95-102.

26. Davis J. A., Holdridge D. B. Factorization using the quadratic sieve algorithm // Sandia Report Sand 83-1 346, Sandia National Laboratories, Albuquerque, New Mexico. 1983.

27. Dixon J. D. Asymptotically fast factorization of integers // Math. Comp. 36. 1981. P. 255-260.

28. Crandall R. E., Pomerance C. Prime numbers: A Computational Perspective. Springer. 2002.

29. Elkenbracht-Huising M. An implementation of the Number Field Sieve // Experimental Mathematics. 1996. Vol. 5. P. 231—253.

30. Gacs P., Lovasz L. Complexity of Algorithms. — Lecture Notes. Yale University. Spring 1999. 180 p.

31. Granville A. It is easy to determine whether a given integer is prime // BULLETIN (New Series) OF THE AMERICAN MATHEMATICAL SOCIETY. Vol. 42. № 1. P. 3-38.

32. Granville A. Smooth numbers: computational number theory and beyond // Algorithmic Number Theory MSRI Publications. 2008. Vol. 44.

33. Lenstra A. K., Lenstra H. W. Jr., Manasse M. S., Pollard J. M., Factoring integers with the number field sieve //in [34] P. 11-42.

34. Lenstra A., Lenstra H. (Eds) The Development of the Number Field Sieve // LNM v.1554. Springer-Verlag. Berlin. 1993.

35. Kleinjung T., Aoki K., Franke J., Lenstra A., Thome E., Bos J., Gaudry P., Kruppa A., Montgomery P., Osvik D. A., te Riele H., Timofeev A., Zimmermann P. Factorization of a 768-bit RSA modulus. Online report. 18 Feb 2010.

36. Lidl R., Niederreiter H. Introduction to Finite Fields and their Applications. Cambridge University Press. 21.07.1994. 416 p.

37. Kleinjung T. On Polynomial Selection for the General Number Field Sieve // Math. Comp. 75 (2006). P. 2037-2047

38. LaMaccia B., Odlyzko A. A. Solving Large Sparse Systems over finite fields. Advances in Cryptology, CRYPTO' 90, Lect.Nites in Comp. Science. Vol. 537. Springer-Verlag. P. 109-133

39. Landquist E. Possible Ways to Extend Zhang's Special Quadratic Sieve. 2003.

40. Marsaglia G., Zaman A., Marsaglia J. C. W. Numerical Solution of Some Classical Differential-Difference Equations j/ Mathematics of Computation, Vol. 53, № 187. July, 1989. P. 191-201.

41. Montgomery P. L. A Survey of Modern Integer Factorization Algorithms // CWI Quarterly. 1994, Vol .7. P. 337-366

42. Montgomery P. L. A block Lanczos algorithm for finding dependencies over GF (2) // EUROCRYPT '95. 1995.

43. Montgomery P. L. Square roots of products of algebraic numbers // in Proceedings of Symposia in Applied Mathematics. Mathematics of Computation 1943-1993. Vancouver. 1993. Walter Gautschi, ed.

44. Niven I., Zuckrman H., Mongomery H. An introduction to the number theory. - Willey Publ. 5-th edition. 1991. 541 p.

45. Odlyzko A. M. The future of integer factorization // CryptoBytes (The technical newsletter of RSA Laboratories) 1 (no. 2). 1995. P. 5-12.

46. Pointcheval D. New Public Key Cryptosystems Based on the Dependent-RSA Problems // EUROCRYPT '99, LNCS 1592, C. 239-254, 1999.

47. Pollard J. M. The lattice sieve //in Lenstra et al. [34]. P. 43-49.

48. Murphy B. A. Polynomial Selection for the Number Field Sieve integer Factorisation Algorithm //A thesis submitted for the degree of Doctor of Philosophy of The Australian National University. 1999.

49. Pollard J. M. Theorems on factorization and primality testing // Proc.Cambridge Phil.Society. 1974. Vol. 76. P. 521-578.

50. Pomerance C. Analysis and comparison of some integer factoring algorithms //In Mathematisch Centrum Computational Methods in Number Theory, Part 1. P. 89-139. 1982.

51.

52,

53

54.

55

56

57.

58.

59.

60

61.

62

63,

64,

Pomerance С. The quadratic sieve factoring algorithm // Advances in Cryptology, Proceedings of Eurocrypt 84. Paris. 1984 Pomerance C. A Tale of Two Sieves // Notices of the AMS 43 (12): P. 1473-1485. Dec 1996.

Pomerance C. Multiplicative independence for random integers // Analytic Number Theory, vol. 2: Proceedings of a Conference in Honor of Heini Halberstam, Birkhauser. Boston. 1996.

Pomerance C. Smooth numbers and the Quadratic Sieve // Algorithmic Number Theory, Cambridge, MSRI publication, Vol. 44. 2008. P. 69-82 Rothe J. Complexity theory and cryptology: an introduction to cryptocomplexity. — Springer Berlin Heidelberg New York. 1998. Schlage-Puchta J.-C. On shank's algorithm for modular square roots // Applied Mathematics E-Notes. № 5. 2005. P 84-88. Shanks D. Five number-theoretic algorithms // Proc. 2nd Manitoba Conf. Numer. Math. 1972. P. 51-70.

Williams C. P., Clearwater S. H. Ultimate zero and one: computing at the quantum frontier. — Springer-Verlag New York. Oct 1999. Zhang M. Factorization of the Numbers of the Form m3 + c2m2 + cim + c0. // in [18], P. 131-136

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир. 1979. 535 с.

Боревич 3. И., Шафаревич И. Р. Теория чисел. — 3-е издание. М.: Наука. 1985. 504 с.

Ван дер Варден Б. J1. Алгебра.. — 2-е изд. М.: Наука. 1979. 623 с. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО. 2003. 326 р.

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир. 1982. 416 с.

65. Захаров В. М., Эминов Б. Ф. Вычисления в конечных полях. — Уч-мет. пособие. Казань: КГТУ им. А.Н.Туполева, 2010. 132 с.

66. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казань: Казан ун.-т. 2011. 192 с.

67. Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы. — 3-е изд. М.: Вильяме. 2000. 832 с.

68. Коблиц Н. Курс теории чисел и криптографии. — М.: ТВП. 2001. 260 с.

69. Корешков Н. А. Теория чисел.. — Уч.-мет. пособие. Казань. КФУ. 2010. 35 с.

70. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО. 1999. 893 с.

71. Носов В. А. Основы теории алгоритмов и анализа их сложности. — Курс лекций. Москва. 1992. — http: //intsys.msu.ru/staff/vnosov / theoralg. htm

72. Писарук Н. Н. Сложность вычислений и криптография. — Минск. Белорусский государственный университет. 1999. 230 с.

73. Черемушкин А. В. Лекции по арифметическим функциям в криптографии. - М.: МЦНМО. 2002. 103 с.

74. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — Триумф. 2002. 850 с.

ПРИЛОЖЕНИЕ А. ДОПОЛНИТЕЛЬНЫЕ ТАБЛИЦЫ И ГРАФИКИ

А.1. Просеивание по подинтервалам для КР

Таблица А.1

Данные экспермента №2

Размерность (бит) Одно из чисел N В Ь

29 4,16- 108 102 102 55%

56 5,25- 1016 103 103 17%

74 1,76 • 1022 3 • 103 3-103 6.5%

108 1,92 • 1032 ю4 ю5 4.5%

147 1,29- 1044 4 • 105 4 • 106 0,6%

На следующих графиках продемонстрировано соотношение найденной доли гладких на исходном, двойном, тройном, четверном интервале и подин-тервалах для чисел различной длины. Отдельно расчитаны результаты для случаев, которые попали в группу "хороший исходный полином", а именно полиномы, для которых доля гладких на исходном интервале соответствует и) > сь>о, где сио специально подобранное значение, делящее участвующие в эксперименте полиномы на две равные группы. Также на графике отмечен "оптимистический" прогноз удвоения количества гладких, который на практике, при удвоении интервала, конечно, не оправдывается, так как с увеличением интервала просеивания значения значительно возрастают. Легко увидеть, что алгоритм просеивания по подинтервалам дает преимущество и практически сближается с оптимальным прогнозом.

400 ,00 % 350 ,00 % 300 ,00 % 250,00% 200 ,00 % 150,00% 100,00% 50,00% 0,00%

-исходный полином ^о п ти м ум (1 ) о п т и м ум (2 ) под и н та р валы

Рис. А.1. Соотношение найденной доли гладких на исходном, двойном, тройном, четверном интервале и подинтервалах для 30-битных чисел в классе "хороших" полиномов, шо = 55%

400,00% 350,00% 300,00% 250,00% 200,00% 150,00% 100,00% 50,00% 0,00%

-исходный полином -о п т и и ум (1 ) оптимум (2) подин тер ^алы

20 ,00 %--

0,00% -I-1-1-1-.-

0 1 2 3 4 5

Рис. А.З. Соотношение найденной доли гладких на исходном, двойном, тройном, четверном интервале и подинтервалах для 56-битных чисел в классе "хороших" полиномов, и о = 17%

-исходный полином •О П ТИ М V" О ) оптимр (2 ) подин те р &а л ы

——♦——и сходный полином п ти и ум (1 ) о л ти м ум (2 ) п о д и нте р 63 л ы "НЗЗН-ни ж н я я граница »»»^««»-верхняя граница

Рис. А.5. Соотношение найденной доли гладких на исходном, двойном, тройном, четверном интервале и подинтервалах для 74-битных чисел в классе "хороших" полиномов, <х>о = 6,5%

' * ■ исходны й полином 'п т и м ум (1 ) о л т и м ум (2) подин тер калы

■■исходны и полином -о п ти м ум (1 ) о л т и м ум (2 ) подин те р »злы

Рис. А.7. Соотношение найденной доли гладких на исходном, двойном, тройном, четверном интервале и подинтервалах для 108-битных чисел в классе "хороших" полиномов, сио = 4,5%

-исходным полином -о л ти м ум (1 ) о п т и м ум (2 ) подин те р&алы

0 12 3 4

т и сходный полином —--да™--о п т и м утл (1) о п т и м ум (2 ) подин те реалы

Рис. А.9. Соотношение найденной доли гладких на исходном, двойном, тройном, четверном интервале и подинтервалах для 147-битных чисел в классе "хороших" полиномов, сио = 0, 6%

4,60% 4,00% 3,50% 3,00% 2,50% 2,00% 1,50% 1,00% 0,50% 0,00%

-и сходный полином -о п ти м ум (1 ) оптимум (2) под и н те р »злы

ПРИЛОЖЕНИЕ Б. НЕКОТОРЫЕ ИСХОДНЫЕ ТЕКСТЫ ПРОГРАММ

Б.1. Генерация сильных чисел RSA

Программа на макро-языке для системы компьютерной алгебры PARI/GP.

get Мах (М) = {

Res =0;

RC=matsize (М) [ 1 ] ; /*количество рядов в матрице*/ for( i = 1, RC, if (Res<M[i ,1] , Res=M[i,l]) ); return (Res );

}

isStrong (N,T) = {

F1 = factor (N— 1); F2 = factor (N+l); Ml = getMax(F1); M2 = getMax (F2 ); return (M1>T &&M2>T);

}

RANEX)M(M, N) = { local(n, L); L = 1 ; while (L < N , L «= 1 ;) ; /* L/2 < N <= L , L power of 2 */ until (n < N к n >M, n = random (L));

return(n); } /^случайное число между М и N*/

getStrongPrime (х) = {

Т = 10 ~ (x-IERESHOLDEXPDEC); Strong — 0 ;

while (Strong==0, Result=nextprime (RANIX)M(10~ (x-1) ,l(Tx ));

Strong=isStrong (Result ,T); ); print (" Result = ",Result ); return ( Result );

}

genPQ (qexp) = {

P = getStrongPrime (qexp + 1); Q = getStrongPrime (qexp ); N = P*Q;

write (" rsagen . result . txt " , N); write ("rsagen. result, txt", Q); write (" rsagen . result . txt" , P); /*P>Q*/ if ( abs (P-Q)< sqrt ( sqrt (N)) *2 , write (" rsagen. result . txt" ,

''ПРЕДОТЕ)!^™: P-Q слишком мало ! ")) ; write (11 rsagen . result . txt", "");

}

read("rsagen.data.txt");

write("rsagen . result . txt ", "Hello!\\n");

write (" rsagen . result . txt " , "^Генерируем qexp + 1, " + ", qexp, for(i=l,K, genPQ (qexp ));

Б.2. Программа для быстрого поиска корней полинома по модулю простых чисел

Программа на языке Haskell, import Primes

— Функция для нахождения обратного элемента inverse :: (Integral а) => а —> а —> а inverse 1 n = 1

inverse х n = let g = fst (extEuclGcd x n)

i n g ' mod' n

— Расширенный алгоритм Евклида

— Возвращает (х,у) , где gcd(a,b) = ха + yb extEuclGcd :: (Integral а) => а —> а —> (а, а) extEuclGcd a b = extEuclGcd_iter a b (1,0) (0,1)

extEuclGcd_iter :: (Integral a) => a —> a

—> (a , a) —> (a , a)

extEuclGcd_iter a b (cl,c2) (dl,d2) | (a > b) kk (rl = 0) = (dl ,d2) | (a > b) kk (rl /= 0) = extEuclGcd_iter

(a- (ql*b)) b (cl - (ql*dl), c2 - (ql*d2)) (dl,d2) | (a <= b) kk (r2 = 0) = (cl ,c2)

| (a <= b) kk (r2 /= 0) = extEuclGcd_iter a (b - (q2*a)) (cl,c2) ( dl - (q2*cl), d2- (q2*c2)) where

q1 = a ' div ' b q 2 = b ' div ' a r 1 = a ' mod' b r 2 = b ' mod£ a

instance Num a => Num [a] where — (1)

(f:fs) + (g:gs) = f+g : fs + gs — (2)

fs + [] = fs — (3a)

[] + gs = gs — (3b)

(f:fs) - (g : gs) = f-g : fs-gs — *

fs — [] = fs — *

[] — gs = negate gs — *

(f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs) — (4)

(5)

ab s = undefined

Signum = map signum

fromlnteger n = [fromlnteger n] negate = map (\x —> —x)

*

— см. http://www. haskell .org/haskellwiki /Blow_your_mind

— takelnt : : ( Num a, Integral b)=>a—>[b] —>[b] takelnt x у = take (fromlntegral x) у

— генерация коэффициентов полинома х"р—х

polySplitZp : : ( Integral a)=>a—>[a]

poly SplitZp p = [1] ++ (take (fromlntegral (p-2)) (repeat 0))

[-1,0]

— генерация коэффициентов полинома степени d,

— представляющего собой константу с constantOfDegree :: (Integral а)=>а—>а—>[а] constantOfDegree d с = (take (fromlntegral d) (repeat 0))

++ [с]

— генерация коэффициентов полинома х Л ((р — 1)/2) — 1, если Ь—0

— либо полинома (x+b) ~ ((р — 1)/2) — 1 polySplitRight :: ( Integral а)=>а—>а—>[а] polySplitRight b р = map (\х—>х'mod'р)

([1 ,b]~q + constantOfDegree q ( — 1)) where q=(p —l)'div'2

— генерация коэффициентов полинома x Л ((p — l)/2) + l, если b=0

— либо полинома (x+b) Л ((p —l)/2) + l poly Split Left :: ( Integral a)=>a—>a—>[a] poly Split Left b p = map (\x->x'mod'p)

([ 1 , b] Л q + constantOfDegree q 1) where q =(p —1)' div ' 2

isUnity [ 1 ] = True isUnity _ = False

normalize [] p = [] normalize [0] p = [0] normalize [1] p = [1] normalize (x:xs) p

j x==0 = normalize xs p | otherwise = let r = inverse x p

in [1] ++map (\w—>w*r ' mod' p) xs

— polyGcdZp [1 ,15 ,29 ,8] (polySplitZp 67) 67 = [1 ,15 ,29 ,8]

— отсаток от деления полинома х на полином у по модулю р polyModZp : : ( Integral а) = >[а] —>[а]—>а->[а]

polyModZp х [] р = х polyModZp [] у р = у polyModZp х [0] р = х polyModZp [0] у р = у polyModZp (x:xs) (y:ys) р

| (length ys) = 0 = [ ] -— если у : ys скаляр

| isZero (x:xs) = [] — если x : xs нуль,

| (x = y) && (xs = ys) = [] — (x:xs) — если x : xs=y : ys | (length xs) >= (length ys) = let с = (inverse у p)*x

in polyModZp (map (\w—>w'mod' p) (xs — ys*[c])) (y:ys) p | (length xs) < (length ys) = normalize (x:xs) p

— polyGcdZp [1 ,15 ,29 ,8] (polySplitLeft 0 67) 67 = [1,21,21]

— polyGcdZp [1 ,15 ,29 ,8] ( polySplitRight 0 67) 67 = [1,61]

— полиномиальный gcd для полиномов с коэффициентами из х и у

— (от старшего к младшему) по модулю р polyGcdZp :: (Integral а) => [ а] —>[а]—>а—>[а] polyGcdZp х [] р = х

polyGcdZp х у р I (Х=У) = X

| (length х) >= (length у) = polyGcdZp у (polyModZp х у р) р | (length х) < (length у) = polyGcdZp х (polyModZp у х р) р

— тест: polyRootsZp [1,15,29,8] 67 = [6, 46, 4]

— итерация АН для поиска полиномиального gcd для быстрого

— определения корня полинома , х — коэф—ты полинома polyRootsZp_iter2 :: (Integral а) => а—>[а]—>а—>[а] polyRootsZp_iter2 b х р

| (length х) > 2 = let gl = polyGcdZp x (poly SplitLeft b p) p

g2 = polyGcdZp x (polySplitRight b p) p in if (isUnity gl) || (isUnity g2) then polyRootsZp_iter (b+l) x p else (polyRootsZp_iter2 b gl p)

++ (polyRootsZp_iter2 b g2 p) | (length x) = 2 =

let с = inverse (x !! 0) p in [ (— (x!!l)*c) 'mod' p ] | (length x) <= 1 = polyRootsZp_iter (b+l) x p

— итерация АН для поиска подходящего b polyRootsZp_iter :: (Integral а) => а—>[а]—>а—>[а] polyRootsZp_iter b х р = if polyEvalZp х (—b) р = О

then polyRootsZp_iter (b+1) х р else рoly Roоt s Z р _ i t er 2 b x p

— поиск корней полинома с коэффициентами из списка х

— (от старшего к младшему) по модулю р

— с помощью алгоритма Нидеррайтера (АН) polyRootsZp :: (Integral а) => [а]—>а—>[а] polyRootsZp f р

| isUnity g = [j | p < 6 = bruteRoots g p | otherwise = polyRootsZp_iter 0 g p where g = polyGcdZp (polySplitZp p) f p

— поиск корня перебором

bruteRoots f p = let result = map (\x—>(x, polyEvalZp fx p))

in map fst (filter (\(x, y)—>y==0) result)

— вычисление полинома с коэффициентами из списка х

— (от старшего к младшему) в точке t по модулю р polyEvalZp х t р = modHorner (reverse х) t р

— вычисление полинома с коэффициентами из списка (r:rs),

— в точке t по модулю р: (r_0 + r_l*t +r_2*t"2+...)

— список коэффициентов от 0 до n—1

modHorner [] t p = О

modHorner (r:rs) t p = mod (r + t * (modHorner rs t p)) p

— вывод ответа showRoots [] = do

return () showRoots (x:xs) = do putStrLn ((show $ fst x) ++ " " ++ show (snd x)) showRoots xs

— основная функция

rootsModPrimes f = filter (\(x , y) —>(length y) > 0)

[ (x, polyRootsZp f x)| x <— primes]

Б.З. Программа для просеивания по подинтервалам для модификации КР Занга

printfactorizations = 0;

justsubs = 0; /*0 значит false*/ justmain = 0 ;

issmooth(v) = {

local(rez , s , t); x = v ;

rez = eval (poly ); s = factor(rez );

t = component (component (s ,1) ^component (s , 1)) ; /*~maxprime*/

if (t <maxp ,

if (printfactorizations ,

factorfile = concat(concat(concat(concat("factors__id;

idiv ( sievingradiusl ,1000)) ,".txt "); writel (factorfile , "W(" ,y ,x ,") = ", rez , " = "); write ( factorfile , s );

);

return (1);

);

return (0);

}

idiv (a ,b) = {

ret urn (component ( divrem (a , b) , 1));

}

mod (a , b) = {

return (component (Mod(a , b ) ,2));

}

subsieveroot (bigp , bigroot , ashift) = {

/*инициализация массива */

shft = ashift ;

mass = vector (2* shft );

for (i=l, 2*shft ,

x = (i—shft) * bigp+bigroot ; mass [ i ] = 0 ; );

/*просеивание*/ for (k=l, j -1,

if (k=bigindex , next); p = fb [k] ; r = roots[к]; lnp = sizedigit(p); for (i=l, r [1] ,

inv = component (Mod( bigp , р)л( —1), 2); il = (( r [ i+1] —bigroot )* inv+shft)%p ; if (il <=0, il = il + p); forstep(i=il , 2*shft , p, mass [ i]+=lnp ;

);

);

);

/*поиск гладких в массиве и вывод их на печать*/ sm2 =0; maxl =0; avgl =0;

for (i=l, 2*shft ,

v = bigroot + (i—shft)* bigp ; u = У ;

bound = sizedigit (idiv (m,maxp))

+ sizedigit(4*(c0*u"3 + cl*u~2*v + c2*u*v~2 + vA3)) - 2;

if ( abs (mass [ i ])> bound kk, (abs(gcd(u, v)) = = l) &&issmooth(/ /*считаем только те гладкие , которые еще не были найдены if ( abs (v)< sievi ngr adius 1 , comment=" <already found >",

comment = ""; sm2-f+; sm2total++; avgl += abs (i—shft ) ;) print("гладкое: (", u, ",", v,") , 1=", i—shft, ";", comment); if ( abs (i—shft)>abs (maxl) , maxl=i —shft ); /*в maxl сохраняем значение и знак максимального 1*/

);

);

if (sm2>0, avgl = idiv(avgl, sm2));

print ( bigp , ";" , bigroot , ";" , sm2 , ";" , maxl , ";" , avgl ); /*вывод в файл для последующей обработке в excel*/

}

zhangsieve (u , ashft) = {

у = u;

shft = ashft;

/♦инициализация массива*/

shft = ashft ;

mass = vector (2* shft );

for (i=l, 2*shft mass [ i ] = 0 ;

);

print ("sieving radius: shft);

/*просеивание*/ for (k=l, j -1, P = fb[k]; r = г о о t s [ к ] ; lnp = sizedigit(p); for (i=l, r [1] ,

if (mod(u, p)==0, next); il = (u*r[i+l]+shft)%p; if (il <=0, il = il + p); forstep(i=il , 2*shft , p, mass [ i]+=lnp ;

);

);

);

/ * фильтрация * / sml =0;

for (i=l, 2 * shft , v = i —shft ; u = у ;

bound = sizedigit (idiv (m,maxp))

+ sizedigit (4*(c0*u~3 + cl*u~2*v + c2*u*v"2 + vA3))

if ( abs (mass [ i ])> bound kk (abs(gcd(u, v)) = = l)

&& issmooth (v) , print (" smooth: (", u, ",", v, ");"); sml++; smltotal++;

);

);

print("найдено гладких: ", sml, " (total:", smltotal, ")");

}

{ /*начало*/

read (" SubZhangCustom . data . txt ");

dO = cl~2 - 4*c0*c2 - 4*c0*m; dl = —4*(cl*m + 2*c0 ); d2 = —2*(2*c2*m + cl ); d3 = —4*m;

print (" n = " , m"3+c2*nT2+cl*mfcO );

print("fcoef: 1 , " , d3 , " , d2, ", " , dl , ", " , dO );

poly = x"4+d3*x"3*y+d2*x"2*y"2+dl*x*y~3+d0*y "4; maxp = 25000 ; maxu = 1 ;

maxpcount = idi v (maxp , 2) ;

/*оценка количества простых в базе для инициализации векторов fb и roots*/

sievingradius1 = 15000;

у = i;

f = eval (poly );

roots = vector (maxpcount); fb = vector (maxpcount); j = i;

forprime (p=2, maxp , R = polrootsmod (f , p ); if (#R>0, fb [ j ] = p ; r = vector(5);

r[i] =№;

for (i=l, #R,

r[i + l] = component (R[ i ], 2 );

);

г о ot s [ j] = r; j ++;

);

);

print (" Факторная база из j — 1, "элементов, B= ", fb[j—1]

/*просеивание */ if (!justsubs , smltotal = 0 ; for (i =1, maxu , zhangsieve(i , sievingradius 1 );

);

);

/* подинтервалы */ i f (justmain , quit ());

у = l;

bigindex = j —1; bigindexlowbound = j —51; bigindexhighbound = j +10; sm2total = 0 ;

while (bigindex>bigindexlowbound , bigroots = roots [ bigindex ] ; for (i=l, bigroots [1] ,

print (" Просеиваем подинтерваля для bigroots); subsieveroot (fb [ bigindex ] , bigroots [ i+1], sievingradius 1

);

bigindex —; );

}