Алгоритм Берлекэмпа

Не следует путать с алгоритмом Берлекэмпа — Мэсси — алгоритмом, предназначенным для нахождения реккурентных зависимостей в последовательностях.

Алгоритм Берлекэмпа — алгоритм, предназначенный для факторизации унитарных многочленов над конечным полем. Разработан Элвином Берлекэмпом в 1967 году. Может использоваться также для проверки неприводимости многочленов над конечными полями. Основная идея алгоритма заключается в возможности представления исходного многочлена в виде произведения наибольших общих делителей самого многочлена и некоторых многочленов, которые с точностью до свободного члена являются <math>f</math>-разлагающими.

Алгоритм Берлекэмпа имеет большую вычислительную сложность, поэтому был разработан ряд дополнительных методов, позволяющих сократить количество необходимых математических операций. Однако, несмотря на свою сложность, алгоритм Берлекэмпа был реализован в системах компьютерной алгебры. Алгоритм нашёл широкое применение в теории кодирования и в изучении линейных рекуррентных соотношений в конечных полях. Имеется много вычислительных задач в алгебре и в теории чисел, которые так или иначе связаны с разложением многочленов над конечными полями, например, разложение на множители многочленов над кольцом целых чисел, отыскание разложения простого рационального числа в поле алгебраических чисел, вычисление группы Галуа некоторого уравнения над полем рациональных чисел и построение расширений полей.

История создания

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

Алгоритм был впервые изложен в статье «Factoring Polynomials Over Finite Fields» и позже воспроизведён в книге «Algebraic Coding Theory». В этой работе 1967 года Берлекэмп пишет, что проблема факторизации возникает в трудах Голомба. Однако, возможность использования матрицы <math>B</math> для определения числа нормированных сомножителей многочлена <math>f(x)</math> была впервые замечена в статье Карела Петра. В статье Батлера было установлено, что ранг матрицы <math>B-E</math> равен <math>n-k</math>, другое доказательство этого факта было дано Шварцем.

Алгоритм Берлекэмпа упоминался во множестве работ и являлся основным алгоритмом решения проблемы факторизации до появления в 1981 году алгоритма Кантора — Цассенхауза. Была разработанна техника позволяющая разложить многочлен на множители за <math> O( n^{(\omega+1)/2+o(1)}+n^{1+o(1)} \log q ),</math> где <math>\omega</math> — показатель в оценке сложности перемножения квадратных матриц.

Постановка и определения

Рассматривается задача факторизации многочлена <math>f(x)</math> степени <math>n</math> (<math>n \ge 2</math>) над конечным полем <math>\Bbb{F}_q</math> (<math>q=p^m</math>, <math>p</math> — простое число) на различные неприводимые унитарные многочлены <math>f(x) = f_1(x)^{e_1} \cdots f_k(x)^{e_k}</math>.

Для использования в алгоритме строится матрица <math>B=(b_{ij})_{i=0,\;j=0}^{n-1,\; n-1}</math> согласно следующим условиям:

<math>{x^{iq}} \equiv \sum^{n-1}_{j=0} b_{ij} x^j \pmod{f(x)}\quad i=\overline{0,n-1}</math>.

Многочлен <math>h(x) \in \Bbb{F}_q[x]</math> такой, что <math> 1 \leqslant \deg{h(x)} < n, \quad {h(x)}^q \equiv h(x) \pmod{f(x)}</math>, называется <math>f</math>-разлагающим многочленом.

Основной случай

Алгоритм факторизации над конечным полем <math>\Bbb{F}_q</math> многочлена вида:

<math>f(x) = f_1(x) \cdots f_k(x)</math>

состоит из следующих шагов:

