Факторизация целых чисел

Поделись знанием:
(перенаправлено с «Разложение на множители»)
Перейти к: навигация, поиск

Факториза́цией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики.

В отличие от задачи распознавания простоты числа, факторизация предположительно является вычислительно сложной задачей. В настоящее время неизвестно, существует ли эффективный не квантовый алгоритм факторизации целых чисел. Однако доказательства того, что не существует решения этой задачи за полиномиальное время, также нет.

Предположение о том, что для больших чисел задача факторизации является вычислительно сложной, лежит в основе широко используемых алгоритмов (например, RSA). Множество областей математики и информатики находят применение в решении этой задачи. Среди них: эллиптические кривые, алгебраическая теория чисел и квантовые вычисления.





История

Задача поиска эффективных способов разложения целых чисел на множители интересовала математиков с давних времен, особенно специалистов в области теории чисел. Существуют предположения о том, что Ферма был одним из первых, кто предложил метод разложения, заключающийся в том, чтобы представить число в виде разности квадратов <math>n = x^2 - y^2</math>, а затем, вычисляя <math>\gcd(n, x-y)</math>, попытаться найти нетривиальный делитель <math>n</math>. Данный способ позволяет находить два мало отличающихся по величине делителя числа быстрее, чем простой перебор делителей[1].

Далее Лежандром было обнаружено, что при таком подходе достаточно получить сравнение <math>x^2 \equiv y^2 \mod n</math> и использовал для этого цепные дроби. Также Эйлером и Гауссом были предложены некоторые способы нахождения чисел, связанных этим сравнением[1].

Одним из ключевых моментов в развитии факторизации целых чисел было создание алгоритма RSA, что возобновило интерес ученых в данном направлении, так как имело практическое применение в области шифрования. Этот алгоритм был предложен в 1977 году тремя учеными Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом из Массачусетского Технологического Института и назван по первым буквам фамилий авторов методом RSA. Он основан на идее криптографии с открытым ключом и для взлома системы необходимо выполнить разложение числа на простые сомножители. На момент публикации алгоритма RSA были известны методы, которые позволяли факторизовать числа, состоящие не более чем из 25—30 цифр, а наиболее известным и применяемым все ещё оставался метод Ферма. Метод RSA позволяет факторизовывать числа из 100 и более десятичных знаков. Создатели, в свою очередь, пообещали за факторизацию числа из 129 десятичных знаков символические сто долларов США[2].

На популярность задачи факторизации также повлияла публикация в 1977 году в журнале Scientific American Мартина Гарднер «Новый алгоритм шифрования, для взлома которого потребуется миллионы лет».Ошибка Lua : attempt to index local 'entity' (a nil value). Столь громкое название было воспринято в качестве вызова всему математическому сообществу. В результате этой гонки было предложено несколько новых и нестандартных идей факторизации[2].

Эпопея с разложением 129-значного числа завершилась в 1994 году, когда коллектив под руководством А. Ленстры, используя 1600 компьютеров, подготовил за 220 дней систему линейных уравнений, содержавшую более полумиллиона неизвестных. Решение этой системы суперкомпьютером заняло два дня. Несмотря на то, что в то время уже были известны методы решета числового поля, данный результат был получен с помощью алгоритма квадратичного решета[2].

Алгоритмы факторизации

Как правило, на вход таких алгоритмов подается число <math>n \in \N</math>, которое необходимо факторизовать, состоящее из <math>N = [\log_2 n] + 1</math> символов (если <math>n</math> представлено в двоичном виде)[3]. При этом алгоритм ищет первый простой делитель, после чего, при необходимости, можно запустить алгоритм заново для дальнейшей факторизации. Также, прежде чем начинать факторизацию большого числа, следует убедиться в том, что оно не простое. Для этого достаточно пройти тест числа на простоту. Эта задача детерминированно разрешима за полиномиальное время[4].

В зависимости от сложности алгоритмы факторизации можно разбить на две группы. Первая группа — экспоненциальные алгоритмы, сложность которых экспоненциально зависит от длины входящих параметров (то есть от длины <math>N</math> самого числа в бинарном представлении). Вторая группа — субэкспоненциальные алгоритмы.

Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время факторизация с полиномиальной сложностью возможна на квантовом компьютере с помощью алгоритма Шора (класс BQP)[5].

