Кіріспе
(Математикалық) көбейтіндіге жіктеу. Математикада, факторлау (немесе факторлау, ағылшын тіліндегі орфографиялық айырмашылықтарға назар аударыңыз) – сан немесе басқа математикалық объектіні бірнеше факторлардың көбейтіндісі түрінде жазу, әдетте, сол сияқты кіші немесе қарапайым объектілер. Мысалы, 3 × 5 – 15 бүтін санының факторлануы, ал (x – 2)(x + 2) – x² – 4 полиномының факторлануы. Факторлау, әдетте, нақты немесе кешен сандар сияқты бөлінуге ие сандар жүйелерінде мағыналы деп есептелмейді, себебі кез келген санды нөлден өзгеше кез келген санға көбейту арқылы жазуға болады. Дегенмен, рационал санның немесе рационал функцияның мағыналы факторлануын алу үшін оны ең төменгі түрде жазып, содан кейін оның алымын және бөлімін бөлек факторлау қажет. Факторлауды алғаш рет ежелгі грек математиктері бүтін сандар үшін қарастырған. Олар әрбір оң бүтін санды 1-ден үлкен бүтін сандардың көбейтіндісіне жіктеуге болады, яғни оны одан әрі бүтін сандарға жіктеу мүмкін емес, – деп тұжырымдайтын арифметиканың негізгі теоремасын дәлелдеді. Бұл факторлау факторлардың ретіне қарай бірегей болады. Бүтін сандарды факторлау көбейтуге кері операция болғанымен, алгоритмдік тұрғыдан әлдеқайда қиын, және бұл қасиет RSA криптожүйесінде ашық кілтті криптографияны жүзеге асыру үшін пайдаланылады. Полиномдарды факторлау ғасырлар бойы зерттелді. Элементар алгебрада, полиномды факторлау оның түбірлерін табу мәселесін факторлардың түбірлерін табуға дейін азайтады. Бүтін сандардағы немесе өрістегі коэффициенттері бар полиномдар бірегей факторлау қасиетіне ие, бұл арифметиканың негізгі теоремасының нұсқасы, онда жай сандар редукцияланбайтын полиномдармен алмастырылған. Атап айтқанда, кешен коэффициенттері бар бір айнымалы полином сызықты полиномдарға бірегей (реттелуіне қарай) жіктеледі: бұл алгебраның негізгі теоремасының нұсқасы. Мұндай жағдайда, жіктеуді түбір табу алгоритмдерімен жүзеге асыруға болады. Бүтін сандардың коэффициенттері бар полиномдар компьютерлік алгебра үшін маңызды болып табылады. Рационал сандардың коэффициенттері бар полиномдар сақинасында (толық) жіктеуді есептеу үшін тиімді компьютерлік алгоритмдер бар (полиномдарды факторлау қараңыз). Бірегей факторлау қасиетіне ие коммутативті сақина бірегей факторлау домені деп аталады. Алгебралық бүтін сандардың кейбір сақиналары сияқты, бірегей факторлау домені емес сандар жүйелері де бар. Дегенмен, алгебралық бүтін сандардың сақиналары Дедекинд домендерінің әлсіз қасиетін қанағаттандырады: идеалдар жай идеалдарға бірегей түрде жіктеледі. Факторлау математикалық объектіні кішірек немесе қарапайым объектілердің көбейтіндісіне жіктеудің жалпылама түріне де сілтеме жасай алады. Мысалы, кез келген функцияны сюръективті функциямен және инъективті функциямен құрастыру арқылы жіктеуге болады. Матрицалар матрицалық жіктеудің көптеген түрлеріне ие. Мысалы, әрбір матрицаның төменгі үшбұрышты матрица L (барлық диагональдық элементтері 1-ге тең), жоғарғы үшбұрышты матрица U және пермутациялық матрица P-нің көбейтіндісі түрінде бірегей LUP жіктеуі бар; бұл Гаусс жоюының матрицалық формасы.
In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x – 2)(x + 2) is a polynomial factorization of x^(2) – 4. Factorization is not usually considered meaningful within number systems possessing division, such as the real or complex numbers, since any can be trivially written as whenever is not zero. However, a meaningful factorization for a rational number or a rational function can be obtained by writing it in lowest terms and separately factoring its numerator and denominator. Factorization was first considered by ancient Greek mathematicians in the case of integers. They proved the fundamental theorem of arithmetic, which asserts that every positive integer may be factored into a product of prime numbers, which cannot be further factored into integers greater than 1. Moreover, this factorization is unique up to the order of the factors. Although integer factorization is a sort of inverse to multiplication, it is much more difficult algorithmically, a fact which is exploited in the RSA cryptosystem to implement public key cryptography. Polynomial factorization has also been studied for centuries. In elementary algebra, factoring a polynomial reduces the problem of finding its roots to finding the roots of the factors. Polynomials with coefficients in the integers or in a field possess the unique factorization property, a version of the fundamental theorem of arithmetic with prime numbers replaced by irreducible polynomials. In particular, a univariate polynomial with complex coefficients admits a unique (up to ordering) factorization into linear polynomials: this is a version of the fundamental theorem of algebra. In this case, the factorization can be done with root finding algorithms. The case of polynomials with integer coefficients is fundamental for computer algebra. There are efficient computer algorithms for computing (complete) factorizations within the ring of polynomials with rational number coefficients (see factorization of polynomials). A commutative ring possessing the unique factorization property is called a unique factorization domain. There are number systems, such as certain rings of algebraic integers, which are not unique factorization domains. However, rings of algebraic integers satisfy the weaker property of Dedekind domains: ideals factor uniquely into prime ideals. Factorization may also refer to more general decompositions of a mathematical object into the product of smaller or simpler objects. For example, every function may be factored into the composition of a surjective function with an injective function. Matrices possess many kinds of matrix factorizations. For example, every matrix has a unique LUP factorization as a product of a lower triangular matrix L with all diagonal entries equal to one, an upper triangular matrix U, and a permutation matrix P; this is a matrix formulation of Gaussian elimination.
Бүкіл сандар
Арифметиканың негізгі теоремасы бойынша, 1-ден үлкен кез келген бүтін санның (факторлардың ретіне қарай) бірегей алғашқы сандарға жіктелуі бар, яғни 1-ден үлкен бүтін сандардың көбейтіндісіне жіктеле алмайтын бүтін сандар. n бүтін санының жіктелуін есептеу үшін, n-нің q бөлгішін табу немесе n-нің жай сан екенін анықтау үшін алгоритм қажет. Мұндай бөлгіш табылып, осы алгоритм q және n/q факторларына қайталап қолданылса, n-нің толық жіктелуіне жетеді. n-нің q бөлгішін табу үшін, егер ол болса, 1 < q және q² ≤ n шартын қанағаттандыратын q-ның барлық мәндерін тексеру жеткілікті. Шындығында, егер r, r² > n шартын қанағаттандыратын n-нің бөлгіші болса, онда q = n/r = 1 – n-нің бөлгіші болады, және q² ≤ n теңсіздігі орындалады.
For finding a divisor q of n, if any, it suffices to test all values of q such that 1 < q and q^(2) ≤ n. In fact, if r is a divisor of n such that r^(2) > n, then 1=q = n / r is a divisor of n such that q^(2) ≤ n.
If one tests the values of q in increasing order, the first divisor that is found is necessarily a prime number, and the cofactor 1=r = n / q cannot have any divisor smaller than q. For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of r that is not smaller than q and not greater than
There is no need to test all values of q for applying the method. In principle, it suffices to test only prime divisors. This needs to have a table of prime numbers that may be generated for example with the sieve of Eratosthenes. As the method of factorization does essentially the same work as the sieve of Eratosthenes, it is generally more efficient to test for a divisor only those numbers for which it is not immediately clear whether they are prime or not. Typically, one may proceed by testing 2, 3, 5, and the numbers > 5, whose last digit is 1, 3, 7, 9 and the sum of digits is not a multiple of 3. This method works well for factoring small integers, but is inefficient for larger integers. For example, Pierre de Fermat was unable to discover that the 6th Fermat number
is not a prime number. In fact, applying the above method would require more than 10,000, for a number that has 10 decimal digits. There are more efficient factoring algorithms. However they remain relatively inefficient, as, with the present state of the art, one cannot factorize, even with the more powerful computers, a number of 500 decimal digits that is the product of two randomly chosen prime numbers. This ensures the security of the RSA cryptosystem, which is widely used for secure internet communication.
Егер q-ның мәндерін өсу ретімен тексерсек, табылган алғашқы бөлгіш міндетті түрде жай сан болады, ал кофактор r = n/q = 1, q-дан кіші бөлгішке ие болмайды. Сондықтан, толық жіктелуді алу үшін алгоритмді жалғастыру үшін r-дің q-дан кіші емес және одан үлкен емес бөлгішін іздеу жеткілікті. Әдісті қолдану үшін q-ның барлық мәндерін тексерудің қажеті жоқ. Принципте, тек жай бөлгіштерді тексеру жеткілікті. Бұл үшін, мысалы, Эратоспеннің решесі арқылы жасалатын жай сандардың кестесі қажет. Факторлау әдісі Эратоспеннің решесі сияқты жұмыс істейтіндіктен, әдетте, тек жай сандары белгісіз сандарды ғана бөлгіш ретінде тексеру тиімдірек. Көбінесе, 2, 3, 5 және соңғы цифры 1, 3, 7, 9-ға тең және цифрларының қосындысы 3-ке бөлінбейтін > 5 сандарын тексеруге болады. Бұл әдіс кішкентай бүтін сандарды жіктеу үшін жақсы жұмыс істейді, бірақ үлкен сандар үшін тиімсіз. Мысалы, Пьер де Ферма 6-шы Ферма санының жай сан емес екенін анықтай алмады. Шындығында, жоғарыдағы әдісті қолдану үшін 10 мыңнан астам тексерулер қажет болады, ал санда ондық разрядтардың саны 10-ға жетеді. Факторлаудың тиімді алгоритмдері бар. Дегенмен, олар салыстырмалы түрде тиімсіз болып қалады, себебі қазіргі технология деңгейінде, тіпті ең қуатты компьютерлердің өзі кездейсоқ таңдалған екі жай санның көбейтіндісінен тұратын 500 ондық разрядты санды жіктеуге шамасы жетпейді. Бұл RSA криптожүйесінің қауіпсіздігін қамтамасыз етеді, ол интернет арқылы қауіпсіз байланыс үшін кеңінен қолданылады.
For finding a divisor q of n, if any, it suffices to test all values of q such that 1 < q and q^(2) ≤ n. In fact, if r is a divisor of n such that r^(2) > n, then 1=q = n / r is a divisor of n such that q^(2) ≤ n.
If one tests the values of q in increasing order, the first divisor that is found is necessarily a prime number, and the cofactor 1=r = n / q cannot have any divisor smaller than q. For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of r that is not smaller than q and not greater than
There is no need to test all values of q for applying the method. In principle, it suffices to test only prime divisors. This needs to have a table of prime numbers that may be generated for example with the sieve of Eratosthenes. As the method of factorization does essentially the same work as the sieve of Eratosthenes, it is generally more efficient to test for a divisor only those numbers for which it is not immediately clear whether they are prime or not. Typically, one may proceed by testing 2, 3, 5, and the numbers > 5, whose last digit is 1, 3, 7, 9 and the sum of digits is not a multiple of 3. This method works well for factoring small integers, but is inefficient for larger integers. For example, Pierre de Fermat was unable to discover that the 6th Fermat number
is not a prime number. In fact, applying the above method would require more than 10,000, for a number that has 10 decimal digits. There are more efficient factoring algorithms. However they remain relatively inefficient, as, with the present state of the art, one cannot factorize, even with the more powerful computers, a number of 500 decimal digits that is the product of two randomly chosen prime numbers. This ensures the security of the RSA cryptosystem, which is widely used for secure internet communication.
Экспрессияларды факторлау тарихы
Алгебралық манипуляцияларды өрнектерді (әсіресе теңдеулерді) жеңілдету үшін жүйелі түрде қолдану 9 ғасырға дейін барып, әл-Хорезмидің "Толықтау және теңгермеу арқылы есептеу туралы қысқаша кітабымен" байланысты болуы мүмкін, кітаптың тақылабы осындай екі түрлі манипуляцияны көрсетеді. Дегенмен, тіпті квадраттық теңдеулерді шешу үшін де, Харриоттың 1631 жылы, оның өлімінен он жыл кейін жарияланған еңбегіне дейін көбейткіштерге жіктеу әдісі қолданылмаған. "Аналитикалық өнердің алгебралық теңдеулерді шешуге арналған тәжірибесі" атты кітабында Харриот мономиалдардың, биномиалдардың және триномиалдардың қосу, алу, көбейту және бөлу кестелерін жасады. Содан кейін екінші бөлімде ол 1=aa − ba + ca = + bc теңдеуін келтіріп, бұл оның бұрын ұсынған көбейту түріне сәйкес келетінін көрсетті, осылайша (a − b)(a + c) көбейткіштеріне жіктеуді алды.
Жалпы әдістер
Келесі әдістер сома түріндегі немесе сомаға келтірілетін кез келген өрнекке қолданылады. Сондықтан, олар ең көп полиномдарға қолданылады, бірақ соманың мүшелері мономиалдар болмаған жағдайда да қолданылуы мүмкін, яғни соманың мүшелері айнымалылар мен тұрақтылардың көбейтіндісінен тұрады.
Бастапқы бөлшектер мен мазмұн факторлары
Рационалды коэффициенттері бар кез келген полиномиалды, бірегей тәсілмен, рационалды сан мен бүтін сандық коэффициенттері бар полиномиалдың көбейтіндісі түрінде жіктеуге болады. Бұл полиномиал примитивті болады (яғни, коэффициенттерінің ең үлкен ортақ бөлгіші 1-ге тең) және оң жетекші коэффициентке (ең жоғары дәрежелі мүшенің коэффициенті) ие болады. Мысалы:
Бұл жіктеуде рационалды сан – мазмұн, ал примитивті полиномиал – примитивті бөлік деп аталады. Бұл жіктеуді есептеу келесідей жүргізіледі: ең бастысы, барлық коэффициенттерді ортақ белгіге келтіріп, бүтін коэффициенттері бар полиномиалды бүтін сан q арқылы бөлуге қол жеткізу. Содан кейін, осы полиномиалдың коэффициенттерінің ең үлкен ортақ бөлгіші p-ді бөліп алып, примитивті бөлікті аламыз, ал мазмұн – p болады. Соңында, қажет болған жағдайда, p-нің және примитивті бөліктің барлық коэффициенттерінің таңбаларын өзгертуге болады. Бұл жіктеу нәтижесі бастапқы полиномиалдан үлкен болуы мүмкін (әсіресе, көптеген өзара жай белгілер болған кезде), бірақ тіпті осылай болған жағдайда да, примитивті бөлікті одан әрі жіктеу үшін өңдеу әдетте оңайырақ болады.
Бірегей факторлау домендері
Бүкіл сандар мен өрістегі полиномиалдар бірегей факторлау қасиетін бөліседі, яғни кез келген нөлдік емес элементті кері элементтің (бүкіл сандар үшін бірлік, ±1) және ирредукциялық элементтердің (бүкіл сандар үшін жай сандар) көбейтіндісіне жіктеуге болады. Бұл жіктелу факторларды өзгертуге және факторлар арасындағы кері элементтерді ауыстыруға дейін бірегей болады. Осы қасиетке ие интегралды домендер бірегей факторлау домендері (UFD) деп аталады. UFD-де ең үлкен ортақ бөлгіштер болады, ал керісінше, ең үлкен ортақ бөлгіштерге ие кез келген интегралды домен UFD болып табылады. Кез келген негізгі идеалдық домен UFD болып табылады. Евклидтік домен – бүкіл сандарға ұқсас Евклидтік бөлініс анықталған интегралды домен. Кез келген Евклидтік домен – негізгі идеалдық домен, демек, ол UFD болып табылады. Евклидтік доменде Евклидтік бөлу ең үлкен ортақ бөлгіштерді есептеу үшін Евклидтік алгоритмді анықтауға мүмкіндік береді. Дегенмен, бұл факторлау алгоритмінің бар екенін білдірмейді. F өрісіндегі бір айнымалы полиномиалдардың Евклидтік домені F[x] үшін факторлау алгоритмінің болуы мүмкін емес, осыған байланысты нақты мысал бар.
Идеалдар
Алгебралық сандар теориясында Диофанти теңдеулерін зерттеу 19 ғасырда математиктерді бүтін сандардың обобщениелерін, яғни алгебралық бүтін сандарды енгізуге әкелді. Алгебралық бүтін сандардың алғаш зерттелген сақиналары Гаусс бүтін сандары және Эйзенштейн бүтін сандары болды, олар қалыпты бүтін сандар сияқты негізгі идеалдық домендер болып табылады және осылайша бірегей факторлау қасиетіне ие. Алайда, көп ұзамай алгебралық бүтін сандардың көпшілігі негізгі емес екені және бірегей факторлауға ие емес екені анықталды. Ең қарапайым мысал – мұнда
және осы факторлардың барлығы толымсыз. Бірегей факторлаудың болмауы Диофанти теңдеулерін шешуде маңызды қиындық тудырады. Мысалы, Ферманың соңғы теоремасының көптеген дұрыс емес дәлелдемелері (мүмкін, Ферманың "бұл шекке сыймайтын керемет дәлелі" де осылардың қатарында) бірегей факторлау туралы түсініксіз болжамдарға негізделген. Бұл қиындық Дедекиндпен шешілді, ол алгебралық бүтін сандардың сақиналары идеалдардың бірегей факторлауына ие екенін дәлелдеді: осы сақиналарда әрбір идеал жай идеалдардың көбейтіндісі болып табылады, және бұл факторлау факторлардың ретіне дейін бірегей. Осы бірегей факторлау қасиетіне ие интегралды домендер қазір Дедекинд домендері деп аталады. Олар алгебралық сандар теориясындағы негізгі құрауыштар болып табылатын көптеген қасиеттерге ие.
Матрицалар
Матрицалық сақиналар коммутативті емес және бірегей факторлануы жоқ: көбінесе, матрицаны матрицалардың көбейтіндісі түрінде жазудың көптеген тәсілдері болады. Сондықтан, факторлау мәселесі белгілі бір типтегі факторларды табудан тұрады. Мысалы, LU ыдырауы матрицаны төменгі үшбұрышты матрица мен жоғарғы үшбұрышты матрицаның көбейтіндісі ретінде көрсетеді. Бұл әрқашан мүмкін болмағандықтан, әдетте үшінші фактор ретінде пермутациялық матрицасы бар "LUP ыдырауы" қарастырылады. Матрицалық факторлаудың ең көп таралған түрлері туралы мәліметтерді Матрицалық бөлшектеу бөлімінен қараңыз. Логикалық матрица – екілік қатынасты көрсетеді, ал матрица көбейтуі – қатынастардың композициясына сәйкес келеді. Қатынастың сипатын, мысалы, дифункционалды қатынас сияқты анықтау үшін, оны факторлау арқылы бөлшектеуге болады.