1. Вычисление матрицы <math>B</math>.
2. Поиск базиса <math>\overline{e_1},\dots ,\overline{e_k}</math> подпространства решений системы линейных уравнений:

   <math>(B-E_n)^T \bold x = \bold 0</math>,

   при этом удаётся выбрать вектор <math>\overline{e_1} = (1,\;0,\;....\;,\;0)</math>, так как он всегда будет присутствовать в базисе пространства решений ввиду того, что <math>x^{i q} \equiv 1\pmod{f(x)}</math> при <math>i=0</math>.

3. Найденное число <math>k</math> есть число неприводимых делителей <math>f(x)</math>.
   • Если <math>k=1</math>, то многочлен является неприводимым.
   • Если <math>k>1</math>, то вектора <math>\overline{e_l}</math> имеют вид <math>(h_{l,\;0}, \dots , h_{l,\;n-1})</math>. По этим числам строятся <math>f</math>-разлагающие многочлены:

     <math>h_l(x) = \sum^{n-1}_{i=0} h_{l,\;i}\;x^i, \quad l=\overline{2,\;k}, \quad h_1(x)=1.</math>.

4. Поиск разложения:

   <math>f(x) = \prod_{c \in \mathbb{F}_q, } \gcd(f(x),h_2(x)-c)</math>

   в виде:

   <math>f(x) = \prod_m g_{m,\;2}(x)</math>,

   где <math>g_{m,\;s}(x), \quad s = \overline{2, k}</math> в общем случае не являются неприводимыми. Функции <math>g_{m,\;s}(x)</math> факторизуются таким же способом, то есть:

   <math>g_{m,\;s}(x) = \prod_{c \in \mathbb{F}_q, } \gcd(g_{m,\;s}(x),h_{s+1}(x)-c), \quad s = \overline{2, k-1}</math>.

Общий случай

Задача факторизации произвольного унитарного многочлена сводится к рассмотрению основного случая. Для этого вычисляется многочлен

