Факторизация

Поделись знанием:
Перейти к: навигация, поиск

В математике факториза́ция или фа́кторинг — это декомпозиция объекта (например, числа, полинома или матрицы) в произведение других объектов или факторов, которые, будучи перемноженными, дают исходный объект. Например, число 15 факторизуется на простые числа 3 и 5, а полином x2 − 4 факторизуется на (x − 2)(x + 2). В результате факторизации во всех случаях получается произведение более простых объектов, чем исходный.

Целью факторизации является приведение объекта к «основным строительным блокам», например, число к простым числам, многочлен — к неприводимым многочленам. Факторизация целых чисел обеспечивается основной теоремой арифметики, а многочленов — основной теоремой алгебры.

Противоположностью факторизации полиномов является их расширение, перемножение полиномиальных факторов для получения «расширенного» многочлена, записанного в виде суммы слагаемых.

Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро.(пример: прибегая к полному перебору всех допустимых вариантов решения задачи, в том числе с помощью распределённых компьютерных вычислений) Её сложность лежит в основе некоторых алгоритмов безопасности с открытым ключом шифрования, таких как RSA.

Матрица может также быть факторизована на произведение матриц специального вида для приложений, в которых эта форма удобна. Одним из основных примеров этого является использование ортогональных, унитарных и треугольных матриц. Существуют различные способы факторизации: QR-разложение, LQ, QL, RQ, RZ.

Ещё одним примером является факторизация функций в виде композиции других функций, имеющих определённые свойства. Например, каждая функция может рассматриваться как композиция сюръективной функции с инъективной. Этот подход является обобщением понятия факторизации систем.





Целые числа

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

Многочлены

См. также

Напишите отзыв о статье "Факторизация"

Ссылки

  • Л. Инфельд, Т. Е. Хал [ega-math.narod.ru/Nquant/Infeld.htm Метод факторизации]
  • [factors.evalwave.com/ One hundred million numbers factored on html pages.]
  • [library.thinkquest.org/20991/alg/factoring.html?tqskip1=1 A page about factorization, Algebra, Factoring]
  • [wims.unice.fr/wims/wims.cgi?module=tool/algebra/factor.en WIMS Factoris] is an online factorization tool.
  • [primenumb.ru/описание-бд/ Списки простых и факторизованных составных чисел]

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

Тон ее уже был ворчливый, губка поднялась, придавая лицу не радостное, а зверское, беличье выраженье. Она замолчала, как будто находя неприличным говорить при Пьере про свою беременность, тогда как в этом и состояла сущность дела.
– Всё таки я не понял, de quoi vous avez peur, [Чего ты боишься,] – медлительно проговорил князь Андрей, не спуская глаз с жены.
Княгиня покраснела и отчаянно взмахнула руками.
– Non, Andre, je dis que vous avez tellement, tellement change… [Нет, Андрей, я говорю: ты так, так переменился…]
– Твой доктор велит тебе раньше ложиться, – сказал князь Андрей. – Ты бы шла спать.
Княгиня ничего не сказала, и вдруг короткая с усиками губка задрожала; князь Андрей, встав и пожав плечами, прошел по комнате.
Пьер удивленно и наивно смотрел через очки то на него, то на княгиню и зашевелился, как будто он тоже хотел встать, но опять раздумывал.
– Что мне за дело, что тут мсье Пьер, – вдруг сказала маленькая княгиня, и хорошенькое лицо ее вдруг распустилось в слезливую гримасу. – Я тебе давно хотела сказать, Andre: за что ты ко мне так переменился? Что я тебе сделала? Ты едешь в армию, ты меня не жалеешь. За что?
– Lise! – только сказал князь Андрей; но в этом слове были и просьба, и угроза, и, главное, уверение в том, что она сама раскается в своих словах; но она торопливо продолжала:
– Ты обращаешься со мной, как с больною или с ребенком. Я всё вижу. Разве ты такой был полгода назад?
– Lise, я прошу вас перестать, – сказал князь Андрей еще выразительнее.
Пьер, всё более и более приходивший в волнение во время этого разговора, встал и подошел к княгине. Он, казалось, не мог переносить вида слез и сам готов был заплакать.
– Успокойтесь, княгиня. Вам это так кажется, потому что я вас уверяю, я сам испытал… отчего… потому что… Нет, извините, чужой тут лишний… Нет, успокойтесь… Прощайте…
Князь Андрей остановил его за руку.
– Нет, постой, Пьер. Княгиня так добра, что не захочет лишить меня удовольствия провести с тобою вечер.
– Нет, он только о себе думает, – проговорила княгиня, не удерживая сердитых слез.
– Lise, – сказал сухо князь Андрей, поднимая тон на ту степень, которая показывает, что терпение истощено.
Вдруг сердитое беличье выражение красивого личика княгини заменилось привлекательным и возбуждающим сострадание выражением страха; она исподлобья взглянула своими прекрасными глазками на мужа, и на лице ее показалось то робкое и признающееся выражение, какое бывает у собаки, быстро, но слабо помахивающей опущенным хвостом.
– Mon Dieu, mon Dieu! [Боже мой, Боже мой!] – проговорила княгиня и, подобрав одною рукой складку платья, подошла к мужу и поцеловала его в лоб.
– Bonsoir, Lise, [Доброй ночи, Лиза,] – сказал князь Андрей, вставая и учтиво, как у посторонней, целуя руку.


Друзья молчали. Ни тот, ни другой не начинал говорить. Пьер поглядывал на князя Андрея, князь Андрей потирал себе лоб своею маленькою рукой.
– Пойдем ужинать, – сказал он со вздохом, вставая и направляясь к двери.
Они вошли в изящно, заново, богато отделанную столовую. Всё, от салфеток до серебра, фаянса и хрусталя, носило на себе тот особенный отпечаток новизны, который бывает в хозяйстве молодых супругов. В середине ужина князь Андрей облокотился и, как человек, давно имеющий что нибудь на сердце и вдруг решающийся высказаться, с выражением нервного раздражения, в каком Пьер никогда еще не видал своего приятеля, начал говорить: