Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[249]

Рис. 33.7 33.7 р-эвристика Полларда. (а) Последовательность хг1 = (xj - 1) mod 1387 с начальным элементом х\ = 2. (Разложение: 1387 = 19 • 73.) Жирные стрелки соответствуют шагам цикла, выполняемым до нахождения делителя 19. (После этого выполнение процедуры прекращается - но на рисунке показан весь р-цикл.) Серым цветом показаны последовательные значения переменной у. Делитель 19 обнаруживается при сравнении у = 63 с х7 = 177: НОД(63 - 177, 1387) = 19. (Ь) Та же самая последовательность по модулю 19. По этому модулю упомянутые выше числа х7 = 177 и у = 63 сравнимы, (с) Та же последовательность по модулю 73

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

Переменная к последовательно принимает значения 2,4,8,... (строки 4 и 13), когда значение г доходит до текущего значения к, значение жг- запоминается в переменной у, а переменная к увеличивается вдвое. Таким образом, у последовательно принимает значения х\, х2, х4, х$,...

В строках 8-10 мы пытаемся найти делитель числа га, используя два члена последовательности - текущее значение жг- и сохранённое значение у. Эта попытка удачна, если число d = gcd(y - Xi,n) отлично от 1 и от га (проверка выполняется в строке 9).

Эти действия на первый взгляд выглядят странно, но по крайней мере легко видеть, что процедура Pollard-Rho никогда не выдаёт неправильных ответов: уж если она чего напечатала, значит, это нетривиальный делитель га. Вопрос только в том, напечатает ли она хоть что-то. Сейчас мы приведём некоторые неформальные аргументы в пользу того, что если число га имеет нетривиальный делитель s, то есть шансы найти его после y/s проходов. (Напомним, что у составного числа га есть делитель, не превосходящий у/п, так что ожидаемое число итераций можно оценить как -(/га.

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

Поэтому последовательности можно изобразить в виде окружности с хвостиком (рис. 33.7): окружность соответствует периодической части последовательности, а хвостик - допериодической. (Эта картинка напоминает греческую букву р, поэтому метод и называется /-эвристикой.)

Что можно сказать о длине периода для случайно выбранного х\1 Некоторая (пусть и безосновательная) оценка может быть получена так. Представим себе, что каждое жг- выбирается случайно и не зависит от предыдущих; сколько шагов пройдёт до первого повторения? (Конечно, предположение о случайности жг- абсурдно


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

Итак, сколько шагов пройдёт до первого повторения? Эту задачу мы уже рассматривали под названием парадокса с днями рождения (раздел 6.6.1), где отмечали, что среднее количество членов последовательности до первого повтора имеет порядок 0(у/га).

Нас будут, впрочем, интересовать оценки длины периода не по модулю п, а по модулю делителей п. Пусть s - некоторый делитель п, для которого gcd(s,ra/s) = 1 (например, выделим степени некоторого одного простого множителя в разложении п на множители). Посмотрим на остатки от деления чисел жг- на число s. Эта последовательность ж = жг- mod s также можно рассматривать как заданную рекуррентным соотношением

xi+1 = (xf - 1) (mods),(33.50)

поскольку переход от модуля п к модулю s определён корректно (при s п) и перестановочен с возведением в квадрат и вычитанием единицы.

Повторив приведённое выше вероятностное рассуждение, мы придём к заключению, что последовательность (ж) становится периодичной за 0(y/s) шагов. Можно ожидать, что в последовательности (ж) повторение появится раньше, так как сравнимость по модулю п - более сильное условие, чем сравнимость по модулю s. (На рис. 33.7 как раз такой случай и показан.)

Теперь объясним, как используется переменная у. Пусть мы хотим найти повторяющиеся члены в последовательности (жг). Для этого не нужно сравнивать каждый член с каждым - вместо этого можно запоминать члены х\, х2, х4, х$,... и сравнивать другие члены последовательности с ними, ища повторений. При этом, конечно, мы не гарантируем, что обнаружим самую раннюю пару повторяющихся членов. Но поскольку повторение, раз случившись, далее идёт по циклу, мы его не пропустим. При этом нам придётся просмотреть больше членов последовательности, чем если бы мы сравнивали все пары, но ненамного (не более чем в константу раз).

Процедура Pollard-Rho сравнивает текущее значение жг- с запомненным значением у - но вместо того, чтобы проверять их равенство (и тем самым искать повторения в последовательности (жг)) вычисляет наибольший общий делитель их разности и числа п. Смысл этого в том, что тем самым можно уловить цикл в последовательности ж - если Xi и у сравнимы по модулю s, то наибольший общий делитель жг- - у и п будет кратен s, и если только он не окажется равным п, то дело сделано - мы нашли нетривиальный делитель числа п. (Заметим ещё, что число s используется только в наших рассуждениях, не встречаясь в программе.)


Всё может быть не так гладко, как мы описали, по двум причинам. Во-первых, наши оценки для числа шагов - всего лишь прикидкии, и алгоритм может проработать намного дольше, прежде чем будет найден общий делитель. Во-вторых, обнаруженный делитель, кратный s, может оказаться равным п и, следовательно, бесполезным. Такое возможно: пусть, например, п = pq, где р и q просты, и пусть последовательности (жг- mod р) и (жг- mod q) имеют одинаковые по длине периодические и допериодические части. Тогда повторения по модулю р совмещены с повторениями по модулю q, и в результате будет обнаруживаться общий делитель п.

Обе эти возможности редко встречаются на практике. В крайнем случае можно изменить формулу, порождающую рекуррентную последовательность, положив, например, жг 1 равным (жг-2 - с) mod п. В качестве значения с не следует брать 0 и 2 (не будем сейчас объяснять, почему); другие значения вполне приемлемы.

Конечно, наш анализ весьма приблизителен, так как поскольку числа Xi не являются случайными - но на практике процедура работает хорошо, являясь одним из наиболее эффективных методов поиска небольших делителей больших целых чисел: оценка yfs на число операций зависит от величины делителя, а не от величины самого числа. При работе с /3-битовым числом п мы ищем множители до у/п, то есть размера не более /3/2, и ожидаемое число арифметических операций имеет порядок га1/4 = 2/4 (что даёт порядка га1/,4/33 = 2/4/33 битовых операций.

Упражнения

33.9-1

Пользуясь рис. 33.7(a), определите, в какой моментэ процедура Pollard-Rho напечатает делитель 73 числа 1387. 33.9-2

Пусть задана функция / : Ъп -> Ъп и значение жо G Ъп. Определим последовательность Ж1,Ж2,... соотношением жг- = f(xi-\). Обозначим через и длину периодической части последовательности, а через t - длину допериодической части. Предложите эффективный алгоритм нахождения t и и. Оцените время его работы.

33.9-3

Через сколько шагов можно ожидать, что процедура Pollard-Rho обнаружит делитель вида ре, где р - простое число, а е > 1? 33.9-4*

Процедура Pollard-Rho на каждом шаге вычисляет наибольший общий делитель. Можно пытаться ускорить работу процедуры так: перемножить несколько соседних членов последовательности (жг), и вычислить наибольший общих делитель их произведения и числа у. Разработайте соответствующую процедуру и объясните, почему она будет работать. Сколько соседних членов стоит брать при работе с /3-битовыми числами?

Задачи.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]