<math>d(x) = \gcd(f(x),\;f^{'}(x))</math>

с применением алгоритма Евклида.

• Если <math>d(x) = 1,</math> то многочлен не содержит кратных корней, так как кратный корень одновременно является и корнем производной.
• Если <math>d(x) = f(x),</math> то <math>f^{'}(x) = 0,</math> и значит <math>f(x) = g(x)^p,\quad g(x)\in \Bbb{F}_q [x].</math> Если <math>g^{'}(x) = 0,</math> то для <math>g(x)</math> необходимо проделать описанную процедуру до тех пор пока не будет получено разложение <math>f(x) = h(x)^{p^s}, h{'}(x) \ne 0.</math> Многочлен <math>h(x)</math> удовлетворяет требованиям основного случая.
• Иначе, многочлен <math>d(x)</math> является нетривиальным делителем многочлена <math>f(x)</math>. В свою очередь, многочлен <math>\frac{f(x)}{d(x)} </math> не имеет кратных неприводимых сомножителей. Если <math>d(x)</math> содержит кратные сомножители, то к нему также применяется описанная процедура. Зная эти разложения, легко получить разложение <math>f(x)</math>.

Таким образом, задача разложения произвольного унитарного многочлена над конечным полем <math> \Bbb{F}_q[x]</math> сводится к разложению на множители конечного числа многочленов, которые не имеют кратных неприводимых сомножителей, то есть к основному случаю.

Обоснование

Пусть:

<math>f(x) = f_1(x)^{e_1} \cdots f_k(x)^{e_k}</math>, где <math>\quad e_i = 1, \quad i=\overline{1,k}</math>.

Согласно китайской теореме об остатках существует единственный многочлен для любого набора <math>(c_1,\;...,\;c_k)</math> элементов поля <math>\mathbb{F}_q</math>:

<math>h(x)\in \mathbb{F}_q[x],</math>

такой что:

<math>h(x) \equiv c_i \pmod{f_i(x)}, \; i=\overline{1,\;k}, \quad \deg{h(x)} < \deg{f(x)}</math>.

Многочлен <math>h(x)</math> удовлетворяет условию:

<math>{h(x)} \equiv c_i \equiv c_i^q \equiv h(x)^q \pmod{f_i(x)}, \quad i=\overline{1,\;k}</math>,

и поэтому:

<math>h(x)^q \equiv h(x) \pmod{f(x)}, \quad \deg{h(x)} < deg{f(x)}</math>.

Из условия:

<math> h(x)^q - h(x) = \prod_{c \in \mathbb{F}_q} (h(x) - c) \equiv 0 \pmod{f(x)}</math>,

и из взаимной простоты сомножителей в правой части следует, что каждый неприводимый делитель многочлена <math>f(x)</math> делит один, и только один из многочленов <math>h(x)-c</math>. Таким образом, доказана справедливость и единственность разложения:

<math>f(x) = \prod_{c \in \mathbb{F}_q } \gcd(f(x),h(x)-c).</math>

Для нахождения многочлена:

<math>h(x) = a_0 + a_1x^1 + \dots + a_{n-1}x^{n-1} \in \mathbb{F}_q</math>

рассмотрим сравнение:

<math>h(x)^q \equiv h(x) \pmod{f(x)}</math>,

которое равносильно условию:

<math>\sum_{i=0}^{n-1}a_ix^{iq}\equiv\sum_{i=0}^{n-1}a_ix^i\pmod{f(x)}</math>.

По определению матрицы <math>B</math> получим:

<math>\sum_{i=0}^{n-1}a_i\sum_{j=0}^{n-1}b_{ij}x^j=\sum_{i=0}^{n-1}a_ix^i</math>,

поэтому:

<math>\sum_{i=0}^{n-1}a_i b_{ij}=a_j, \quad j=\overline{0,\;n-1}</math>.

Полученная система уравнений определяет коэффициенты <math>f</math>-разлагающих многочленов и может быть записана в виде:

<math>\quad(a_0,\;a_1,... ,a_{n-1})B=(a_0,\;a_1,\;... ,a_{n-1})</math>

или:

<math>\quad(a_0,\;a_1,... ,a_{n-1})(B-E_n)=\bold0</math>.

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

Сложность алгоритма составляет <math>O(n^3 + qkn)</math> математических операций. Алгоритм будет эффективен только для небольших полей. Это связанно с необходимостью перебора всех <math>c \in \Bbb{F}_q</math>.

Усовершенствования

• В случае простого поля, если значение <math>p</math> велико, то перебор значений <math>c \in {\Bbb{Z} / p \Bbb{Z}}</math> займёт много времени. Однако, возможно определить множество <math>M</math>, состоящее из <math>c</math>, для которых <math>\gcd(f(x),h(x)-c)</math> нетривиален. Для этого необходимо найти корни результанта <math>R(c)</math>, которые и будут составлять множество <math>M</math>.
• Ещё один метод разложения унитарного многочлена <math>f (x) \in GF(q) [x]</math>, не имеющего кратных неприводимых множителей, основан на приведении некоторой эффективно вычислимой с помощью алгоритма Берлекэмпа матрицы A к диагональному виду. Однако сам процесс диагонализации довольно сложен.
• В работе Калтофена и Лобо была предложена вероятностная версия алгоритма Берлекэмпа, позволяющая разложить на множители многочлен <math>f(x) \in GF(q) [x]</math> степени <math>n</math> за <math>O((n \log n+ \log q) \cdot n (\log n) \log (\log n))</math> арифметических операций. Алгоритм Калтофена — Лобо был реализован на компьютере, и оказался эффективным для многочленов высокой степени, например, для многочленов степени 10001 над полем <math>\Bbb{Z}/127\Bbb{Z}</math> он работает около 102,5 часов на компьютере Sun-4.

Применение

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

Реализации в системах компьютерной алгебры

В системе компьютерной алгебры PARI/GP алгоритм Берлекэмпа может быть использован посредством команды factormod.

Литература

• Berlekamp, Elwyn R. (1967). «Factoring Polynomials Over Finite Fields». Bell System Technical Journal 46: 1853–1859. [www.alcatel-lucent.com/bstj/vol46-1967/articles/bstj46-8-1853.pdf BSTJ] Later republished in: Berlekamp Elwyn R. Algebraic Coding Theory. — McGraw Hill, 1968. — ISBN 0-89412-063-8.
• Василенко О. Н. [window.edu.ru/resource/845/23845/files/book.pdf Теоретико-числовые алгоритмы в криптографии]. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.

• Лидл Р., Нидеррайтер Г. [eknigi.org/estestvennye_nauki/123549-konechnye-polya.html Конечные поля] = Finite Fields / Под ред. В. И. Нечаева. — 1-е изд. — М.: Мир, 1988. — Т. 1. — 430 с. — ISBN 5-03-000065-8.
• Ван дер Варден Б.Л. [mburyakov.ru/phtf/lib/Varden.pdf Алгебра]. — M.: Наука, 1976. — 646 с.

Отрывок, характеризующий Алгоритм Берлекэмпа

– Что за манера! Уж сидели, сидели! – сказала графиня, проводя гостей.


Когда Наташа вышла из гостиной и побежала, она добежала только до цветочной. В этой комнате она остановилась, прислушиваясь к говору в гостиной и ожидая выхода Бориса. Она уже начинала приходить в нетерпение и, топнув ножкой, сбиралась было заплакать оттого, что он не сейчас шел, когда заслышались не тихие, не быстрые, приличные шаги молодого человека.
Наташа быстро бросилась между кадок цветов и спряталась.
Борис остановился посереди комнаты, оглянулся, смахнул рукой соринки с рукава мундира и подошел к зеркалу, рассматривая свое красивое лицо. Наташа, притихнув, выглядывала из своей засады, ожидая, что он будет делать. Он постоял несколько времени перед зеркалом, улыбнулся и пошел к выходной двери. Наташа хотела его окликнуть, но потом раздумала. «Пускай ищет», сказала она себе. Только что Борис вышел, как из другой двери вышла раскрасневшаяся Соня, сквозь слезы что то злобно шепчущая. Наташа удержалась от своего первого движения выбежать к ней и осталась в своей засаде, как под шапкой невидимкой, высматривая, что делалось на свете. Она испытывала особое новое наслаждение. Соня шептала что то и оглядывалась на дверь гостиной. Из двери вышел Николай.
– Соня! Что с тобой? Можно ли это? – сказал Николай, подбегая к ней.
– Ничего, ничего, оставьте меня! – Соня зарыдала.
– Нет, я знаю что.
– Ну знаете, и прекрасно, и подите к ней.
– Соооня! Одно слово! Можно ли так мучить меня и себя из за фантазии? – говорил Николай, взяв ее за руку.
Соня не вырывала у него руки и перестала плакать.
Наташа, не шевелясь и не дыша, блестящими главами смотрела из своей засады. «Что теперь будет»? думала она.
– Соня! Мне весь мир не нужен! Ты одна для меня всё, – говорил Николай. – Я докажу тебе.
– Я не люблю, когда ты так говоришь.
– Ну не буду, ну прости, Соня! – Он притянул ее к себе и поцеловал.
«Ах, как хорошо!» подумала Наташа, и когда Соня с Николаем вышли из комнаты, она пошла за ними и вызвала к себе Бориса.
– Борис, подите сюда, – сказала она с значительным и хитрым видом. – Мне нужно сказать вам одну вещь. Сюда, сюда, – сказала она и привела его в цветочную на то место между кадок, где она была спрятана. Борис, улыбаясь, шел за нею.
– Какая же это одна вещь ? – спросил он.
Она смутилась, оглянулась вокруг себя и, увидев брошенную на кадке свою куклу, взяла ее в руки.
– Поцелуйте куклу, – сказала она.
Борис внимательным, ласковым взглядом смотрел в ее оживленное лицо и ничего не отвечал.
– Не хотите? Ну, так подите сюда, – сказала она и глубже ушла в цветы и бросила куклу. – Ближе, ближе! – шептала она. Она поймала руками офицера за обшлага, и в покрасневшем лице ее видны были торжественность и страх.
– А меня хотите поцеловать? – прошептала она чуть слышно, исподлобья глядя на него, улыбаясь и чуть не плача от волненья.
Борис покраснел.
– Какая вы смешная! – проговорил он, нагибаясь к ней, еще более краснея, но ничего не предпринимая и выжидая.
Она вдруг вскочила на кадку, так что стала выше его, обняла его обеими руками, так что тонкие голые ручки согнулись выше его шеи и, откинув движением головы волосы назад, поцеловала его в самые губы.
Она проскользнула между горшками на другую сторону цветов и, опустив голову, остановилась.
– Наташа, – сказал он, – вы знаете, что я люблю вас, но…
– Вы влюблены в меня? – перебила его Наташа.
– Да, влюблен, но, пожалуйста, не будем делать того, что сейчас… Еще четыре года… Тогда я буду просить вашей руки.
Наташа подумала.
– Тринадцать, четырнадцать, пятнадцать, шестнадцать… – сказала она, считая по тоненьким пальчикам. – Хорошо! Так кончено?
И улыбка радости и успокоения осветила ее оживленное лицо.
– Кончено! – сказал Борис.
– Навсегда? – сказала девочка. – До самой смерти?
И, взяв его под руку, она с счастливым лицом тихо пошла с ним рядом в диванную.


Графиня так устала от визитов, что не велела принимать больше никого, и швейцару приказано было только звать непременно кушать всех, кто будет еще приезжать с поздравлениями. Графине хотелось с глазу на глаз поговорить с другом своего детства, княгиней Анной Михайловной, которую она не видала хорошенько с ее приезда из Петербурга. Анна Михайловна, с своим исплаканным и приятным лицом, подвинулась ближе к креслу графини.
– С тобой я буду совершенно откровенна, – сказала Анна Михайловна. – Уж мало нас осталось, старых друзей! От этого я так и дорожу твоею дружбой.
Анна Михайловна посмотрела на Веру и остановилась. Графиня пожала руку своему другу.
– Вера, – сказала графиня, обращаясь к старшей дочери, очевидно, нелюбимой. – Как у вас ни на что понятия нет? Разве ты не чувствуешь, что ты здесь лишняя? Поди к сестрам, или…
Красивая Вера презрительно улыбнулась, видимо не чувствуя ни малейшего оскорбления.
– Ежели бы вы мне сказали давно, маменька, я бы тотчас ушла, – сказала она, и пошла в свою комнату.
Но, проходя мимо диванной, она заметила, что в ней у двух окошек симметрично сидели две пары. Она остановилась и презрительно улыбнулась. Соня сидела близко подле Николая, который переписывал ей стихи, в первый раз сочиненные им. Борис с Наташей сидели у другого окна и замолчали, когда вошла Вера. Соня и Наташа с виноватыми и счастливыми лицами взглянули на Веру.
Весело и трогательно было смотреть на этих влюбленных девочек, но вид их, очевидно, не возбуждал в Вере приятного чувства.
– Сколько раз я вас просила, – сказала она, – не брать моих вещей, у вас есть своя комната.
Она взяла от Николая чернильницу.
– Сейчас, сейчас, – сказал он, мокая перо.
– Вы всё умеете делать не во время, – сказала Вера. – То прибежали в гостиную, так что всем совестно сделалось за вас.
Несмотря на то, или именно потому, что сказанное ею было совершенно справедливо, никто ей не отвечал, и все четверо только переглядывались между собой. Она медлила в комнате с чернильницей в руке.
– И какие могут быть в ваши года секреты между Наташей и Борисом и между вами, – всё одни глупости!
– Ну, что тебе за дело, Вера? – тихеньким голоском, заступнически проговорила Наташа.
Она, видимо, была ко всем еще более, чем всегда, в этот день добра и ласкова.
– Очень глупо, – сказала Вера, – мне совестно за вас. Что за секреты?…
– У каждого свои секреты. Мы тебя с Бергом не трогаем, – сказала Наташа разгорячаясь.
– Я думаю, не трогаете, – сказала Вера, – потому что в моих поступках никогда ничего не может быть дурного. А вот я маменьке скажу, как ты с Борисом обходишься.
– Наталья Ильинишна очень хорошо со мной обходится, – сказал Борис. – Я не могу жаловаться, – сказал он.
– Оставьте, Борис, вы такой дипломат (слово дипломат было в большом ходу у детей в том особом значении, какое они придавали этому слову); даже скучно, – сказала Наташа оскорбленным, дрожащим голосом. – За что она ко мне пристает? Ты этого никогда не поймешь, – сказала она, обращаясь к Вере, – потому что ты никогда никого не любила; у тебя сердца нет, ты только madame de Genlis [мадам Жанлис] (это прозвище, считавшееся очень обидным, было дано Вере Николаем), и твое первое удовольствие – делать неприятности другим. Ты кокетничай с Бергом, сколько хочешь, – проговорила она скоро.
– Да уж я верно не стану перед гостями бегать за молодым человеком…
– Ну, добилась своего, – вмешался Николай, – наговорила всем неприятностей, расстроила всех. Пойдемте в детскую.
Все четверо, как спугнутая стая птиц, поднялись и пошли из комнаты.
– Мне наговорили неприятностей, а я никому ничего, – сказала Вера.
– Madame de Genlis! Madame de Genlis! – проговорили смеющиеся голоса из за двери.
Красивая Вера, производившая на всех такое раздражающее, неприятное действие, улыбнулась и видимо не затронутая тем, что ей было сказано, подошла к зеркалу и оправила шарф и прическу. Глядя на свое красивое лицо, она стала, повидимому, еще холоднее и спокойнее.

В гостиной продолжался разговор.
– Ah! chere, – говорила графиня, – и в моей жизни tout n'est pas rose. Разве я не вижу, что du train, que nous allons, [не всё розы. – при нашем образе жизни,] нашего состояния нам не надолго! И всё это клуб, и его доброта. В деревне мы живем, разве мы отдыхаем? Театры, охоты и Бог знает что. Да что обо мне говорить! Ну, как же ты это всё устроила? Я часто на тебя удивляюсь, Annette, как это ты, в свои годы, скачешь в повозке одна, в Москву, в Петербург, ко всем министрам, ко всей знати, со всеми умеешь обойтись, удивляюсь! Ну, как же это устроилось? Вот я ничего этого не умею.
– Ах, душа моя! – отвечала княгиня Анна Михайловна. – Не дай Бог тебе узнать, как тяжело остаться вдовой без подпоры и с сыном, которого любишь до обожания. Всему научишься, – продолжала она с некоторою гордостью. – Процесс мой меня научил. Ежели мне нужно видеть кого нибудь из этих тузов, я пишу записку: «princesse une telle [княгиня такая то] желает видеть такого то» и еду сама на извозчике хоть два, хоть три раза, хоть четыре, до тех пор, пока не добьюсь того, что мне надо. Мне всё равно, что бы обо мне ни думали.
– Ну, как же, кого ты просила о Бореньке? – спросила графиня. – Ведь вот твой уже офицер гвардии, а Николушка идет юнкером. Некому похлопотать. Ты кого просила?
– Князя Василия. Он был очень мил. Сейчас на всё согласился, доложил государю, – говорила княгиня Анна Михайловна с восторгом, совершенно забыв всё унижение, через которое она прошла для достижения своей цели.
– Что он постарел, князь Василий? – спросила графиня. – Я его не видала с наших театров у Румянцевых. И думаю, забыл про меня. Il me faisait la cour, [Он за мной волочился,] – вспомнила графиня с улыбкой.
– Всё такой же, – отвечала Анна Михайловна, – любезен, рассыпается. Les grandeurs ne lui ont pas touriene la tete du tout. [Высокое положение не вскружило ему головы нисколько.] «Я жалею, что слишком мало могу вам сделать, милая княгиня, – он мне говорит, – приказывайте». Нет, он славный человек и родной прекрасный. Но ты знаешь, Nathalieie, мою любовь к сыну. Я не знаю, чего я не сделала бы для его счастья. А обстоятельства мои до того дурны, – продолжала Анна Михайловна с грустью и понижая голос, – до того дурны, что я теперь в самом ужасном положении. Мой несчастный процесс съедает всё, что я имею, и не подвигается. У меня нет, можешь себе представить, a la lettre [буквально] нет гривенника денег, и я не знаю, на что обмундировать Бориса. – Она вынула платок и заплакала. – Мне нужно пятьсот рублей, а у меня одна двадцатипятирублевая бумажка. Я в таком положении… Одна моя надежда теперь на графа Кирилла Владимировича Безухова. Ежели он не захочет поддержать своего крестника, – ведь он крестил Борю, – и назначить ему что нибудь на содержание, то все мои хлопоты пропадут: мне не на что будет обмундировать его.
Графиня прослезилась и молча соображала что то.
– Часто думаю, может, это и грех, – сказала княгиня, – а часто думаю: вот граф Кирилл Владимирович Безухой живет один… это огромное состояние… и для чего живет? Ему жизнь в тягость, а Боре только начинать жить.
– Он, верно, оставит что нибудь Борису, – сказала графиня.
– Бог знает, chere amie! [милый друг!] Эти богачи и вельможи такие эгоисты. Но я всё таки поеду сейчас к нему с Борисом и прямо скажу, в чем дело. Пускай обо мне думают, что хотят, мне, право, всё равно, когда судьба сына зависит от этого. – Княгиня поднялась. – Теперь два часа, а в четыре часа вы обедаете. Я успею съездить.
И с приемами петербургской деловой барыни, умеющей пользоваться временем, Анна Михайловна послала за сыном и вместе с ним вышла в переднюю.
– Прощай, душа моя, – сказала она графине, которая провожала ее до двери, – пожелай мне успеха, – прибавила она шопотом от сына.
– Вы к графу Кириллу Владимировичу, ma chere? – сказал граф из столовой, выходя тоже в переднюю. – Коли ему лучше, зовите Пьера ко мне обедать. Ведь он у меня бывал, с детьми танцовал. Зовите непременно, ma chere. Ну, посмотрим, как то отличится нынче Тарас. Говорит, что у графа Орлова такого обеда не бывало, какой у нас будет.


– Mon cher Boris, [Дорогой Борис,] – сказала княгиня Анна Михайловна сыну, когда карета графини Ростовой, в которой они сидели, проехала по устланной соломой улице и въехала на широкий двор графа Кирилла Владимировича Безухого. – Mon cher Boris, – сказала мать, выпрастывая руку из под старого салопа и робким и ласковым движением кладя ее на руку сына, – будь ласков, будь внимателен. Граф Кирилл Владимирович всё таки тебе крестный отец, и от него зависит твоя будущая судьба. Помни это, mon cher, будь мил, как ты умеешь быть…
– Ежели бы я знал, что из этого выйдет что нибудь, кроме унижения… – отвечал сын холодно. – Но я обещал вам и делаю это для вас.
Несмотря на то, что чья то карета стояла у подъезда, швейцар, оглядев мать с сыном (которые, не приказывая докладывать о себе, прямо вошли в стеклянные сени между двумя рядами статуй в нишах), значительно посмотрев на старенький салоп, спросил, кого им угодно, княжен или графа, и, узнав, что графа, сказал, что их сиятельству нынче хуже и их сиятельство никого не принимают.