Analysis of some algorithms for smooth integers recognition.pdf Пусть задана факторная база S — множество, состоящее из некоторых простых чисел. Определение 1. Целое число будем называть S-гладким, если все его простые делители входят в S. Задачу нахождения большого количества гладких чисел приходится решать в некоторых методах факторизации чисел (например, квадратичное решето, решето числового поля) и дискретного логарифмирования. Рассмотрим два метода её решения: просеивания (в двух вариантах) и Бернштейна. 1. Метод просеивания [1] Задан многочлен F(x) G Z[x], факторная база S и целые числа A, C, A < C. Требуется найти все такие x, A ^ x ^ C, что F(x) — S-гладкое. Строится таблица, ячейки которой занумерованы целыми числами от A до C. Метод заключается в заполнении таблицы, её изменении и последующем просмотре. Алгоритм 1. Метод просеивания Вход: S — факторная база; A, C — целые числа, A < C; многочлен F(x) G Z[x]; M = max |F(x)|; первоначальное заполнение таблицы T: A^x^C x A A +1 C F (x) F (A) F (A +1) F (C) Выход: множество чисел x, A ^ x ^ C, таких, что F(x) — S-гладкое. 1: Для всех q G S, l G {1, 2,..., ln M/ ln q} 2: найти все решения x0 сравнения F(x) = 0 (mod ql). 3: Для всех решений x0 4: содержимое ячеек T(x) с номерами x = x0 + hql, (A — x0)/ql ^ h ^ (C — x0)/ql, поделить на q. 5: Просмотреть содержимое всех ячеек. Значение F(x) является S-гладким тогда и только тогда, когда T(x) = ±1. В отличие от метода пробных делений, в данном алгоритме все деления выполняются точно, то есть нет «неудачных» делений. Улучшение алгоритма 1 (логарифмический вариант) заключается в том, что вычисляется не F(x), а log |F(x)|; на шаге 4 вместо деления на q вычитается log q; на шаге 5 значения T(x) сравниваются с 0. В результате получаем выигрыш как по времени выполнения алгоритма, так и по требуемой памяти. Однако из-за погрешностей округления в вычислении логарифма даже для S-гладких значений F(x) можем получить T(x) = 0, и шаг 5 надо модифицировать следующим образом: значение F(x) является S-гладким тогда и только тогда, когда |T(x)| ^ E для некоторого «малого» E. При этом возможны ошибки первого и второго рода: необнаружение гладкого числа (влияет на эффективность алгоритма) и принятие негладкого числа за гладкое (влияет на корректность алгоритма). Для оценки величины E проведён следующий эксперимент: F(x) = (x + m)2 — N, где m = VN, N — модуль RSA длиной |N| бит; логарифм берётся по основанию 2 и округляется до ближайшего целого снизу; факторная база S состоит из |S | первых N простых чисел q, таких, что — =1 (параметры соответствуют методу квадратичq ного решета для факторизации числа N). Результаты представлены в табл. 1. Здесь Min — минимальное значение T [x], полученное после просеивания и соответствующее негладкому числу; Max — максимальное значение T [x], которое соответствует гладкому числу. Видно, что во всех случаях можно выбрать такое E, что Max < E < Min. Это позволит избежать ошибок обоих родов. Таблица 1 Оценка параметра E |S| = = 20 |S| = = 30 |S| = 50 |S| = = 100 |N | Min Max Min Max Min Max Min Max 20 7,6 3,2 8 2,8 9 3,2 10,6 3,2 40 8,8 4,2 8,6 4,6 9,6 4,6 11 7 50 8,8 6 9 5,2 9,8 6,6 10,8 5,8 60 10,2 5,4 10 6,3 10 6,4 11,2 7,4 Эксперименты показали, что логарифмический вариант просеивания работает быстрее, чем вариант с делением; результаты приведены в табл. 2 (CPU Intel Pentium P6100 2,00ГГц, память 1,7Гбайт, swap 1,9Гбайт). Таблица 2 Выигрыш логарифмического просеивания (по времени) |S| |N | C — A Выигрыш, % 30 50 217 41,16 50 50 215 55,2 50 60 218 48,72 100 50 213 45 100 60 217 45,24 150 50 213 56 150 60 216 43 150 70 217 49 Кроме того, хранение логарифмов чисел вместо самих чисел позволяет экономить используемую память. Так, при размере числа |N| = 64 бита, длине отрезка C — A = 218 и факторной базе из 50 элементов во время работы программы, реализующей просеивание с делением, используется память файла подкачки на 50 % (972 Mбайт), в то время как программа с вычислением логарифмов использует лишь 27% (525Mбайт). Это сильно влияет на время выполнения программы; в первом случае оно составляет 129 с, во втором — 42 с. 2. Метод Бернштейна [2] Метод Бернштейна позволяет сократить объём вычислений при помощи использования деревьев. Задача формулируется так: заданы факторная база S и множество целых чисел P. Требуется найти все S-гладкие p Е P. Отличие в постановке задачи от метода просеивания состоит в том, что множество чисел произвольно. Обозначим Q = П s и найдём остатки от деления Q на числа p Е P. Пусть ses Q mod p = r. Тогда r = ab, где a = (Q,p) — произведение тех простых, которые присутствуют в базе S и в исследуемом числе. Пусть наибольший показатель в каноническом разложении числа p на простые множители не превосходит z. Тогда в каноническом разложении rz все простые присутствуют в степени, не меньшей, чем в p. Таким образом, (rz mod p,p) есть часть числа p, разложимая в базе S; и число p является S-гладким, если (rz mod p,p) = p, т. е. rz mod p = 0. Определение 2. Деревом произведений для множества чисел называется двоичное дерево, листья которого соответствуют элементам этого множества и каждому узлу сопоставлено число, равное произведению чисел, соответствующих его потомкам. Алгоритм 2. Метод Бернштейна Вход: S — факторная база; множество чисел P; |P| ^ |S|. Выход: все S-гладкие числа p G P. 1: Построить дерево произведений для факторной базы S. В корне этого дерева получим Q. 2: Построить дерево произведений T для множества P (при этом вычисляются только значения, не большие Q, остальные помечаются *). 3: Вычислить дерево остатков Q mod T следующим образом: сначала число R, приписанное корню дерева T, заменяется на Q mod R, а затем происходит спуск по ветвям, во время которого каждое число заменяется на его остаток от деления на новое значение, приписанное его родителю. ok 4: Найти наименьшее натуральное число k, для которого max P ^ 22 . 5: Для всех p G P: найти r = Q mod p в дереве остатков Q mod T; вычислить sp := r2 mod p. 6: Ответ: все числа p, для которых sp = 0. Замечание. Значение z выбирается в виде 2k для того, чтобы возведение в степень z выполнить за k возведений в квадрат. В табл. 3 приведены результаты сравнения метода просеивания (с логарифмированием) и метода Бернштейна. Таблица 3 Сравнение методов просеивания и Бернштейна |S | = 50 |S | = = 100 |N | = 50 |N | = 60 |N = 50 |N | = 60 Метод Время, Память, Время, Память, Время, Память, Время, Память, c Мбайт с Мбайт с Мбайт с Мбайт Просеивание 4 200 19 880 3 155 23 990 Метод Бернштейна 3 5 13 5 3 29 25 30 Таким образом, метод Бернштейна существенно выигрывает по памяти и времени при небольшой мощности факторной базы, однако при увеличении размеров факторной базы и просеиваемых чисел метод просеивания с логарифмированием догоняет и обгоняет метод Бернштейна по времени, хотя и существенно проигрывает по памяти.

Скачать электронную версию публикации