ро-метод Полларда для дискретного логарифмирования
ро-метод Полларда для дискретного логарифмирования (<math>\rho</math>-метод) — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Предложен британским математиком Джоном Поллардом (англ. John Pollard) в 1978 году, основные идеи алгоритма очень похожи на идеи ро-алгоритма Полларда для факторизации чисел. Данный метод рассматривается для группы ненулевых вычетов по модулю <math>p</math>, где <math>p</math> — простое число, большее <math>3</math>.
Содержание
Постановка задачи дискретного логарифмирования
Для заданного простого числа <math>p </math> и двух целых чисел <math>a </math> и <math>b </math> требуется найти целое число <math>x </math>, удовлетворяющее сравнению:
| <math>a^x\equiv b\;\pmod{p},</math> | (1) |
где <math>b </math> является элементом циклической группы <math>G </math>, порожденной элементом <math>a </math>.
Алгоритм ро-метода
Рассматриваются последовательность пар <math>\{u_i,\ v_i\} </math> целых чисел по модулю <math>p-1 </math> и последовательность <math>\{z_i\} </math> целых чисел по модулю <math>p </math>, определенные следующим образом :
| <math>\{u_i\}, \{v_i\}, \{z_i\},\ i\in N,</math> | (2) |
| 3 |
| 4 |
| <math>z_{i+1}\equiv b^{u_{i+1 |
z_i^2\;\bmod\;p, & \frac{p}{3}<z_i<\frac{2}{3}p;\\ az_i\;\bmod\;p, & \frac{2}{3}p<z_i<p; \end{cases}</math>|5}}
Замечание: во всех выражениях рассматривается наименьшие неотрицательные вычеты.
Замечание 2: в более общем случае возможно разбиение на 3 подмножества несколько иным способом: разбиваем группу <math>G</math> на три примерно равных по мощности подмножества <math>S_1, S_2, S_3</math> так, чтобы <math>1</math> не принадлежала подмножеству <math>S_2</math>.
Поскольку каждая треть отрезка, которой принадлежит элемент, вероятно, никак не связана с элементами последовательностей <math>\{u_i, v_i\} </math>, полученная последовательность — псевдослучайная. Поэтому могут существовать такие числа <math>j </math> и <math>k </math>, что <math>z_k = z_j </math>. Если удастся найти такую пару чисел, то получится:
| <math>b^{u_j}a^{v_j}\equiv b^{u_k}a^{v_k} \pmod{p}.</math> | (6) |
Если число <math>u_j - u_k </math> взаимно простое с числом <math>p - 1 </math>, то это сравнение можно решить и найти дискретный логарифм:
| <math>b^{u_j - u_k}\equiv a^{v_k - v_j} \pmod{p}.</math> |
| <math>x\equiv\log_a{b}\equiv(u_j-u_k)^{-1}(v_k-v_j)\pmod{p-1}.</math> | (7) |
Если же наибольший общий делитель чисел <math>u_j - u_k </math> и <math>p - 1 </math> равен числу <math>d > 1 </math>, то существует решение этого сравнения для <math>x </math> по модулю <math>(p - 1) / d </math>. Пусть <math>x = x_0 </math> <math> (mod (p - 1)/d) </math>, тогда искомое число <math>x = x_0 + m (p - 1)/d </math>, где <math>m </math> может принимать значения <math>0, 1, ... , d - 1 </math>. Поэтому если <math>d </math> — достаточно небольшое число, то задача решается перебором всех возможных значений для <math>m </math>. В худшем случае — когда <math>d = p - 1 </math> — метод оказывается ничем не лучше полного перебора всех возможных значений для дискретного логарифма.
Для поиска индексов <math>j </math> и <math>k </math> используется алгоритм поиска циклов Флойда. При использовании данного алгоритма на <math>i </math>-м шаге имеются значения <math>(z_i,\ u_i,\ v_i,\ z_{2i},\ u_{2i},\ v_{2i})</math> и ищется номер <math>i </math>, для которого <math>z_i = z_{2i}</math>. Наименьшее значение <math>i </math>, при котором выполняется данное условие, называется епактой. Если при этом <math>(u_{2i}-u_i,\ p-1)=1</math>, то
| <math>x\equiv\log_a{b}\equiv(u_{2i}-u_i)^{-1}(v_{i}-v_{2i})\pmod{p-1
}.</math> |
(8) |
Pо-метод для группы точек эллиптической кривой
Пусть задана группа точек эллиптической кривой (ЭК) <math>E(F_p)</math>. Не ограничивая общности, можно предположить, что <math>p > 3</math> и <math>p</math> — простое число. Обозначим подгруппу <math>E(F_p)</math> порядка <math>n</math> через <math>G</math> и зафиксируем порождающий элемент <math>P</math>. Для произвольного элемента группы <math>Q = xP</math> задача дискретного логарифмирования заключается в нахождении элемента <math> 1 < x < n.</math>
Группа <math>G</math> представляется в виде объединения <math>G = S_1 \cup S_2 \cup S_3</math>, где <math>S_i </math> — произвольные множества приблизительно одинаковой мощности. Функция итерирования <math>f\colon G \to G</math> определяется как
| 9 |
| 10 |
| 11 |
</math>. Исходя из формул (10) и (11), решается задача дискретного логарифмирования:
| {{{1}}} |
Сложность алгоритма
Основная работа алгоритма состоит в вычислении последовательностей <math>\{x_i\}, \{x_{2i}\} </math>. Данные вычисления требуют трех умножений по модулю для перехода к следующей итерации. Размер необходимой памяти при этом минимален, поскольку нет необходимости хранения информации о всех предыдущих элементах последовательностей. Таким образом, сложность алгоритма сводится к сложности задачи нахождения епакты, которая, в свою очередь, имеет эвристическую оценку сложности <math>O(\sqrt p)</math>, причем для разных случаев значения константы <math>C\sqrt p</math> могут довольно сильно отличаться, но, как правило лежат в пределах <math>[1;3]</math>.
Сравнение с другими алгоритмами
По сравнению с другими алгоритмами дискретного логарифмирования алгоритм <math>\rho-</math>Полларда является менее затратным как по отношению к бинарным операциям, так и по отношению к необходимому количеству памяти. Например, при достаточно больших значениях числа <math>p</math> данный алгоритм является более эффективным по сложности, чем алгоритм COS и алгоритм Адлемана, имеющие сложность <math>O(exp{((\log{p}\log{\log{p}})^{1/2})})</math>. В сравнении с алгоритмом Шенкса, также имеющим сложность <math>O(\sqrt p)</math>, алгоритм Полларда является более выгодным по отношению к используемой памяти — для алгоритма Шенкса требуется <math>O(p)</math> памяти, в то время как для данного алгоритма размер требуемой памяти постоянен (при условии использования алгоритма поиска циклов Флойда).
Распараллеливание метода
Системы с распределенной памятью
Идея метода <math>\rho-</math>Полларда для систем с распределенной памятью состоит в разделении итерирования точек между клиентскими рабочими станциями и поиска коллизии сервером. Пусть задано множество клиентских рабочих станций <math>S = \left \{ S_i \mid i = 1 ... r\right \}.</math> Сервер определяет параметры, общие для системы, некоторое подмножество<math> D \subset G</math> и выполняет инициализацию рабочих станций. Клиентская рабочая станция <math>S_i </math> строит последовательность точек <math>R_{ij} \subset D</math> и отправляет поэлементно точки на сервер. Если точка не содержится в базе данных, сервер добавляет точку в базу данных, иначе вычисляет значение дискретного логарифма.
Системы с общей памятью
Идея такого метода состоит в распараллеливании отдельно функции итерирования и алгоритма обнаружения коллизии. Функция итерирования распараллеливается на этапе вычисления последовательностей <math>R_i</math> и <math>R_{2i}</math>.Следует отметить, что параллельное вычисление<math>R_{i_0}</math> и <math>R_{2i_0} </math> для фиксированного значения <math>i_0</math> и последующее сравнение является неэффективным. Это объясняется тем фактом, что накладные расходы, связанные с использованием потоков, являются вычислительно более затратными, чем вычисление <math>R_{2i_0} = f (R_{2i_{0} - 2})</math>.Таким образом, целесообразно вычислять последовательности так, чтобы накладные расходы нивелировались. Это может быть достигнуто организацией вычислений последовательностей вида <math>\left \{ R_{iw+j}\right \}^l_{i=0}</math> и <math>\left \{ R_{2(iw+j)}\right \}^l_{i=0}</math>, где <math>w</math> — размер блока вычислений, <math>0 \leqslant j < w, l = \left \lceil \frac{m}{w} \right \rceil</math>. Функция обнаружения коллизии в методе <math>\rho-</math>Полларда сравнивает значения <math>R_m</math> и <math>R_{2m}</math>. Такое сравнение можно распараллелить, если использовать алгоритм итерирования для систем с общей памятью. Результатом выполнения функции итерирования точек являются два множества точек <math>\left \{ R_{i}\right \}^w_{i=0}</math> и <math>\left \{ R_{2i}\right \}^w_{i=0}</math>,сравнение которых осуществляется по блокам, то есть <math>R_i = R_{2i}, i = 1 ...\frac{w}{2}</math> и <math>R_i = R_{2i}, i = \frac{w}{2} ... w</math> в случае с двумя ядрами.
Комбинированный метод
Метод <math>\rho-</math>Полларда для систем с распределенной памятью может быть расширен для использования на многоядерных рабочих станциях. Идея метода состоит в том, что итерирование точек клиентскими рабочими станциями происходит в соответствии с определенным алгоритмом, суть которого в том, что есть клиентская рабочая станция <math>S_i </math> строит последовательность точек <math>\left \{ R_{ij}\right \}^w_{j=0}</math>. Далее рабочая станция <math>S_i </math> выбирает подмножество точек <math>\left \{ R_{ij}\right \}^w_{j=0} \cap D</math> и отправляет его серверу. Проверка на принадлежность подмножеству осуществляется в параллельном режиме: <math>R_{ij} \in D, i = 1 ...\frac{w}{2}</math> и <math>R_{ij} \in D, i = \frac{w}{2} ... w</math> (в случае с двумя ядрами). Сервер добавляет точки и <math>\left \{ R_{ij}\right \}^w_{j=0} \cap D</math> в базу данных до тех пор, пока не найдет уже существующую точку.
Модификации и оптимизации
Существует несколько значительных улучшений алгоритма, основанных на различных приемах.
Одно из улучшений описано в работе [Teske 1998]. Отличие приведенного в работе метода заключается в усложненной итерационной функции — она содержит 20 различных веток вместо описанных выше трех. Численные эксперименты показывают, что такое улучшение приводит к ускорению работы алгоритма случайного блуждания в среднем на 20 %.
<math>\Lambda-</math>метод Полларда
В работе по вычислению дискретных логарифмов Поллардом также был предложен <math>\lambda-</math>метод, названный так потому, что форма греческой буквы напоминает изображение двух путей, соединяющихся в один. Идея метода состоит в том, чтобы идти сразу двумя путями: одним от числа <math>b</math>, чей дискретный логарифм надо найти, другим от числа <math>B</math>, чей дискретный логарифм уже известен. Если эти два пути сойдутся, появляется возможность найти дискретный логарифм числа <math>b</math>. Поллард предложил рассматривать шаги на каждом пути как прыжки кенгуру, поэтому этот алгоритм иногда называют «методом кенгуру». Если известно, что искомый дискретный логарифм лежит в некотором коротком интервале, то можно адаптировать метод кенгуру, а именно, использовать кенгуру с более короткими прыжками.
Одним важным свойством лямбда-метода является тот факт, что он легко распределяется на несколько компьютеров. Каждый участник распределенных вычислений выбирает случайное число <math>r</math> и начинает делать псевдослучайные шаги от числа <math>b^r</math>, где <math>b</math> — элемент группы, для которого ищется дискретный логарифм. Каждый участник использует одну и ту же легко вычислимую псевдослучайную функцию <math>f\colon G \to S</math>, где <math>S</math> — относительно небольшое множество чисел со средним значением, сравнимым с размером группы <math>G</math>, имеющей порядок <math>n</math>. Степени <math>a^s</math> для <math>s \in S</math> вычисляются заранее. Тогда «блуждание», начиная с элемента <math>b^r</math>, принимает вид: <math>w_0 = b^r, w_1 = w_0a^{f(w_0)}, w_2 = w_1a^{f(w_1)}, ...</math>
Пусть другой участник, выбрав начальное число <math>r^\prime</math> , получил последовательность <math>w^\prime_0, w^\prime_1, w^\prime_2, ...</math> Если она пересекается с последовательностью <math>w_0, w_1, w_2, ...</math> , то есть <math>w^\prime_i = w_j</math> при некоторых <math>i, j</math>, то, учитывая, что <math>b = a^x</math>, выполняется:
| 13 |
| 14 |
Возможно использование псевдослучайной функции <math> (5)</math>. В таком случае будут полезны все совпадения: совпадение внутри одной последовательности также может быть использовано для вычисления дискретного логарифма. В случае такого совпадения <math>\lambda-</math>метод просто превращается в <math>\rho-</math>метод. Однако, если известно, что искомый дискретный логарифм лежит в коротком интервале, то можно использовать первоначальный метод. Тогда время работы будет около квадратного корня из длины интервала. В этом случае среднее значение целых чисел из множества <math>S</math> должно быть меньше для того, чтобы «кенгуру» прыгали только по интервалу нужной длины.
Центральный компьютер должен отслеживать все последовательности от всех участников для выявления совпадений. Согласно парадоксу дней рождения, совпадение ожидается, когда количество элементов во всех последовательностях будет порядка <math>O(\sqrt{n})</math>). Очевидно, что в описанном виде этот метод требует больших затрат памяти центрального компьютера. Следующая идея, описанная в работе ван Оршотом, сильно уменьшает требования к памяти и, таким образом, делает этот метод применимым к решению сложных проблем. Идея состоит в рассмотрении так называемых выделенных точек. Предполагается, что элементы группы представляются целыми числами (или, возможно, наборами целых чисел). Выделенное двоичное поле длины <math> k</math> в таком числе будет состоять из одних нулей примерно <math>1/2k</math> -ю часть всего времени. Случайное блуждание будет проходить через такие выделенные точки в среднем через каждые <math>2^k</math> шагов. Если две случайные последовательности где-нибудь пересекутся, то они будут пересекаться и дальше и вместе попадут в следующую выделенную точку. Итак, идея состоит в отправке на центральный компьютер только этих выделенных точек, что уменьшит необходимый размер памяти в <math>2^k</math> раз.
Напишите отзыв о статье "Ро-метод Полларда для дискретного логарифмирования"
Литература
- Василенко О.Н. [www.ict.edu.ru/ft/002416/book.pdf Теоретико-числовые алгоритмы в криптографии]. — М.: МЦНМО, 2003. — С. 328. — ISBN 5-94057-103-4.
- Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты. — М.: УРСС, 2011 — С.664. — ISBN 978-5-453-00016-6
- Pollard, J. M. [www.ams.org/journals/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf Monte Carlo methods for index computation (mod p). Mathematics of Computation] — 32 (143), 1978—918—924 — JSTOR 2006496
- Teske, Speeding up Pollard’s rho method for computing discrete logarithms. Algorithmic Number Theory Symposium (ANTS IV), 1998—541—553
- Горбенко И. Д., Качко Е. Г. [hpc-ua.org/hpc-ua-12/files/proceedings/32.pdf Методы распараллеливания алгоритма Полларда решения задачи дискретного логарифмирования для систем с общей памятью] — 2012
- P.C. van Oorschot, M.J. Wiener Parallel collision search with cryptanalytic applications — Journal of Cryptology 12 (1) — 1-28 — 1999
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Ро-метод Полларда для дискретного логарифмирования
Наполеон чуть поворотил голову назад и отвел назад свою маленькую пухлую ручку, как будто желая взять что то. Лица его свиты, догадавшись в ту же секунду в чем дело, засуетились, зашептались, передавая что то один другому, и паж, тот самый, которого вчера видел Ростов у Бориса, выбежал вперед и почтительно наклонившись над протянутой рукой и не заставив ее дожидаться ни одной секунды, вложил в нее орден на красной ленте. Наполеон, не глядя, сжал два пальца. Орден очутился между ними. Наполеон подошел к Лазареву, который, выкатывая глаза, упорно продолжал смотреть только на своего государя, и оглянулся на императора Александра, показывая этим, что то, что он делал теперь, он делал для своего союзника. Маленькая белая рука с орденом дотронулась до пуговицы солдата Лазарева. Как будто Наполеон знал, что для того, чтобы навсегда этот солдат был счастлив, награжден и отличен от всех в мире, нужно было только, чтобы его, Наполеонова рука, удостоила дотронуться до груди солдата. Наполеон только прило жил крест к груди Лазарева и, пустив руку, обратился к Александру, как будто он знал, что крест должен прилипнуть к груди Лазарева. Крест действительно прилип.Русские и французские услужливые руки, мгновенно подхватив крест, прицепили его к мундиру. Лазарев мрачно взглянул на маленького человечка, с белыми руками, который что то сделал над ним, и продолжая неподвижно держать на караул, опять прямо стал глядеть в глаза Александру, как будто он спрашивал Александра: всё ли еще ему стоять, или не прикажут ли ему пройтись теперь, или может быть еще что нибудь сделать? Но ему ничего не приказывали, и он довольно долго оставался в этом неподвижном состоянии.
Государи сели верхами и уехали. Преображенцы, расстроивая ряды, перемешались с французскими гвардейцами и сели за столы, приготовленные для них.
Лазарев сидел на почетном месте; его обнимали, поздравляли и жали ему руки русские и французские офицеры. Толпы офицеров и народа подходили, чтобы только посмотреть на Лазарева. Гул говора русского французского и хохота стоял на площади вокруг столов. Два офицера с раскрасневшимися лицами, веселые и счастливые прошли мимо Ростова.
– Каково, брат, угощенье? Всё на серебре, – сказал один. – Лазарева видел?
– Видел.
– Завтра, говорят, преображенцы их угащивать будут.
– Нет, Лазареву то какое счастье! 10 франков пожизненного пенсиона.
– Вот так шапка, ребята! – кричал преображенец, надевая мохнатую шапку француза.
– Чудо как хорошо, прелесть!
– Ты слышал отзыв? – сказал гвардейский офицер другому. Третьего дня было Napoleon, France, bravoure; [Наполеон, Франция, храбрость;] вчера Alexandre, Russie, grandeur; [Александр, Россия, величие;] один день наш государь дает отзыв, а другой день Наполеон. Завтра государь пошлет Георгия самому храброму из французских гвардейцев. Нельзя же! Должен ответить тем же.
Борис с своим товарищем Жилинским тоже пришел посмотреть на банкет преображенцев. Возвращаясь назад, Борис заметил Ростова, который стоял у угла дома.
– Ростов! здравствуй; мы и не видались, – сказал он ему, и не мог удержаться, чтобы не спросить у него, что с ним сделалось: так странно мрачно и расстроено было лицо Ростова.
– Ничего, ничего, – отвечал Ростов.
– Ты зайдешь?
– Да, зайду.
Ростов долго стоял у угла, издалека глядя на пирующих. В уме его происходила мучительная работа, которую он никак не мог довести до конца. В душе поднимались страшные сомнения. То ему вспоминался Денисов с своим изменившимся выражением, с своей покорностью и весь госпиталь с этими оторванными руками и ногами, с этой грязью и болезнями. Ему так живо казалось, что он теперь чувствует этот больничный запах мертвого тела, что он оглядывался, чтобы понять, откуда мог происходить этот запах. То ему вспоминался этот самодовольный Бонапарте с своей белой ручкой, который был теперь император, которого любит и уважает император Александр. Для чего же оторванные руки, ноги, убитые люди? То вспоминался ему награжденный Лазарев и Денисов, наказанный и непрощенный. Он заставал себя на таких странных мыслях, что пугался их.
Запах еды преображенцев и голод вызвали его из этого состояния: надо было поесть что нибудь, прежде чем уехать. Он пошел к гостинице, которую видел утром. В гостинице он застал так много народу, офицеров, так же как и он приехавших в статских платьях, что он насилу добился обеда. Два офицера одной с ним дивизии присоединились к нему. Разговор естественно зашел о мире. Офицеры, товарищи Ростова, как и большая часть армии, были недовольны миром, заключенным после Фридланда. Говорили, что еще бы подержаться, Наполеон бы пропал, что у него в войсках ни сухарей, ни зарядов уж не было. Николай молча ел и преимущественно пил. Он выпил один две бутылки вина. Внутренняя поднявшаяся в нем работа, не разрешаясь, всё также томила его. Он боялся предаваться своим мыслям и не мог отстать от них. Вдруг на слова одного из офицеров, что обидно смотреть на французов, Ростов начал кричать с горячностью, ничем не оправданною, и потому очень удивившею офицеров.
– И как вы можете судить, что было бы лучше! – закричал он с лицом, вдруг налившимся кровью. – Как вы можете судить о поступках государя, какое мы имеем право рассуждать?! Мы не можем понять ни цели, ни поступков государя!
– Да я ни слова не говорил о государе, – оправдывался офицер, не могший иначе как тем, что Ростов пьян, объяснить себе его вспыльчивости.
Но Ростов не слушал.
– Мы не чиновники дипломатические, а мы солдаты и больше ничего, – продолжал он. – Умирать велят нам – так умирать. А коли наказывают, так значит – виноват; не нам судить. Угодно государю императору признать Бонапарте императором и заключить с ним союз – значит так надо. А то, коли бы мы стали обо всем судить да рассуждать, так этак ничего святого не останется. Этак мы скажем, что ни Бога нет, ничего нет, – ударяя по столу кричал Николай, весьма некстати, по понятиям своих собеседников, но весьма последовательно по ходу своих мыслей.
– Наше дело исполнять свой долг, рубиться и не думать, вот и всё, – заключил он.
– И пить, – сказал один из офицеров, не желавший ссориться.
– Да, и пить, – подхватил Николай. – Эй ты! Еще бутылку! – крикнул он.
В 1808 году император Александр ездил в Эрфурт для нового свидания с императором Наполеоном, и в высшем Петербургском обществе много говорили о величии этого торжественного свидания.
В 1809 году близость двух властелинов мира, как называли Наполеона и Александра, дошла до того, что, когда Наполеон объявил в этом году войну Австрии, то русский корпус выступил за границу для содействия своему прежнему врагу Бонапарте против прежнего союзника, австрийского императора; до того, что в высшем свете говорили о возможности брака между Наполеоном и одной из сестер императора Александра. Но, кроме внешних политических соображений, в это время внимание русского общества с особенной живостью обращено было на внутренние преобразования, которые были производимы в это время во всех частях государственного управления.
Жизнь между тем, настоящая жизнь людей с своими существенными интересами здоровья, болезни, труда, отдыха, с своими интересами мысли, науки, поэзии, музыки, любви, дружбы, ненависти, страстей, шла как и всегда независимо и вне политической близости или вражды с Наполеоном Бонапарте, и вне всех возможных преобразований.
Князь Андрей безвыездно прожил два года в деревне. Все те предприятия по именьям, которые затеял у себя Пьер и не довел ни до какого результата, беспрестанно переходя от одного дела к другому, все эти предприятия, без выказыванья их кому бы то ни было и без заметного труда, были исполнены князем Андреем.
Он имел в высшей степени ту недостававшую Пьеру практическую цепкость, которая без размахов и усилий с его стороны давала движение делу.
Одно именье его в триста душ крестьян было перечислено в вольные хлебопашцы (это был один из первых примеров в России), в других барщина заменена оброком. В Богучарово была выписана на его счет ученая бабка для помощи родильницам, и священник за жалованье обучал детей крестьянских и дворовых грамоте.
Одну половину времени князь Андрей проводил в Лысых Горах с отцом и сыном, который был еще у нянек; другую половину времени в богучаровской обители, как называл отец его деревню. Несмотря на выказанное им Пьеру равнодушие ко всем внешним событиям мира, он усердно следил за ними, получал много книг, и к удивлению своему замечал, когда к нему или к отцу его приезжали люди свежие из Петербурга, из самого водоворота жизни, что эти люди, в знании всего совершающегося во внешней и внутренней политике, далеко отстали от него, сидящего безвыездно в деревне.
Кроме занятий по именьям, кроме общих занятий чтением самых разнообразных книг, князь Андрей занимался в это время критическим разбором наших двух последних несчастных кампаний и составлением проекта об изменении наших военных уставов и постановлений.
Весною 1809 года, князь Андрей поехал в рязанские именья своего сына, которого он был опекуном.
Пригреваемый весенним солнцем, он сидел в коляске, поглядывая на первую траву, первые листья березы и первые клубы белых весенних облаков, разбегавшихся по яркой синеве неба. Он ни о чем не думал, а весело и бессмысленно смотрел по сторонам.
Проехали перевоз, на котором он год тому назад говорил с Пьером. Проехали грязную деревню, гумны, зеленя, спуск, с оставшимся снегом у моста, подъём по размытой глине, полосы жнивья и зеленеющего кое где кустарника и въехали в березовый лес по обеим сторонам дороги. В лесу было почти жарко, ветру не слышно было. Береза вся обсеянная зелеными клейкими листьями, не шевелилась и из под прошлогодних листьев, поднимая их, вылезала зеленея первая трава и лиловые цветы. Рассыпанные кое где по березнику мелкие ели своей грубой вечной зеленью неприятно напоминали о зиме. Лошади зафыркали, въехав в лес и виднее запотели.
Лакей Петр что то сказал кучеру, кучер утвердительно ответил. Но видно Петру мало было сочувствования кучера: он повернулся на козлах к барину.
– Ваше сиятельство, лёгко как! – сказал он, почтительно улыбаясь.
– Что!
– Лёгко, ваше сиятельство.
«Что он говорит?» подумал князь Андрей. «Да, об весне верно, подумал он, оглядываясь по сторонам. И то зелено всё уже… как скоро! И береза, и черемуха, и ольха уж начинает… А дуб и не заметно. Да, вот он, дуб».
На краю дороги стоял дуб. Вероятно в десять раз старше берез, составлявших лес, он был в десять раз толще и в два раза выше каждой березы. Это был огромный в два обхвата дуб с обломанными, давно видно, суками и с обломанной корой, заросшей старыми болячками. С огромными своими неуклюжими, несимметрично растопыренными, корявыми руками и пальцами, он старым, сердитым и презрительным уродом стоял между улыбающимися березами. Только он один не хотел подчиняться обаянию весны и не хотел видеть ни весны, ни солнца.
«Весна, и любовь, и счастие!» – как будто говорил этот дуб, – «и как не надоест вам всё один и тот же глупый и бессмысленный обман. Всё одно и то же, и всё обман! Нет ни весны, ни солнца, ни счастия. Вон смотрите, сидят задавленные мертвые ели, всегда одинакие, и вон и я растопырил свои обломанные, ободранные пальцы, где ни выросли они – из спины, из боков; как выросли – так и стою, и не верю вашим надеждам и обманам».
Князь Андрей несколько раз оглянулся на этот дуб, проезжая по лесу, как будто он чего то ждал от него. Цветы и трава были и под дубом, но он всё так же, хмурясь, неподвижно, уродливо и упорно, стоял посреди их.
«Да, он прав, тысячу раз прав этот дуб, думал князь Андрей, пускай другие, молодые, вновь поддаются на этот обман, а мы знаем жизнь, – наша жизнь кончена!» Целый новый ряд мыслей безнадежных, но грустно приятных в связи с этим дубом, возник в душе князя Андрея. Во время этого путешествия он как будто вновь обдумал всю свою жизнь, и пришел к тому же прежнему успокоительному и безнадежному заключению, что ему начинать ничего было не надо, что он должен доживать свою жизнь, не делая зла, не тревожась и ничего не желая.
По опекунским делам рязанского именья, князю Андрею надо было видеться с уездным предводителем. Предводителем был граф Илья Андреич Ростов, и князь Андрей в середине мая поехал к нему.
Был уже жаркий период весны. Лес уже весь оделся, была пыль и было так жарко, что проезжая мимо воды, хотелось купаться.
Князь Андрей, невеселый и озабоченный соображениями о том, что и что ему нужно о делах спросить у предводителя, подъезжал по аллее сада к отрадненскому дому Ростовых. Вправо из за деревьев он услыхал женский, веселый крик, и увидал бегущую на перерез его коляски толпу девушек. Впереди других ближе, подбегала к коляске черноволосая, очень тоненькая, странно тоненькая, черноглазая девушка в желтом ситцевом платье, повязанная белым носовым платком, из под которого выбивались пряди расчесавшихся волос. Девушка что то кричала, но узнав чужого, не взглянув на него, со смехом побежала назад.
Князю Андрею вдруг стало от чего то больно. День был так хорош, солнце так ярко, кругом всё так весело; а эта тоненькая и хорошенькая девушка не знала и не хотела знать про его существование и была довольна, и счастлива какой то своей отдельной, – верно глупой – но веселой и счастливой жизнию. «Чему она так рада? о чем она думает! Не об уставе военном, не об устройстве рязанских оброчных. О чем она думает? И чем она счастлива?» невольно с любопытством спрашивал себя князь Андрей.
Граф Илья Андреич в 1809 м году жил в Отрадном всё так же как и прежде, то есть принимая почти всю губернию, с охотами, театрами, обедами и музыкантами. Он, как всякому новому гостю, был рад князю Андрею, и почти насильно оставил его ночевать.
В продолжение скучного дня, во время которого князя Андрея занимали старшие хозяева и почетнейшие из гостей, которыми по случаю приближающихся именин был полон дом старого графа, Болконский несколько раз взглядывая на Наташу чему то смеявшуюся и веселившуюся между другой молодой половиной общества, всё спрашивал себя: «о чем она думает? Чему она так рада!».
Вечером оставшись один на новом месте, он долго не мог заснуть. Он читал, потом потушил свечу и опять зажег ее. В комнате с закрытыми изнутри ставнями было жарко. Он досадовал на этого глупого старика (так он называл Ростова), который задержал его, уверяя, что нужные бумаги в городе, не доставлены еще, досадовал на себя за то, что остался.