Экспоненциальные алгоритмы

Перебор возможных делителей

Сложность <math> O(\sqrt{n}\log^2 n) </math> или <math> O(\sqrt{n}\log n) </math>.

Один из самых простых и очевидных алгоритмов факторизации, заключающийся в том, чтобы последовательно делить факторизуемое число <math>n</math> на натуральные числа от <math>1</math> до <math>\lceil \sqrt{n} \rceil</math>. Формально достаточно делить только на простые числа в этом интервале, однако, для этого необходимо знать их множество. На практике составляется таблица простых чисел и производится проверка небольших чисел (например, до <math>2^{16}</math>). Для очень больших чисел алгоритм не используется в силу низкой скорости работы[6].


Метод факторизации Ферма

Сложность <math> O(n)</math> или <math>O(exp(N))</math>.

Идея алгоритма заключается в поиске таких чисел <math>A</math> и <math>B</math>, что факторизуемое число n представимо в виде: <math>n = A^2 - B^2 = (A-B)(A+B)</math>. Как и метод пробного деления, обычно не применяется на практике для факторизации больших чисел, так как имеет экспоненциальную сложность. Метод примечателен тем, что реализуем без операции деления, а только лишь с операциями сложения и вычитания[8]. Следует так же отметить, что если <math>n = pq</math>, при условии того, что <math>p</math> и <math>q</math> — простые числа не сильно отличающиеся по величине, то метод Ферма факторизует n достаточно быстро[9].


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

Сложность <math>O(n^{1/4})</math>.

Алгоритм Полларда является вероятностным алгоритмом, позволяющим находить делитель составного числа <math>n</math>, работающим со сложностью, зависящей лишь от величины делителя, но не величины факторизуемого числа <math>n</math>. Это обуславливает удобство применимости данного алгоритма в тех случаях, когда другие алгоритмы, сложность которых зависит от <math>n</math>, становятся неэффективны[11]. Примечателен так же тем, что существует вариант реализации такого алгоритма, при котором достаточно в памяти хранить всего 3 целых числа[12].


Алгоритм Ленстры

Сложность <math>O(n^{1/3}\log^2n)</math>.

Следует отметить, что несмотря на относительно неплохую эффективность среди экспоненциальных алгоритмов, в алгоритме Ленстры есть необходимость неоднократно вычислять квадратный корень в одном из шагов алгоритма, что, безусловно, является более трудоемким, чем сложение или вычитание[14].


Алгоритм Полларда — Штрассена

Сложность <math>O(n^{1/4}\log^4n)</math>.

Данный алгоритм имеет наилучшую оценку сложности среди детерминированных алгоритмов факторизации. Он может использоваться непосредственно для факторизации не очень больших целых чисел, а также в качестве вспомогательного алгоритма в субэкспоненциальном методе Диксона[16].


Метод квадратичных форм Шенкса

Гарантированная сложность <math>O(n^{1/4+\varepsilon})</math> и при верности гипотезы Римана <math>O(n^{1/5+\varepsilon})</math>.

В отличии от алгоритма Полларда - Штрассена не требует выделения больших объёмов памяти, к тому же имеет достаточно простые расчётные формулыК:Википедия:Статьи без источников (тип: не указан)[источник не указан 2714 дней].

P-1 алгоритм Полларда

Сложность <math>O(n^{1/2}\log^cn)</math>[17].

Несмотря на экспоненциальную оценку сложности, алгоритм во всех случаях быстро находит небольшие простые делители <math>n</math>, потому что они являются степенно-гладкими для небольшой границы гладкости <math>B</math>. В практических задачах данный алгоритм обычно используется до применения субэкспоненциальных алгоритмов факторизации, чтобы отделить небольшие простые делители числа <math>n</math>[17].


Метод Лемана

Сложность <math>O(n^{1/3})</math>.

В настоящее время алгоритм представляет скорее исторический, чем практический интерес, так как этот алгоритм был первым детерминированным алгоритмом со сложностью выполнения быстрее, чем <math>O(\sqrt{n})</math>.


Субэкспоненциальные алгоритмы

Для обозначения сложности принята L-нотация[3]:

