Ро-алгоритм Полларда

Эта статья — об алгоритме факторизации чисел. О методе дискретного логарифмирования см. ро-метод Полларда для дискретного логарифмирования.

Ро-алгоритм (<math>\rho</math>-алгоритм) — предложенный Джоном Поллардом в 1975 году алгоритм, служащий для факторизации (разложения на множители) целых чисел. Данный алгоритм основывается на алгоритме Флойда поиска длины цикла в последовательности и некоторых следствиях из парадокса дней рождений. Алгоритм наиболее эффективен при факторизации составных чисел с достаточно малыми множителями в разложении. Сложность алгоритма оценивается как <math>O(N^{1/4})</math>.

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

История алгоритма

В конце 60-х годов XX века Роберт Флойд придумал достаточно эффективный алгоритм поиска длины цикла в последовательности, также известный, как алгоритм «черепаха и заяц». Джон Поллард, Дональд Кнут и другие математики проанализировали поведение этого алгоритма в среднем случае. Было предложено несколько модификаций и улучшений алгоритма.

В 1975 году Поллард опубликовал статью, в которой он, основываясь на алгоритме Флойда обнаружения циклов, изложил идею алгоритма факторизации чисел, работающего за время, пропорциональное <math>N^{1/4}</math>. Автор алгоритма назвал его методом факторизации Монте-Карло, отражая кажущуюся случайность чисел, генерируемых в процессе вычисления. Однако позже метод всё-таки получил своё современное название — ρ-aлгоритм Полларда.

В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма <math>F_{n} = 2^{2^n}+1</math> при <math>5 \leq n \leq 13</math>.

Так, <math>F_8 = 1238926361552897 \cdot p_{62}</math>, где <math>p_{62}</math> — простое число, состоящее из 62 десятичных цифр.

В рамках проекта «Cunningham project» алгоритм Полларда помог найти делитель длиной 19 цифр числа <math>2^{2386}+1</math>. Большие делители также могли бы быть найдены, однако открытие метода факторизации с помощью эллиптических кривых сделало алгоритм Полларда неконкурентоспособным.

Описание алгоритма

Оригинальная версия

Рассматривается последовательность целых чисел <math>{x_{n}}</math>, такая что <math>x_{0}=2</math> и <math>x_{i+1}=(x_{i}^{2}-1\,) (\mathrm{mod}\, N)</math>, где <math>N</math> — число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом:

1. Вычисляются тройки чисел

<math>(x_{i}, x_{2i}, Q_{i}), i=1,2,...</math>, где <math>Q_{i} \equiv \prod_{j=1}^{i}(x_{2j}-x_{j})\, (\mathrm{mod}\, N)</math>.

Причём каждая такая тройка получается из предыдущей.

2. Каждый раз, когда число <math>i</math> кратно числу <math>m</math> (скажем, <math>m=100</math>), вычисляется наибольший общий делитель <math>d_{i}=\mathrm{GCD}(Q_{i},N)</math> любым известным методом.

3. Если <math>1 < d_{i} < N</math>, то частичное разложения числа <math>N</math> найдено, причём <math>N = d_{i} \times (N/d_{i})</math>.

Найденный делитель <math>d_{i}</math> может быть составным, поэтому его также необходимо факторизовать. Если число <math>N/d_{i}</math> составное, то продолжаем алгоритм с модулем <math>N' = N/d_{i}</math>.

4. Вычисления повторяются <math>S</math> раз. Если при этом число не было до конца факторизовано, выбирается, например, другое начальное число <math>x_{0}</math>.

Современная версия

Пусть <math>N</math> составное целое положительное число, которое требуется разложить на множители. Алгоритм выглядит следующим образом:

1. Случайным образом выбирается небольшое число <math>x_{0}</math> и строится последовательность <math>\{x_{n}\}, n = 0, 1, 2, ...</math>, определяя каждое следующее как <math>x_{n+1} = F(x_{n})\, (\mathrm{mod}\,\, N)</math>.
2. Одновременно на каждом i-ом шаге вычисляется <math>d = \mathrm{GCD}(N,|x_{i}-x_{j}|)</math> для каких-либо <math>i</math>, <math>j</math> таких, что <math>j<i</math>, например, <math>i = 2j</math>.
3. Если <math>d>1</math>, то вычисление заканчивается, и найденное на предыдущем шаге число <math>d</math> является делителем <math>N</math>. Если <math>N/d</math> не является простым числом, то процедуру поиска делителей продолжается, взяв в качестве <math>N</math> число <math>N'=N/d</math>.

На практике функция <math>F(x)</math> выбирается не слишком сложной для вычисления (но в то же время не линейным многочленом), при условии того, что она не должна порождать взаимно однозначное отображение. Обычно в качестве <math>F(x)</math> выбираются функции <math>F(x) = x^2 \pm 1 (\mathrm{mod}\, N)</math> или <math>F(x) = x^2 \pm a (\mathrm{mod}\, N)</math>. Однако функции <math>x^2-2</math> и <math>x^2</math> не подходят.

Если известно, что для делителя <math>p</math> числа <math>N</math> справедливо <math>p \equiv 1\, (\mathrm{mod}\, k)</math> при некотором <math>k > 2</math>, то имеет смысл использовать <math>F(x) = x^k + b</math>.

Существенным недостатком алгоритма в такой реализации является необходимость хранить большое число предыдущих значений <math>x_{j}</math>.

Улучшения алгоритма

Изначальная версия алгоритма обладает рядом недостатков. В настоящий момент существует несколько подходов к улучшению оригинального алгоритма.

Пусть <math>F(x) = (x^2 - 1) \mathrm{mod}\, N</math>. Тогда, если <math>(x_{j} - x_{i}) \equiv 0 (\mathrm{mod}\, p)</math>, то <math>(f(x_{j}) - f(x_{i})) \equiv 0 (\mathrm{mod}\, p)</math>, поэтому, если пара <math>(x_{i}, x_{j})</math> даёт решение, то решение даст любая пара <math>(x_{i+k}, x_{j+k})</math>.

Поэтому, нет необходимости проверять все пары <math>(x_{i}, x_{j})</math>, а можно ограничиться парами вида <math>(x_{i}, x_{j})</math>, где <math>j = 2^k</math>, и <math>k</math> пробегает набор последовательны значений 1, 2, 3, …, а <math>i</math> принимает значения из интервала <math>[2^{k}+1; 2^{k+1}]</math>. Например, <math>k=3</math>, <math>j=2^3=8</math>, а <math>i\in [9;16]</math>.

Эта идея была предложена Ричардом Брентом в 1980 году и позволяет уменьшить количество выполняемых операций приблизительно на 25 %.

Ещё одна вариация ρ-алгоритма Полларда была разработана Флойдом. Согласно Флойду, значение <math>y</math> обновляется на каждом шаге по формуле <math>y = F^2(y) = F(F(y))</math>, поэтому на шаге <math>i</math> будут получены значения <math>x_{i} = F^{i}(x_{0})</math>, <math>y_{i} = x_{2i} = F^{2i}(x_{0})</math>, и НОД на этом шаге вычисляется для <math>N</math> и <math>y-x</math>.

Пример факторизации числа

Данный пример наглядно демонстрирует ρ-алгоритм факторизации (версия алгоритма, с улучшением Флойда), для числа N = 8051:

Таблица: факторизация числа 8051

n = 8051,   F(x) = x2 + 1 mod n ,   x0 = y0 = 2
i	xi=F(xi-1)	yi=F(F(yi-1))	НОД(|xi − yi|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

Используя другие варианты полинома <math>F(x)</math>, можно также получить делитель 83:

Таблица: факторизация числа 8051

n = 8051,   F(x) = x2 + 3 mod n ,   x0 = y0 = 2
i	xi=F(xi-1)	yi=F(F(yi-1))	НОД(|xi − yi|, 8051)
1	7	52	1
2	52	1442	1
3	2707	778	1
4	1442	3932	83

Таким образом, d₁ = 97, d₂ = 83 — нетривиальные делители числа 8051.

После нахождения делителя числа, в ρ-алгоритме предлагается продолжать вычисления и искать делители числа <math>N/d</math>, если <math>N/d</math> не является простым. В этом простом примере данного шага совершать не потребовалось.

Обоснование ρ-алгоритма Полларда

Алгоритм основывается на известном парадоксе дней рождения.

{{{1}}}

Следует отметить, что вероятность <math>p = 0.5</math> в парадоксе дней рождения достигается при <math>\lambda \approx 0.69</math>.

Пусть последовательность <math>\{u_{n}\}</math> состоит из разностей <math>x_{i} - x_{j}</math>, проверяемых в ходе работы алгоритма. Определяется новая последовательность <math>\{z_{n}\}</math>, где <math>z_{n} = u_{n}\, \mathrm{mod}\, q</math>, <math>q</math> — меньший из делителей числа <math>N</math>.

Все члены последовательности <math>\{z_{n}\}</math> меньше <math>\sqrt{N}</math>. Если рассматривать её как случайную последовательность целых чисел, меньших <math>q</math>, то, согласно парадоксу дней рождения, вероятность того, что среди <math>l+1</math> её членов попадутся два одинаковых, превысит <math>1/2</math> при <math>\lambda \approx 0.69</math>, тогда <math>l</math> должно быть не меньше <math>\sqrt{2\lambda q} \approx \sqrt{1.4 q} \approx 1.18\sqrt{q}</math>.

Если <math>z_{i}=z_{j}</math>, тогда <math>x_{i}-x_{j} \equiv 0\, \mathrm{mod}\, q</math>, то есть, <math>x_{i}-x_{j}=kq</math> для некоторого целого <math>k</math>. Если <math>x_{i} \neq x_{j}</math>, что выполняется с большой вероятностью, то искомый делитель <math>q</math> числа <math>N</math> будет найден как <math>\mathrm{GCD}(N, |x_{i}-x_{j}|)</math>. Поскольку <math>\sqrt{q} \leq n^{1/4}</math>, то с вероятностью, превышающей <math>1/2</math> , делитель <math>N</math> будет найден за <math>1.18 \times N^{1/4}</math> итераций.

Сложность алгоритма

Чтобы оценить сложность алгоритма, рассматривается последовательность, строящаяся в процессе вычислений, как случайная (разумеется, ни о какой строгости при этом говорить нельзя). Чтобы полностью факторизовать число <math>N</math> длиной <math>\beta</math> бит, достаточно найти все его делители, не превосходящие <math>\sqrt{N}</math>, что требует максимум порядка <math>\sqrt{N}</math> арифметических операций, или <math>N^{1/4}\beta^2 = 2^{\beta/4}\beta^2</math> битовых операций.

Поэтому сложность алгоритма оценивается, как <math>O(N^{1/4})</math>. Однако в этой оценке не учитываются накладные расходы по вычислению наибольшего общего делителя. Полученная сложность алгоритма, хотя и не является точной, достаточно хорошо согласуется с практикой.

Справедливо следующее утверждение: пусть <math>N</math> — составное число. Тогда существует такая константа <math>C</math>, что для любого положительного числа <math>\lambda</math> вероятность события, состоящего в том, что ρ-алгоритм Полларда не найдет нетривиального делителя <math>N</math> за время <math>C\sqrt{\lambda \sqrt N}(\log N)^2</math>, не превосходит величины <math>e^{-\lambda}</math>. Данное утверждение следует из парадокса дней рождения.

Особенности реализации

Объём памяти, используемый алгоритмом, можно значительно уменьшить.

 int Rho-Поллард (int N)
 { 
   int x = random(1, N-2);
   int y = 1; int i = 0; int stage = 2;
   while (Н.О.Д.(N, abs(x - y)) == 1)
   {
     if (i == stage ){
       y = x;
       stage = stage*2; 
     }
     x = (x*x - 1) (mod N);
     i = i + 1;
   }
   return Н.О.Д(N, abs(x-y));
 }

В этом варианте вычисление требует хранить в памяти всего три переменные <math>N</math>, <math>x</math>, и <math>y</math>, что выгодно отличает алгоритм в такой реализации от других методов факторизации чисел.

Распараллеливание алгоритма

Алгоритм Полларда допускает распараллеливание с использованием как систем с разделяемой памятью, так и систем с распределенной памятью (передача сообщений), однако второй случай является наиболее интересным с практической точки зрения.

Система с распределенной памятью

Существующий метод распалаллеливания заключается в том, что каждый вычислительный узел исполняет один и тот же последовательный алгоритм, однако, исходное число <math>x_{0}</math> и/или полином <math>F(x)</math> берутся различными. Для упрощения распаралеливания, предлагается получать их из генератора случайных чисел. Однако такая параллельная реализация не даёт линейного ускорения.

Предположим что есть <math>P</math> одинаковых исполнителей. Если мы используем <math>P</math> различных последовательностей (то есть различных полиномов <math>F(x)</math>), то вероятность того, что первые <math>k</math> чисел в этих последовательностях будут различными по модулю <math>p</math> будет примерно равна <math>\exp({-k^2 P}/{2 p})</math>. Таким образом, максимальное ускорение можно оценить как <math>P^{1/2}</math>.

Ричард Крэндалл предположил, что достижимо ускорение <math>O(P/(log{P})^2)</math>, однако данное утверждение пока не проверено.

Система с общей памятью

Предыдущий метод, очевидно, можно использовать и на системах с общей памятью, однако, гораздо разумнее использовать единый генератор <math>F(x)</math>.

См. также

• P-1 алгоритм Полларда
• P-метод Полларда дискретного логарифмирования
• P+1 алгоритм Уильямса
• Метод пробных делений
• Метод Ферма
• Факторизация с помощью эллиптических кривых
• Общий метод решета числового поля

Литература

• Василенко О. Н. [www.ict.edu.ru/ft/002416/book.pdf Теоретико-числовые алгоритмы в криптографии]. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
• Ишмухаметов Ш. Т. [old.kpfu.ru/f9/bibl/Monograph_ishm.pdf Методы факторизации натуральных чисел: Учебное пособие] / Захаров В.М.. — Казань: Казанский Университет, 2011. — С. 61-64. — 190 с. — ISBN 978-3-659-17639-5.
• Косяков М.С. [books.ifmo.ru/file/pdf/1551.pdf Введение в распределенные вычисления] / НИУ ИТМО. — СПб, 2014. — 155 с.
• Герман О.Н., Нестеренко А.Ю. [new.math.msu.su/department/number/dw/lib/exe/fetch.php?media=тчмк.pdf Теоретико-числовые методы в криптографии]. — М., 2012. — 300 с.
• Соловьев Ю.П., Садовничий В.А., Шавгулидзе Е.Т., Белокуров В.В. Эллиптические кривые и современные алгоритмы теории чисел. — М.: Ин-т компьют. исслед., 2003. — 192 с. — ISBN ISBN 5-939722-27-X.
• Brent R. P. [maths-people.anu.edu.au/~brent/pd/rpb193.pdf Некоторые параллельные алгоритмы факторизации чисел] (англ.) = Some parallel algorithms for integer factorization. — 1999. — С. 7. — DOI:10.1017/S0305004100049252.
• Brent R. P. [link.springer.com/article/10.1007/BF01933190 An improved Monte Carlo factorization algorithm] (англ.) // BIT Numerical Mathematics. — 1980. — 1 June (vol. 20, fasc. 2). — P. 176-184. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=1572-9125&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 1572-9125]. — DOI:10.1007/BF01933190.
• Chatterjee S., Sarkar P. [www.amazon.com/Introduction-Identity-Based-Encryption-Information-Security/dp/1596932384 Introduction] (англ.) // Identity-Based Encryption. — Boston: Springer US, 2008. — ISBN 978-1-59693-238-8.
• Childs, Lindsay N. Congruences // [books.google.ru/books/about/A_Concrete_Introduction_to_Higher_Algebr.html?id=qyDAKBr_I2YC&redir_esc=y Введение в высшую алгебру] = Concrete Introduction to Higher Algebra. — 3-е изд. — USA: Springer, 2009. — С. 471-473. — 603 с. — ISBN 978-0-387-74725-5.
• Chris Christensen [dx.doi.org/10.1080/01611190802293397 Review of Modern Cryptanalysis: Techniques for Advanced Code Breaking by Christopher Swenson] // Cryptologia. — 2009. — 27 января (т. 33, вып. 1). — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0161-1194&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0161-1194]. — DOI:10.1080/01611190802293397.
• Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. [books.google.ru/books?id=NLngYyWFl_YC Алгоритмы: построение и анализ] = Introduction to algorithms. — 2-е изд. — USA: MIT Press, 2001. — С. 897-907. — 1180 с. — ISBN 9780262032933.
• Crandall R.E. [people.reed.edu/~crandall/papers/parrho.pdf Распараллеливание P-алгоритма факторизации Полларда] (англ.) = Parallelization of Polldar-rho factorization. — 1999.
• Koshy T. Congruences // [books.google.ru/books?id=d5Z5I3gnFh0C Элементарная теория чисел и её приложения] = Elementary Number Theory with Applications. — 2-е изд. — USA: Academic Press, 2007. — С. 238. — 771 с. — ISBN 9780123724878.
• Kuhn F., Struik R. [link.springer.com/chapter/10.1007/3-540-45537-X_17 Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms] (англ.) // Selected Areas in Cryptography / Serge Vaudenay, Amr M.. — Springer Berlin Heidelberg, 2001. — P. 212-229. — ISBN 978-3-540-43066-7, 978-3-540-45537-0. — DOI:10.1007/3-540-45537-x_17.
• Mollin R.A. [antoanthongtin.vn/portals/0/uploadimages/kiennt2/sach/sach-csdl4/1584886188.pdf An Introduction to Cryptography] / Rosen K.H.. — 2. — London: Chapman and Hall, 2006. — 413 с. — ISBN 9781584886181.
• Pollard J. M. [www.cs.cmu.edu/~avrim/451f11/lectures/lect1122_Pollard.pdf A Monte Carlo method for factorization] // BIT Numerical Mathematics. — 1975. — Vol. 15, № 3. — P. 331–334.
• Pollard J.M. [journals.cambridge.org/article_S0305004100049252 Theorems on factorization and primality testing] // Mathematical Proceedings of the Cambridge Philosophical Society. — 1974. — Т. 76, вып. 03. — С. 521–528. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=1469-8064&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 1469-8064]. — DOI:10.1017/S0305004100049252.
• Pollard J. M. [journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2074504 Методы факторизации и проверка простоты.] (англ.) = Theorems on factorization and primality testing. // Математические Труды Кэмбриджского Философского Общества (Mathematical Proceedings of the Cambridge Philosophical Society). — 1974. — Т. 76, № 3. — С. 521. — DOI:10.1017/S0305004100049252.
• Reisel, H. [books.google.ru/books?id=94DaZuVETzIC Простые числа и компьютерные методы факторизации] = Prime Numbers and Computer Methods for Factorization. — 2-е изд. — USA: Springer, 2012. — С. 183. — 464 с. — ISBN 978-0-8176-8297-2.
• Robert W. Floyd [doi.acm.org/10.1145/321420.321422 Nondeterministic Algorithms] // J. ACM. — 1967. — Т. 14, вып. 4. — С. 636–644. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0004-5411&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0004-5411]. — DOI:10.1145/321420.321422.

Отрывок, характеризующий Ро-алгоритм Полларда

«Chere et excellente amie, quelle chose terrible et effrayante que l'absence! J'ai beau me dire que la moitie de mon existence et de mon bonheur est en vous, que malgre la distance qui nous separe, nos coeurs sont unis par des liens indissolubles; le mien se revolte contre la destinee, et je ne puis, malgre les plaisirs et les distractions qui m'entourent, vaincre une certaine tristesse cachee que je ressens au fond du coeur depuis notre separation. Pourquoi ne sommes nous pas reunies, comme cet ete dans votre grand cabinet sur le canape bleu, le canape a confidences? Pourquoi ne puis je, comme il y a trois mois, puiser de nouvelles forces morales dans votre regard si doux, si calme et si penetrant, regard que j'aimais tant et que je crois voir devant moi, quand je vous ecris».
[Милый и бесценный друг, какая страшная и ужасная вещь разлука! Сколько ни твержу себе, что половина моего существования и моего счастия в вас, что, несмотря на расстояние, которое нас разлучает, сердца наши соединены неразрывными узами, мое сердце возмущается против судьбы, и, несмотря на удовольствия и рассеяния, которые меня окружают, я не могу подавить некоторую скрытую грусть, которую испытываю в глубине сердца со времени нашей разлуки. Отчего мы не вместе, как в прошлое лето, в вашем большом кабинете, на голубом диване, на диване «признаний»? Отчего я не могу, как три месяца тому назад, почерпать новые нравственные силы в вашем взгляде, кротком, спокойном и проницательном, который я так любила и который я вижу перед собой в ту минуту, как пишу вам?]
Прочтя до этого места, княжна Марья вздохнула и оглянулась в трюмо, которое стояло направо от нее. Зеркало отразило некрасивое слабое тело и худое лицо. Глаза, всегда грустные, теперь особенно безнадежно смотрели на себя в зеркало. «Она мне льстит», подумала княжна, отвернулась и продолжала читать. Жюли, однако, не льстила своему другу: действительно, и глаза княжны, большие, глубокие и лучистые (как будто лучи теплого света иногда снопами выходили из них), были так хороши, что очень часто, несмотря на некрасивость всего лица, глаза эти делались привлекательнее красоты. Но княжна никогда не видала хорошего выражения своих глаз, того выражения, которое они принимали в те минуты, когда она не думала о себе. Как и у всех людей, лицо ее принимало натянуто неестественное, дурное выражение, как скоро она смотрелась в зеркало. Она продолжала читать: 211
«Tout Moscou ne parle que guerre. L'un de mes deux freres est deja a l'etranger, l'autre est avec la garde, qui se met en Marieche vers la frontiere. Notre cher еmpereur a quitte Petersbourg et, a ce qu'on pretend, compte lui meme exposer sa precieuse existence aux chances de la guerre. Du veuille que le monstre corsicain, qui detruit le repos de l'Europe, soit terrasse par l'ange que le Tout Рuissant, dans Sa misericorde, nous a donnee pour souverain. Sans parler de mes freres, cette guerre m'a privee d'une relation des plus cheres a mon coeur. Je parle du jeune Nicolas Rostoff, qui avec son enthousiasme n'a pu supporter l'inaction et a quitte l'universite pour aller s'enroler dans l'armee. Eh bien, chere Marieie, je vous avouerai, que, malgre son extreme jeunesse, son depart pour l'armee a ete un grand chagrin pour moi. Le jeune homme, dont je vous parlais cet ete, a tant de noblesse, de veritable jeunesse qu'on rencontre si rarement dans le siecle оu nous vivons parmi nos villards de vingt ans. Il a surtout tant de franchise et de coeur. Il est tellement pur et poetique, que mes relations avec lui, quelque passageres qu'elles fussent, ont ete l'une des plus douees jouissances de mon pauvre coeur, qui a deja tant souffert. Je vous raconterai un jour nos adieux et tout ce qui s'est dit en partant. Tout cela est encore trop frais. Ah! chere amie, vous etes heureuse de ne pas connaitre ces jouissances et ces peines si poignantes. Vous etes heureuse, puisque les derienieres sont ordinairement les plus fortes! Je sais fort bien, que le comte Nicolas est trop jeune pour pouvoir jamais devenir pour moi quelque chose de plus qu'un ami, mais cette douee amitie, ces relations si poetiques et si pures ont ete un besoin pour mon coeur. Mais n'en parlons plus. La grande nouvelle du jour qui occupe tout Moscou est la mort du vieux comte Безухой et son heritage. Figurez vous que les trois princesses n'ont recu que tres peu de chose, le prince Basile rien, est que c'est M. Pierre qui a tout herite, et qui par dessus le Marieche a ete reconnu pour fils legitime, par consequent comte Безухой est possesseur de la plus belle fortune de la Russie. On pretend que le prince Basile a joue un tres vilain role dans toute cette histoire et qu'il est reparti tout penaud pour Petersbourg.
«Je vous avoue, que je comprends tres peu toutes ces affaires de legs et de testament; ce que je sais, c'est que depuis que le jeune homme que nous connaissions tous sous le nom de M. Pierre les tout court est devenu comte Безухой et possesseur de l'une des plus grandes fortunes de la Russie, je m'amuse fort a observer les changements de ton et des manieres des mamans accablees de filles a Marieier et des demoiselles elles memes a l'egard de cet individu, qui, par parenthese, m'a paru toujours etre un pauvre, sire. Comme on s'amuse depuis deux ans a me donner des promis que je ne connais pas le plus souvent, la chronique matrimoniale de Moscou me fait comtesse Безухой. Mais vous sentez bien que je ne me souc nullement de le devenir. A propos de Marieiage, savez vous que tout derienierement la tante en general Анна Михайловна, m'a confie sous le sceau du plus grand secret un projet de Marieiage pour vous. Ce n'est ni plus, ni moins, que le fils du prince Basile, Anatole, qu'on voudrait ranger en le Marieiant a une personne riche et distinguee, et c'est sur vous qu'est tombe le choix des parents. Je ne sais comment vous envisagerez la chose, mais j'ai cru de mon devoir de vous en avertir. On le dit tres beau et tres mauvais sujet; c'est tout ce que j'ai pu savoir sur son compte.
«Mais assez de bavardage comme cela. Je finis mon second feuillet, et maman me fait chercher pour aller diner chez les Apraksines. Lisez le livre mystique que je vous envoie et qui fait fureur chez nous. Quoiqu'il y ait des choses dans ce livre difficiles a atteindre avec la faible conception humaine, c'est un livre admirable dont la lecture calme et eleve l'ame. Adieu. Mes respects a monsieur votre pere et mes compliments a m elle Bourienne. Je vous embrasse comme je vous aime. Julie».
«P.S.Donnez moi des nouvelles de votre frere et de sa charmante petite femme».
[Вся Москва только и говорит что о войне. Один из моих двух братьев уже за границей, другой с гвардией, которая выступает в поход к границе. Наш милый государь оставляет Петербург и, как предполагают, намерен сам подвергнуть свое драгоценное существование случайностям войны. Дай Бог, чтобы корсиканское чудовище, которое возмущает спокойствие Европы, было низвергнуто ангелом, которого Всемогущий в Своей благости поставил над нами повелителем. Не говоря уже о моих братьях, эта война лишила меня одного из отношений самых близких моему сердцу. Я говорю о молодом Николае Ростове; который, при своем энтузиазме, не мог переносить бездействия и оставил университет, чтобы поступить в армию. Признаюсь вам, милая Мари, что, несмотря на его чрезвычайную молодость, отъезд его в армию был для меня большим горем. В молодом человеке, о котором я говорила вам прошлым летом, столько благородства, истинной молодости, которую встречаешь так редко в наш век между двадцатилетними стариками! У него особенно так много откровенности и сердца. Он так чист и полон поэзии, что мои отношения к нему, при всей мимолетности своей, были одною из самых сладостных отрад моего бедного сердца, которое уже так много страдало. Я вам расскажу когда нибудь наше прощанье и всё, что говорилось при прощании. Всё это еще слишком свежо… Ах! милый друг, вы счастливы, что не знаете этих жгучих наслаждений, этих жгучих горестей. Вы счастливы, потому что последние обыкновенно сильнее первых. Я очень хорошо знаю, что граф Николай слишком молод для того, чтобы сделаться для меня чем нибудь кроме как другом. Но эта сладкая дружба, эти столь поэтические и столь чистые отношения были потребностью моего сердца. Но довольно об этом.
«Главная новость, занимающая всю Москву, – смерть старого графа Безухого и его наследство. Представьте себе, три княжны получили какую то малость, князь Василий ничего, а Пьер – наследник всего и, сверх того, признан законным сыном и потому графом Безухим и владельцем самого огромного состояния в России. Говорят, что князь Василий играл очень гадкую роль во всей этой истории, и что он уехал в Петербург очень сконфуженный. Признаюсь вам, я очень плохо понимаю все эти дела по духовным завещаниям; знаю только, что с тех пор как молодой человек, которого мы все знали под именем просто Пьера, сделался графом Безухим и владельцем одного из лучших состояний России, – я забавляюсь наблюдениями над переменой тона маменек, у которых есть дочери невесты, и самих барышень в отношении к этому господину, который (в скобках будь сказано) всегда казался мне очень ничтожным. Так как уже два года все забавляются тем, чтобы приискивать мне женихов, которых я большею частью не знаю, то брачная хроника Москвы делает меня графинею Безуховой. Но вы понимаете, что я нисколько этого не желаю. Кстати о браках. Знаете ли вы, что недавно всеобщая тетушка Анна Михайловна доверила мне, под величайшим секретом, замысел устроить ваше супружество. Это ни более ни менее как сын князя Василья, Анатоль, которого хотят пристроить, женив его на богатой и знатной девице, и на вас пал выбор родителей. Я не знаю, как вы посмотрите на это дело, но я сочла своим долгом предуведомить вас. Он, говорят, очень хорош и большой повеса. Вот всё, что я могла узнать о нем.
Но будет болтать. Кончаю мой второй листок, а маменька прислала за мной, чтобы ехать обедать к Апраксиным.
Прочитайте мистическую книгу, которую я вам посылаю; она имеет у нас огромный успех. Хотя в ней есть вещи, которые трудно понять слабому уму человеческому, но это превосходная книга; чтение ее успокоивает и возвышает душу. Прощайте. Мое почтение вашему батюшке и мои приветствия m lle Бурьен. Обнимаю вас от всего сердца. Юлия.
PS. Известите меня о вашем брате и о его прелестной жене.]
Княжна подумала, задумчиво улыбаясь (при чем лицо ее, освещенное ее лучистыми глазами, совершенно преобразилось), и, вдруг поднявшись, тяжело ступая, перешла к столу. Она достала бумагу, и рука ее быстро начала ходить по ней. Так писала она в ответ:
«Chere et excellente ami. Votre lettre du 13 m'a cause une grande joie. Vous m'aimez donc toujours, ma poetique Julie.
L'absence, dont vous dites tant de mal, n'a donc pas eu son influenсе habituelle sur vous. Vous vous plaignez de l'absence – que devrai je dire moi, si j'osais me plaindre, privee de tous ceux qui me sont chers? Ah l si nous n'avions pas la religion pour nous consoler, la vie serait bien triste. Pourquoi me supposez vous un regard severe, quand vous me parlez de votre affection pour le jeune homme? Sous ce rapport je ne suis rigide que pour moi. Je comprends ces sentiments chez les autres et si je ne puis approuver ne les ayant jamais ressentis, je ne les condamiene pas. Me parait seulement que l'amour chretien, l'amour du prochain, l'amour pour ses ennemis est plus meritoire, plus doux et plus beau, que ne le sont les sentiments que peuvent inspire les beaux yeux d'un jeune homme a une jeune fille poetique et aimante comme vous.
«La nouvelle de la mort du comte Безухой nous est parvenue avant votre lettre, et mon pere en a ete tres affecte. Il dit que c'etait avant derienier representant du grand siecle, et qu'a present c'est son tour; mais qu'il fera son possible pour que son tour vienne le plus tard possible. Que Dieu nous garde de ce terrible malheur! Je ne puis partager votre opinion sur Pierre que j'ai connu enfant. Il me paraissait toujours avoir un coeur excellent, et c'est la qualite que j'estime le plus dans les gens. Quant a son heritage et au role qu'y a joue le prince Basile, c'est bien triste pour tous les deux. Ah! chere amie, la parole de notre divin Sauveur qu'il est plus aise a un hameau de passer par le trou d'une aiguille, qu'il ne l'est a un riche d'entrer dans le royaume de Dieu, cette parole est terriblement vraie; je plains le prince Basile et je regrette encore davantage Pierre. Si jeune et accable de cette richesse, que de tentations n'aura t il pas a subir! Si on me demandait ce que je desirerais le plus au monde, ce serait d'etre plus pauvre que le plus pauvre des mendiants. Mille graces, chere amie, pour l'ouvrage que vous m'envoyez, et qui fait si grande fureur chez vous. Cependant, puisque vous me dites qu'au milieu de plusurs bonnes choses il y en a d'autres que la faible conception humaine ne peut atteindre, il me parait assez inutile de s'occuper d'une lecture inintelligible, qui par la meme ne pourrait etre d'aucun fruit. Je n'ai jamais pu comprendre la passion qu'ont certaines personnes de s'embrouiller l'entendement, en s'attachant a des livres mystiques, qui n'elevent que des doutes dans leurs esprits, exaltant leur imagination et leur donnent un caractere d'exageration tout a fait contraire a la simplicite chretnne. Lisons les Apotres et l'Evangile. Ne cherchons pas a penetrer ce que ceux la renferment de mysterux, car, comment oserions nous, miserables pecheurs que nous sommes, pretendre a nous initier dans les secrets terribles et sacres de la Providence, tant que nous portons cette depouille charienelle, qui eleve entre nous et l'Eterienel un voile impenetrable? Borienons nous donc a etudr les principes sublimes que notre divin Sauveur nous a laisse pour notre conduite ici bas; cherchons a nous y conformer et a les suivre, persuadons nous que moins nous donnons d'essor a notre faible esprit humain et plus il est agreable a Dieu, Qui rejette toute science ne venant pas de Lui;que moins nous cherchons a approfondir ce qu'il Lui a plu de derober a notre connaissance,et plutot II nous en accordera la decouverte par Son divin esprit.
«Mon pere ne m'a pas parle du pretendant, mais il m'a dit seulement qu'il a recu une lettre et attendait une visite du prince Basile. Pour ce qui est du projet de Marieiage qui me regarde, je vous dirai, chere et excellente amie, que le Marieiage, selon moi,est une institution divine a laquelle il faut se conformer. Quelque penible que cela soit pour moi, si le Tout Puissant m'impose jamais les devoirs d'epouse et de mere, je tacherai de les remplir aussi fidelement que je le pourrai, sans m'inquieter de l'examen de mes sentiments a l'egard de celui qu'il me donnera pour epoux. J'ai recu une lettre de mon frere, qui m'annonce son arrivee a Лысые Горы avec sa femme. Ce sera une joie de courte duree, puisqu'il nous quitte pour prendre part a cette malheureuse guerre, a laquelle nous sommes entraines Dieu sait, comment et pourquoi. Non seulement chez vous au centre des affaires et du monde on ne parle que de guerre, mais ici, au milieu de ces travaux champetres et de ce calme de la nature, que les citadins se representent ordinairement a la campagne, les bruits de la guerre se font entendre et sentir peniblement. Mon pere ne parle que Marieche et contreMarieche, choses auxquelles je ne comprends rien; et avant hier en faisant ma promenade habituelle dans la rue du village, je fus temoin d'une scene dechirante… C'etait un convoi des recrues enroles chez nous et expedies pour l'armee… Il fallait voir l'etat dans lequel se trouvant les meres, les femmes, les enfants des hommes qui partaient et entendre les sanglots des uns et des autres!
On dirait que l'humanite a oublie les lois de son divin Sauveur, Qui prechait l'amour et le pardon des offenses, et qu'elle fait consister son plus grand merite dans l'art de s'entretuer.
«Adieu, chere et bonne amie, que notre divin Sauveur et Sa tres Sainte Mere vous aient en Leur sainte et puissante garde. Marieie».
[Милый и бесценный друг. Ваше письмо от 13 го доставило мне большую радость. Вы всё еще меня любите, моя поэтическая Юлия. Разлука, о которой вы говорите так много дурного, видно, не имела на вас своего обычного влияния. Вы жалуетесь на разлуку, что же я должна была бы сказать, если бы смела, – я, лишенная всех тех, кто мне дорог? Ах, ежели бы не было у нас религии для утешения, жизнь была бы очень печальна. Почему приписываете вы мне строгий взгляд, когда говорите о вашей склонности к молодому человеку? В этом отношении я строга только к себе. Я понимаю эти чувства у других, и если не могу одобрять их, никогда не испытавши, то и не осуждаю их. Мне кажется только, что христианская любовь, любовь к ближнему, любовь к врагам, достойнее, слаще и лучше, чем те чувства, которые могут внушить прекрасные глаза молодого человека молодой девушке, поэтической и любящей, как вы.
Известие о смерти графа Безухова дошло до нас прежде вашего письма, и мой отец был очень тронут им. Он говорит, что это был предпоследний представитель великого века, и что теперь черед за ним, но что он сделает все, зависящее от него, чтобы черед этот пришел как можно позже. Избави нас Боже от этого несчастия.
Я не могу разделять вашего мнения о Пьере, которого знала еще ребенком. Мне казалось, что у него было всегда прекрасное сердце, а это то качество, которое я более всего ценю в людях. Что касается до его наследства и до роли, которую играл в этом князь Василий, то это очень печально для обоих. Ах, милый друг, слова нашего Божественного Спасителя, что легче верблюду пройти в иглиное ухо, чем богатому войти в царствие Божие, – эти слова страшно справедливы. Я жалею князя Василия и еще более Пьера. Такому молодому быть отягощенным таким огромным состоянием, – через сколько искушений надо будет пройти ему! Если б у меня спросили, чего я желаю более всего на свете, – я желаю быть беднее самого бедного из нищих. Благодарю вас тысячу раз, милый друг, за книгу, которую вы мне посылаете и которая делает столько шуму у вас. Впрочем, так как вы мне говорите, что в ней между многими хорошими вещами есть такие, которых не может постигнуть слабый ум человеческий, то мне кажется излишним заниматься непонятным чтением, которое по этому самому не могло бы принести никакой пользы. Я никогда не могла понять страсть, которую имеют некоторые особы, путать себе мысли, пристращаясь к мистическим книгам, которые возбуждают только сомнения в их умах, раздражают их воображение и дают им характер преувеличения, совершенно противный простоте христианской.