Факторизация: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
← Содержимое страницы заменено на «Категория:Арифметика Категория:Алгебра» Метки: замена ручная отмена отменено через визуальный редактор |
Oleg4280 (обсуждение | вклад) м откат правок 93.125.104.182 (обс.) к версии La loi et la justice Метки: откат ссылка на неоднозначность |
||
Строка 1:
{{о|математической концепции||Фактор}}
В [[Математика|математике]] '''факториза́ция''' — это [[Декомпозиция|декомпозиция]] объекта (например, [[Число|числа]], [[полином]]а или [[Матрица (математика)|матрицы]]) в [[Умножение|произведение]] других объектов, или '''факторов''', которые, будучи [[Умножение|перемноженными]], дают исходный объект. Например, число 15 факторизуется на [[простые числа]] 3 и 5, а полином ''x''<sup>2</sup> − 4 факторизуется на (''x'' − 2)(''x'' + 2). В результате факторизации во всех случаях получается произведение более простых объектов, чем исходный.
Целью факторизации является приведение объекта к «основным строительным блокам», например, число к простым числам, многочлен — к [[Неприводимый многочлен|неприводимым многочленам]]. Факторизация целых чисел обеспечивается [[Основная теорема арифметики|основной теоремой арифметики]], а многочленов — [[Основная теорема алгебры|основной теоремой алгебры]].
Противоположностью факторизации полиномов является их [[Расширенный полином|расширение]], перемножение полиномиальных факторов для получения «расширенного» многочлена, записанного в виде суммы слагаемых.
[[Факторизация целых чисел]] для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов шифрования с [[Криптосистема с открытым ключом|открытым ключом]], таких как [[RSA]].
[[Матрица (математика)|Матрица]] может также быть факторизована на произведение матриц специального вида для приложений, в которых эта форма удобна. Одним из основных примеров этого является использование [[Ортогональная матрица|ортогональных]], [[Унитарная матрица|унитарных]] и [[Треугольная матрица|треугольных]] матриц. Существуют различные способы факторизации: [[QR-разложение]], ''LQ'', ''QL'', ''RQ'', ''RZ''.
Ещё одним примером является факторизация [[Функция (математика)|функций]] в виде [[Композиция функций|композиции]] других функций, имеющих определённые свойства. Например, каждая функция может рассматриваться как композиция [[Сюръекция|сюръективной функции]] с [[Инъекция (математика)|инъективной]]. Этот подход является обобщением понятия факторизации систем.
Наконец, в [[Теория графов|теории графов]] [[факторизация графа]] определяется как разложение графа на непересекающиеся по рёбрам остовные подграфы (то есть подграфы, содержащие все вершины графа) специального вида<ref>{{книга |часть=Факторизация |заглавие=Математическая энциклопедия (в 5 томах) |место=М. |том=5 |год=1985 |издательство=[[Большая Российская энциклопедия (издательство)|Советская Энциклопедия]] |страницы=591}}</ref>.
== Целые числа ==
{{Main|Факторизация целых чисел}}
По [[Основная теорема арифметики|основной теореме арифметики]] каждое натуральное [[число]] имеет единственное разложение на простые множители. Существует множество [[алгоритм]]ов факторизации целого, с помощью которых можно факторизовать любое натуральное число до состава его простых множителей с помощью [[Рекуррентная формула|рекуррентных формул]]. Однако, для очень больших чисел эффективный алгоритм пока неизвестен.
== Гауссовы числа ==
{{Main|Факторизация гауссовых чисел}}
[[Кольцо (алгебра)|Кольцо]] [[Гауссовы целые числа|гауссовых чисел]] [[Факториальное кольцо|факториально]], то есть разложение на простые множители однозначно с точностью до их порядка и ассоциированности (умножения на [[Обратимый элемент|делители единицы]]).
== Многочлены ==
{{main|Факторизация многочленов}}
== См. также ==
* [[Отношение эквивалентности|Факторизация отображений]]
* [[Разложение матрицы]]
* [[Факториальное кольцо]]
* [[Wolfram Alpha]]
== Примечания ==
{{примечания}}
== Ссылки ==
* Л. Инфельд, Т. Е. Хал [http://ega-math.narod.ru/Nquant/Infeld.htm Метод факторизации]
* [https://web.archive.org/web/20110118232722/http://factors.evalwave.com/ One hundred million numbers factored on html pages.]
* [https://web.archive.org/web/20110606004149/http://library.thinkquest.org/20991/alg/factoring.html?tqskip1=1 A page about factorization, Algebra, Factoring]
* [http://wims.unice.fr/wims/wims.cgi?module=tool/algebra/factor.en WIMS Factoris] is an online factorization tool.
* [https://web.archive.org/web/20150810185800/http://www.primenumb.ru/%D0%BE%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B5-%D0%B1%D0%B4/ Списки простых и факторизованных составных чисел]
[[Категория:Арифметика]]
[[Категория:Алгебра]]
|