<math>L_{n}(\alpha,\;c):=O(\exp((c+o(1))(\log n)^{\alpha}(\log\log n)^{1-\alpha})),</math>

где <math>n</math> — число подлежащее факторизации, <math>0<\alpha<1</math> и <math>c</math> — некоторые константы.

Алгоритм Диксона

Сложность <math>L_n(1/2,\;2\sqrt{2})</math>.


Факторизация методом непрерывных дробей

Сложность <math>L_n(1/2,\;\sqrt{2})</math>[23].

Метод квадратичного решета

Сложность <math>L_n(1/2,\;1)</math>[23].

Данный метод с использованием нескольких многочленов эффективен и достаточно легко реализуем на компьютере. Есть основания полагать, что он является наилучшим из известных алгоритмов факторизации для <math>n < 10^{110}</math> (не считая метод факторизации с помощью эллиптических кривых, который в некоторых случаях может работать быстрее. Стоит так же заметить, что для чисел <math>n > 10^{110}</math> алгоритмы решета числового поля сработают быстрее, чем метод квадратичного решета[24].

Факторизация Ленстры с помощью эллиптических кривых

Сложность <math>L_p(1/2,\;\sqrt{2})</math>, где <math>p</math> — наименьшее простое, которое делит <math>n</math>[25].

Параметры <math>a, x, y</math> выбираются случайно. Значения <math>w,v</math> следует выбирать эмпирически, рассмотрев некоторую серию возрастающих значений[25]. На практике при заданных <math>n, v, w</math> алгоритм заключается в том, чтобы выполнить алгоритм с одной кривой. Это повторяется до тех пор, пока <math>n</math> не разложится на множители или пока время, отведенное для алгоритма, не закончится.

Существуют модификации алгоритма, позволяющие работать с несколькими кривыми одновременно[25].


Отрывок, характеризующий Факторизация целых чисел

«И можно ли говорить и думать о таких пустяках?» думает Пьер.
– Да, из Ольмюца, – отвечает он со вздохом.
От ужина Пьер повел свою даму за другими в гостиную. Гости стали разъезжаться и некоторые уезжали, не простившись с Элен. Как будто не желая отрывать ее от ее серьезного занятия, некоторые подходили на минуту и скорее отходили, запрещая ей провожать себя. Дипломат грустно молчал, выходя из гостиной. Ему представлялась вся тщета его дипломатической карьеры в сравнении с счастьем Пьера. Старый генерал сердито проворчал на свою жену, когда она спросила его о состоянии его ноги. «Эка, старая дура, – подумал он. – Вот Елена Васильевна так та и в 50 лет красавица будет».
– Кажется, что я могу вас поздравить, – прошептала Анна Павловна княгине и крепко поцеловала ее. – Ежели бы не мигрень, я бы осталась.
Княгиня ничего не отвечала; ее мучила зависть к счастью своей дочери.
Пьер во время проводов гостей долго оставался один с Элен в маленькой гостиной, где они сели. Он часто и прежде, в последние полтора месяца, оставался один с Элен, но никогда не говорил ей о любви. Теперь он чувствовал, что это было необходимо, но он никак не мог решиться на этот последний шаг. Ему было стыдно; ему казалось, что тут, подле Элен, он занимает чье то чужое место. Не для тебя это счастье, – говорил ему какой то внутренний голос. – Это счастье для тех, у кого нет того, что есть у тебя. Но надо было сказать что нибудь, и он заговорил. Он спросил у нее, довольна ли она нынешним вечером? Она, как и всегда, с простотой своей отвечала, что нынешние именины были для нее одними из самых приятных.
Кое кто из ближайших родных еще оставались. Они сидели в большой гостиной. Князь Василий ленивыми шагами подошел к Пьеру. Пьер встал и сказал, что уже поздно. Князь Василий строго вопросительно посмотрел на него, как будто то, что он сказал, было так странно, что нельзя было и расслышать. Но вслед за тем выражение строгости изменилось, и князь Василий дернул Пьера вниз за руку, посадил его и ласково улыбнулся.
– Ну, что, Леля? – обратился он тотчас же к дочери с тем небрежным тоном привычной нежности, который усвоивается родителями, с детства ласкающими своих детей, но который князем Василием был только угадан посредством подражания другим родителям.
И он опять обратился к Пьеру.
– Сергей Кузьмич, со всех сторон , – проговорил он, расстегивая верхнюю пуговицу жилета.
Пьер улыбнулся, но по его улыбке видно было, что он понимал, что не анекдот Сергея Кузьмича интересовал в это время князя Василия; и князь Василий понял, что Пьер понимал это. Князь Василий вдруг пробурлил что то и вышел. Пьеру показалось, что даже князь Василий был смущен. Вид смущенья этого старого светского человека тронул Пьера; он оглянулся на Элен – и она, казалось, была смущена и взглядом говорила: «что ж, вы сами виноваты».
«Надо неизбежно перешагнуть, но не могу, я не могу», думал Пьер, и заговорил опять о постороннем, о Сергее Кузьмиче, спрашивая, в чем состоял этот анекдот, так как он его не расслышал. Элен с улыбкой отвечала, что она тоже не знает.
Когда князь Василий вошел в гостиную, княгиня тихо говорила с пожилой дамой о Пьере.
– Конечно, c'est un parti tres brillant, mais le bonheur, ma chere… – Les Marieiages se font dans les cieux, [Конечно, это очень блестящая партия, но счастье, моя милая… – Браки совершаются на небесах,] – отвечала пожилая дама.
Князь Василий, как бы не слушая дам, прошел в дальний угол и сел на диван. Он закрыл глаза и как будто дремал. Голова его было упала, и он очнулся.
– Aline, – сказал он жене, – allez voir ce qu'ils font. [Алина, посмотри, что они делают.]
Княгиня подошла к двери, прошлась мимо нее с значительным, равнодушным видом и заглянула в гостиную. Пьер и Элен так же сидели и разговаривали.
– Всё то же, – отвечала она мужу.
Князь Василий нахмурился, сморщил рот на сторону, щеки его запрыгали с свойственным ему неприятным, грубым выражением; он, встряхнувшись, встал, закинул назад голову и решительными шагами, мимо дам, прошел в маленькую гостиную. Он скорыми шагами, радостно подошел к Пьеру. Лицо князя было так необыкновенно торжественно, что Пьер испуганно встал, увидав его.
– Слава Богу! – сказал он. – Жена мне всё сказала! – Он обнял одной рукой Пьера, другой – дочь. – Друг мой Леля! Я очень, очень рад. – Голос его задрожал. – Я любил твоего отца… и она будет тебе хорошая жена… Бог да благословит вас!…
Он обнял дочь, потом опять Пьера и поцеловал его дурно пахучим ртом. Слезы, действительно, омочили его щеки.
– Княгиня, иди же сюда, – прокричал он.
Княгиня вышла и заплакала тоже. Пожилая дама тоже утиралась платком. Пьера целовали, и он несколько раз целовал руку прекрасной Элен. Через несколько времени их опять оставили одних.
«Всё это так должно было быть и не могло быть иначе, – думал Пьер, – поэтому нечего спрашивать, хорошо ли это или дурно? Хорошо, потому что определенно, и нет прежнего мучительного сомнения». Пьер молча держал руку своей невесты и смотрел на ее поднимающуюся и опускающуюся прекрасную грудь.
– Элен! – сказал он вслух и остановился.
«Что то такое особенное говорят в этих случаях», думал он, но никак не мог вспомнить, что такое именно говорят в этих случаях. Он взглянул в ее лицо. Она придвинулась к нему ближе. Лицо ее зарумянилось.
– Ах, снимите эти… как эти… – она указывала на очки.
Пьер снял очки, и глаза его сверх той общей странности глаз людей, снявших очки, глаза его смотрели испуганно вопросительно. Он хотел нагнуться над ее рукой и поцеловать ее; но она быстрым и грубым движеньем головы пeрехватила его губы и свела их с своими. Лицо ее поразило Пьера своим изменившимся, неприятно растерянным выражением.
«Теперь уж поздно, всё кончено; да и я люблю ее», подумал Пьер.
– Je vous aime! [Я вас люблю!] – сказал он, вспомнив то, что нужно было говорить в этих случаях; но слова эти прозвучали так бедно, что ему стало стыдно за себя.
Через полтора месяца он был обвенчан и поселился, как говорили, счастливым обладателем красавицы жены и миллионов, в большом петербургском заново отделанном доме графов Безухих.


Старый князь Николай Андреич Болконский в декабре 1805 года получил письмо от князя Василия, извещавшего его о своем приезде вместе с сыном. («Я еду на ревизию, и, разумеется, мне 100 верст не крюк, чтобы посетить вас, многоуважаемый благодетель, – писал он, – и Анатоль мой провожает меня и едет в армию; и я надеюсь, что вы позволите ему лично выразить вам то глубокое уважение, которое он, подражая отцу, питает к вам».)
– Вот Мари и вывозить не нужно: женихи сами к нам едут, – неосторожно сказала маленькая княгиня, услыхав про это.
Князь Николай Андреич поморщился и ничего не сказал.
Через две недели после получения письма, вечером, приехали вперед люди князя Василья, а на другой день приехал и он сам с сыном.
Старик Болконский всегда был невысокого мнения о характере князя Василья, и тем более в последнее время, когда князь Василий в новые царствования при Павле и Александре далеко пошел в чинах и почестях. Теперь же, по намекам письма и маленькой княгини, он понял, в чем дело, и невысокое мнение о князе Василье перешло в душе князя Николая Андреича в чувство недоброжелательного презрения. Он постоянно фыркал, говоря про него. В тот день, как приехать князю Василью, князь Николай Андреич был особенно недоволен и не в духе. Оттого ли он был не в духе, что приезжал князь Василий, или оттого он был особенно недоволен приездом князя Василья, что был не в духе; но он был не в духе, и Тихон еще утром отсоветывал архитектору входить с докладом к князю.
– Слышите, как ходит, – сказал Тихон, обращая внимание архитектора на звуки шагов князя. – На всю пятку ступает – уж мы знаем…
Однако, как обыкновенно, в 9 м часу князь вышел гулять в своей бархатной шубке с собольим воротником и такой же шапке. Накануне выпал снег. Дорожка, по которой хаживал князь Николай Андреич к оранжерее, была расчищена, следы метлы виднелись на разметанном снегу, и лопата была воткнута в рыхлую насыпь снега, шедшую с обеих сторон дорожки. Князь прошел по оранжереям, по дворне и постройкам, нахмуренный и молчаливый.
– А проехать в санях можно? – спросил он провожавшего его до дома почтенного, похожего лицом и манерами на хозяина, управляющего.
– Глубок снег, ваше сиятельство. Я уже по прешпекту разметать велел.
Князь наклонил голову и подошел к крыльцу. «Слава тебе, Господи, – подумал управляющий, – пронеслась туча!»
– Проехать трудно было, ваше сиятельство, – прибавил управляющий. – Как слышно было, ваше сиятельство, что министр пожалует к вашему сиятельству?
Князь повернулся к управляющему и нахмуренными глазами уставился на него.
– Что? Министр? Какой министр? Кто велел? – заговорил он своим пронзительным, жестким голосом. – Для княжны, моей дочери, не расчистили, а для министра! У меня нет министров!
– Ваше сиятельство, я полагал…
– Ты полагал! – закричал князь, всё поспешнее и несвязнее выговаривая слова. – Ты полагал… Разбойники! прохвосты! Я тебя научу полагать, – и, подняв палку, он замахнулся ею на Алпатыча и ударил бы, ежели бы управляющий невольно не отклонился от удара. – Полагал! Прохвосты! – торопливо кричал он. Но, несмотря на то, что Алпатыч, сам испугавшийся своей дерзости – отклониться от удара, приблизился к князю, опустив перед ним покорно свою плешивую голову, или, может быть, именно от этого князь, продолжая кричать: «прохвосты! закидать дорогу!» не поднял другой раз палки и вбежал в комнаты.
Перед обедом княжна и m lle Bourienne, знавшие, что князь не в духе, стояли, ожидая его: m lle Bourienne с сияющим лицом, которое говорило: «Я ничего не знаю, я такая же, как и всегда», и княжна Марья – бледная, испуганная, с опущенными глазами. Тяжелее всего для княжны Марьи было то, что она знала, что в этих случаях надо поступать, как m lle Bourime, но не могла этого сделать. Ей казалось: «сделаю я так, как будто не замечаю, он подумает, что у меня нет к нему сочувствия; сделаю я так, что я сама скучна и не в духе, он скажет (как это и бывало), что я нос повесила», и т. п.
Князь взглянул на испуганное лицо дочери и фыркнул.
– Др… или дура!… – проговорил он.
«И той нет! уж и ей насплетничали», подумал он про маленькую княгиню, которой не было в столовой.
– А княгиня где? – спросил он. – Прячется?…
– Она не совсем здорова, – весело улыбаясь, сказала m llе Bourienne, – она не выйдет. Это так понятно в ее положении.
– Гм! гм! кх! кх! – проговорил князь и сел за стол.
Тарелка ему показалась не чиста; он указал на пятно и бросил ее. Тихон подхватил ее и передал буфетчику. Маленькая княгиня не была нездорова; но она до такой степени непреодолимо боялась князя, что, услыхав о том, как он не в духе, она решилась не выходить.
– Я боюсь за ребенка, – говорила она m lle Bourienne, – Бог знает, что может сделаться от испуга.
Вообще маленькая княгиня жила в Лысых Горах постоянно под чувством страха и антипатии к старому князю, которой она не сознавала, потому что страх так преобладал, что она не могла чувствовать ее. Со стороны князя была тоже антипатия, но она заглушалась презрением. Княгиня, обжившись в Лысых Горах, особенно полюбила m lle Bourienne, проводила с нею дни, просила ее ночевать с собой и с нею часто говорила о свекоре и судила его.
– Il nous arrive du monde, mon prince, [К нам едут гости, князь.] – сказала m lle Bourienne, своими розовенькими руками развертывая белую салфетку. – Son excellence le рrince Kouraguine avec son fils, a ce que j'ai entendu dire? [Его сиятельство князь Курагин с сыном, сколько я слышала?] – вопросительно сказала она.
– Гм… эта excellence мальчишка… я его определил в коллегию, – оскорбленно сказал князь. – А сын зачем, не могу понять. Княгиня Лизавета Карловна и княжна Марья, может, знают; я не знаю, к чему он везет этого сына сюда. Мне не нужно. – И он посмотрел на покрасневшую дочь.
– Нездорова, что ли? От страха министра, как нынче этот болван Алпатыч сказал.
– Нет, mon pere. [батюшка.]
Как ни неудачно попала m lle Bourienne на предмет разговора, она не остановилась и болтала об оранжереях, о красоте нового распустившегося цветка, и князь после супа смягчился.
После обеда он прошел к невестке. Маленькая княгиня сидела за маленьким столиком и болтала с Машей, горничной. Она побледнела, увидав свекора.
Маленькая княгиня очень переменилась. Она скорее была дурна, нежели хороша, теперь. Щеки опустились, губа поднялась кверху, глаза были обтянуты книзу.
– Да, тяжесть какая то, – отвечала она на вопрос князя, что она чувствует.
– Не нужно ли чего?
– Нет, merci, mon pere. [благодарю, батюшка.]
– Ну, хорошо, хорошо.
Он вышел и дошел до официантской. Алпатыч, нагнув голову, стоял в официантской.
– Закидана дорога?
– Закидана, ваше сиятельство; простите, ради Бога, по одной глупости.
Князь перебил его и засмеялся своим неестественным смехом.
– Ну, хорошо, хорошо.
Он протянул руку, которую поцеловал Алпатыч, и прошел в кабинет.
Вечером приехал князь Василий. Его встретили на прешпекте (так назывался проспект) кучера и официанты, с криком провезли его возки и сани к флигелю по нарочно засыпанной снегом дороге.
Князю Василью и Анатолю были отведены отдельные комнаты.
Анатоль сидел, сняв камзол и подпершись руками в бока, перед столом, на угол которого он, улыбаясь, пристально и рассеянно устремил свои прекрасные большие глаза. На всю жизнь свою он смотрел как на непрерывное увеселение, которое кто то такой почему то обязался устроить для него. Так же и теперь он смотрел на свою поездку к злому старику и к богатой уродливой наследнице. Всё это могло выйти, по его предположению, очень хорошо и забавно. А отчего же не жениться, коли она очень богата? Это никогда не мешает, думал Анатоль.
Он выбрился, надушился с тщательностью и щегольством, сделавшимися его привычкою, и с прирожденным ему добродушно победительным выражением, высоко неся красивую голову, вошел в комнату к отцу. Около князя Василья хлопотали его два камердинера, одевая его; он сам оживленно оглядывался вокруг себя и весело кивнул входившему сыну, как будто он говорил: «Так, таким мне тебя и надо!»
– Нет, без шуток, батюшка, она очень уродлива? А? – спросил он, как бы продолжая разговор, не раз веденный во время путешествия.
– Полно. Глупости! Главное дело – старайся быть почтителен и благоразумен с старым князем.
– Ежели он будет браниться, я уйду, – сказал Анатоль. – Я этих стариков терпеть не могу. А?
– Помни, что для тебя от этого зависит всё.
В это время в девичьей не только был известен приезд министра с сыном, но внешний вид их обоих был уже подробно описан. Княжна Марья сидела одна в своей комнате и тщетно пыталась преодолеть свое внутреннее волнение.
«Зачем они писали, зачем Лиза говорила мне про это? Ведь этого не может быть! – говорила она себе, взглядывая в зеркало. – Как я выйду в гостиную? Ежели бы он даже мне понравился, я бы не могла быть теперь с ним сама собою». Одна мысль о взгляде ее отца приводила ее в ужас.
Маленькая княгиня и m lle Bourienne получили уже все нужные сведения от горничной Маши о том, какой румяный, чернобровый красавец был министерский сын, и о том, как папенька их насилу ноги проволок на лестницу, а он, как орел, шагая по три ступеньки, пробежал зa ним. Получив эти сведения, маленькая княгиня с m lle Bourienne,еще из коридора слышные своими оживленно переговаривавшими голосами, вошли в комнату княжны.
– Ils sont arrives, Marieie, [Они приехали, Мари,] вы знаете? – сказала маленькая княгиня, переваливаясь своим животом и тяжело опускаясь на кресло.
Она уже не была в той блузе, в которой сидела поутру, а на ней было одно из лучших ее платьев; голова ее была тщательно убрана, и на лице ее было оживление, не скрывавшее, однако, опустившихся и помертвевших очертаний лица. В том наряде, в котором она бывала обыкновенно в обществах в Петербурге, еще заметнее было, как много она подурнела. На m lle Bourienne тоже появилось уже незаметно какое то усовершенствование наряда, которое придавало ее хорошенькому, свеженькому лицу еще более привлекательности.
– Eh bien, et vous restez comme vous etes, chere princesse? – заговорила она. – On va venir annoncer, que ces messieurs sont au salon; il faudra descendre, et vous ne faites pas un petit brin de toilette! [Ну, а вы остаетесь, в чем были, княжна? Сейчас придут сказать, что они вышли. Надо будет итти вниз, а вы хоть бы чуть чуть принарядились!]
Маленькая княгиня поднялась с кресла, позвонила горничную и поспешно и весело принялась придумывать наряд для княжны Марьи и приводить его в исполнение. Княжна Марья чувствовала себя оскорбленной в чувстве собственного достоинства тем, что приезд обещанного ей жениха волновал ее, и еще более она была оскорблена тем, что обе ее подруги и не предполагали, чтобы это могло быть иначе. Сказать им, как ей совестно было за себя и за них, это значило выдать свое волнение; кроме того отказаться от наряжения, которое предлагали ей, повело бы к продолжительным шуткам и настаиваниям. Она вспыхнула, прекрасные глаза ее потухли, лицо ее покрылось пятнами и с тем некрасивым выражением жертвы, чаще всего останавливающемся на ее лице, она отдалась во власть m lle Bourienne и Лизы. Обе женщины заботились совершенно искренно о том, чтобы сделать ее красивой. Она была так дурна, что ни одной из них не могла притти мысль о соперничестве с нею; поэтому они совершенно искренно, с тем наивным и твердым убеждением женщин, что наряд может сделать лицо красивым, принялись за ее одеванье.
– Нет, право, ma bonne amie, [мой добрый друг,] это платье нехорошо, – говорила Лиза, издалека боком взглядывая на княжну. – Вели подать, у тебя там есть масака. Право! Что ж, ведь это, может быть, судьба жизни решается. А это слишком светло, нехорошо, нет, нехорошо!
Нехорошо было не платье, но лицо и вся фигура княжны, но этого не чувствовали m lle Bourienne и маленькая княгиня; им все казалось, что ежели приложить голубую ленту к волосам, зачесанным кверху, и спустить голубой шарф с коричневого платья и т. п., то всё будет хорошо. Они забывали, что испуганное лицо и фигуру нельзя было изменить, и потому, как они ни видоизменяли раму и украшение этого лица, само лицо оставалось жалко и некрасиво. После двух или трех перемен, которым покорно подчинялась княжна Марья, в ту минуту, как она была зачесана кверху (прическа, совершенно изменявшая и портившая ее лицо), в голубом шарфе и масака нарядном платье, маленькая княгиня раза два обошла кругом нее, маленькой ручкой оправила тут складку платья, там подернула шарф и посмотрела, склонив голову, то с той, то с другой стороны.
– Нет, это нельзя, – сказала она решительно, всплеснув руками. – Non, Marie, decidement ca ne vous va pas. Je vous aime mieux dans votre petite robe grise de tous les jours. Non, de grace, faites cela pour moi. [Нет, Мари, решительно это не идет к вам. Я вас лучше люблю в вашем сереньком ежедневном платьице: пожалуйста, сделайте это для меня.] Катя, – сказала она горничной, – принеси княжне серенькое платье, и посмотрите, m lle Bourienne, как я это устрою, – сказала она с улыбкой предвкушения артистической радости.
Но когда Катя принесла требуемое платье, княжна Марья неподвижно всё сидела перед зеркалом, глядя на свое лицо, и в зеркале увидала, что в глазах ее стоят слезы, и что рот ее дрожит, приготовляясь к рыданиям.
– Voyons, chere princesse, – сказала m lle Bourienne, – encore un petit effort. [Ну, княжна, еще маленькое усилие.]
Маленькая княгиня, взяв платье из рук горничной, подходила к княжне Марье.
– Нет, теперь мы это сделаем просто, мило, – говорила она.
Голоса ее, m lle Bourienne и Кати, которая о чем то засмеялась, сливались в веселое лепетанье, похожее на пение птиц.
– Non, laissez moi, [Нет, оставьте меня,] – сказала княжна.
И голос ее звучал такой серьезностью и страданием, что лепетанье птиц тотчас же замолкло. Они посмотрели на большие, прекрасные глаза, полные слез и мысли, ясно и умоляюще смотревшие на них, и поняли, что настаивать бесполезно и даже жестоко.
– Au moins changez de coiffure, – сказала маленькая княгиня. – Je vous disais, – с упреком сказала она, обращаясь к m lle Bourienne, – Marieie a une de ces figures, auxquelles ce genre de coiffure ne va pas du tout. Mais du tout, du tout. Changez de grace. [По крайней мере, перемените прическу. У Мари одно из тех лиц, которым этот род прически совсем нейдет. Перемените, пожалуйста.]
– Laissez moi, laissez moi, tout ca m'est parfaitement egal, [Оставьте меня, мне всё равно,] – отвечал голос, едва удерживающий слезы.
M lle Bourienne и маленькая княгиня должны были признаться самим себе, что княжна. Марья в этом виде была очень дурна, хуже, чем всегда; но было уже поздно. Она смотрела на них с тем выражением, которое они знали, выражением мысли и грусти. Выражение это не внушало им страха к княжне Марье. (Этого чувства она никому не внушала.) Но они знали, что когда на ее лице появлялось это выражение, она была молчалива и непоколебима в своих решениях.
– Vous changerez, n'est ce pas? [Вы перемените, не правда ли?] – сказала Лиза, и когда княжна Марья ничего не ответила, Лиза вышла из комнаты.
Княжна Марья осталась одна. Она не исполнила желания Лизы и не только не переменила прически, но и не взглянула на себя в зеркало. Она, бессильно опустив глаза и руки, молча сидела и думала. Ей представлялся муж, мужчина, сильное, преобладающее и непонятно привлекательное существо, переносящее ее вдруг в свой, совершенно другой, счастливый мир. Ребенок свой, такой, какого она видела вчера у дочери кормилицы, – представлялся ей у своей собственной груди. Муж стоит и нежно смотрит на нее и ребенка. «Но нет, это невозможно: я слишком дурна», думала она.