Кіріспе
Есептеу әдісі
факторлау алгоритмдері
factorization algorithms
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems. The first polynomial factorization algorithm was published by Theodor von Schubert in 1793. Leopold Kronecker rediscovered Schubert's algorithm in 1882 and extended it to multivariate polynomials and coefficients in an algebraic extension. But most of the knowledge on this topic is not older than circa 1965 and the first computer algebra systems:
When the long known finite step algorithms were first put on computers, they turned out to be highly inefficient. The fact that almost any uni or multivariate polynomial of degree up to 100 and with coefficients of a moderate size (up to 100 bits) can be factored by modern algorithms in a few minutes of computer time indicates how successfully this problem has been attacked during the past fifteen years. (Erich Kaltofen, 1982)
Nowadays, modern algorithms and computers can quickly factor univariate polynomials of degree more than 1000 having coefficients with thousands of digits. For this purpose, even for factoring over the rational numbers and number fields, a fundamental step is a factorization of a polynomial over a finite field.
Математика мен компьютерлік алгебрада көптамаларды факторлау немесе көптамалық факторлау – берілген өрістегі немесе бүтін сандардағы коэффициенттері бар көптаманы сол өрістегі коэффициенттері бар азайтылмайтын факторлардың көбейтіндісі ретінде көрсету. Полиномиялық факторлау – компьютерлік алгебра жүйелерінің негізгі компоненттерінің бірі. Бірінші полиномиалды факторлау алгоритмін 1793 жылы Теодор фон Шуберт жариялады. Леопольд Кронекер 1882 жылы Шуберт алгоритмін қайта тауып, оны алгебралық кеңейтудегі көпөлшемді полиномиалдар мен коэффициенттерге дейін кеңейтті. Бірақ бұл тақырыптағы білімнің көпшілігі 1965 жылдан және алғашқы компьютерлік алгебра жүйелерінен бұрынғы емес:
Көптен бері белгілі шекті қадамдық алгоритмдер алғаш рет компьютерлерге енгізілгенде, олар өте тиімсіз болып шықты. 100-ге дейін дәрежесі бар және орташа мөлшердегі коэффициенттері бар (100 битке дейін) кез келген бір немесе көпөлшемді полиномиалды қазіргі заманғы алгоритмдермен бірнеше минуттың компьютер уақытында факторлауға болады, бұл соңғы он бес жыл ішінде осы мәселеге қаншалықты сәтті шабуыл жасалғанын көрсетеді (Эрих Кальтофен, 1982).
Қазіргі кезде қазіргі заманғы алгоритмдер мен компьютерлер мыңнан астам таңбалары бар 1000-нан жоғары дәрежедегі бірөлшемді көпмүшелерді жылдам факторлай алады. Осы мақсатта, тіпті рационалды сандар мен сандық өрістерді факторлау үшін, негізгі қадам – шекті өрісте көпмүшені факторлау болып табылады.
factorization algorithms
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems. The first polynomial factorization algorithm was published by Theodor von Schubert in 1793. Leopold Kronecker rediscovered Schubert's algorithm in 1882 and extended it to multivariate polynomials and coefficients in an algebraic extension. But most of the knowledge on this topic is not older than circa 1965 and the first computer algebra systems:
When the long known finite step algorithms were first put on computers, they turned out to be highly inefficient. The fact that almost any uni or multivariate polynomial of degree up to 100 and with coefficients of a moderate size (up to 100 bits) can be factored by modern algorithms in a few minutes of computer time indicates how successfully this problem has been attacked during the past fifteen years. (Erich Kaltofen, 1982)
Nowadays, modern algorithms and computers can quickly factor univariate polynomials of degree more than 1000 having coefficients with thousands of digits. For this purpose, even for factoring over the rational numbers and number fields, a fundamental step is a factorization of a polynomial over a finite field.
Квадратсыз факторлау
Егер полиномиалдың екі немесе одан көп көбейткіштері бірдей болса, онда полиномиал осы көбейткіштің квадратына еселенеді. Көптік фактор сонымен қатар полиномиалдың туындысының да көбейткіші болып табылады (егер бірнеше айнымалы болса, кез келген айнымалыға қатысты). Бірөлшемді полиномиалдар үшін, көптік факторлар тиісті кеңейту өрісінде көптік түбірлерге тең. Рационал сандардағы (немесе жалпы алғанда, нөлдік сипаттамасы бар өрістегі) бірөлшемді полиномиалдар үшін Юн алгоритмі осыны пайдаланып, полиномиалды шаршысыз факторларға, яғни квадраттың көбейткіші емес факторларға тиімді түрде жіктейді, gcd(f(x), f'(x)) есептеулерінің тізбесінен бастайды. Бастапқы полиномиалды жіктеу үшін әрбір шаршысыз факторды жіктеу жеткілікті. Сондықтан шаршысыз жіктеу көптеген полиномиалдық жіктеу алгоритмдерінің бірінші қадамы болып табылады. Юн алгоритмі көпөлшемді жағдайға полиномиалдық сақинадағы бірөлшемді полиномиал ретінде көпөлшемді полиномиалды қарастыру арқылы кеңейтеді. Шекті өрістегі полиномиал үшін Юн алгоритмі тек дәрежесі сипаттамадан кіші болған жағдайда ғана қолданылады, өйтпесе нөлдік емес полиномиалдың туындысы нөлге тең болуы мүмкін (p элементі бар өрісте, x^p полиномиалының туындысы әрқашан нөл болады). Дегенмен, полиномиалдан және оның туындысынан басталатын gcd есептеулерінің тізбесі шаршысыз жіктеуді есептеуге мүмкіндік береді; қараңыз: Шекті өрістердегі полиномиалдық жіктеу#Шаршысыз жіктеу.
Классикалық әдістер
Бұл бөлім қолмен есептеу кезінде пайдалы болатын оқулықтағы әдістерді сипаттайды. Бұл әдістер компьютерлік есептеулерде қолданылмайды, себебі олар бүтін сандық факторлауды пайдаланады, ал қазіргі таңда полиномиалдық факторлау одан жылдам. Төмендегі екі әдіс бүтін сандық коэффициенттері бар біртұра полиномнан басталады, мақсаты – бүтін сандық коэффициенттері бар полиномдар түріндегі факторларды табу.
Сызықтық коэффициенттерді табу
Рационалды коэффициенттері бар барлық сызықтық факторларды рационалды түбір сынағы арқылы табуға болады. Егер факторланбас керек көпмүше болса, онда барлық мүмкін сызықтық факторлар түрінде болады, мұнда - тұрақты санның көбейткіші, ал - тұрақты санның көбейткіші. Тұрақты санның барлық мүмкін комбинацияларын жарамдылығына тексеруге болады, және әр жарамды комбинацияны көпмүше бөлу арқылы шығаруға болады. Егер бастапқы көпмүше кемінде екеуі 2-дәрежелі немесе одан жоғары дәрежелі факторлардың көбейтіндісі болса, бұл әдіс тек толық емес факторлауды қамтамасыз етеді; әйтпесе факторлау толық болады. Атап айтқанда, егер дәл бір сызықтық емес фактор болса, ол барлық сызықтық факторлар шығарылғаннан кейін қалған көпмүше болады. Кубтық көпмүше жағдайында, егер кубтық көпмүше факторланатын болса, рационалды түбір сынағы толық факторлауды береді, яғни сызықтық факторға және бөлгісіз квадраттық факторға, немесе үш сызықтық факторға.
Біркелті көптік сандарды бүтін сандарға бөлу
If - бұл бүтін сандар бойынша бірөлшекті көптік, мазмұны бос және квадраттары жоқ деп есептеледі, онда кез келген фактордың абсолюттік мәні коэффициенттерімен шектелетін шекті есептеуден басталады. Осылайша, егер - бұл , және modulo - белгілі болса, онда оның суреті mod-тен қалпына келтірілуі мүмкін. Зассенхаус алгоритмі келесідей жүргізіледі. Біріншіден, -тің суреті квадратсыз болып қалатын және дәрежесі -мен бірдей болатын жай санды таңдаңыз. Бұл бүтін сандық көптіктерді шығарады, олардың көбейтіндісі сәйкес келеді. Модуль бойынша, көптік факторларға ие (бірліктерге дейін): Бұл факторлардың барлық ішкі жиынтықтарының көбейтінділері модуль бойынша -тің "нағыз" факторларына сәйкес келуі міндетті емес, бірақ біз оларды бөлу арқылы тексеруге болады. Осылайша, барлық иррационалды нағыз факторларды ең көп жағдайды тексеру арқылы табуға болады, оларды толықтыруды өткізіп тастау арқылы жағдайларға дейін азайтуға болады. Егер азайтылатын болса, онда жағдайлардың саны бұрыннан табылған нағыз факторға кіретін жағдайларды алып тастау арқылы одан әрі азайтылады. Зассенхаус алгоритмі әр жағдайды (әр ішкі жиынтықты) жылдам өңдейді, алайда, ең нашар жағдайда ол жағдайлардың экспоненциалдық санын қарастырады. Рационалды көптіктерді факторлау үшін бірінші полиномиалдық уақыт алгоритмін Ленстра, Ленстра және Ловас тапты, және ол Ленстра–Ленстра–Ловас торлық негізді азайту (LLL) алгоритмінің қолданылуы болып табылады. LLL факторлау алгоритмінің оңайлатылған нұсқасы мынадай: полиномиалдың α күрделі (немесе p-адық) түбірін жоғары дәлдікпен есептеңіз, содан кейін 1, α, α², α³ арасындағы жуық сызықтық қатынасты табу үшін Ленстра–Ленстра–Ловас торлық негізді азайту алгоритмін қолданыңыз, бүтін сандық коэффициенттерімен, бұл нақты сызықтық қатынас болуы мүмкін және көптік факторы. Біреу осы әдістің коэффициентін немесе азайтылмауын қамтамасыз ететін дәлдік шегін анықтай алады. Бұл әдіс полиномиалдық уақытта аяқтаса да, ол практикада қолданылмайды, өйткені тордың өлшемдері жоғары және кірістері үлкен, бұл есептеуді баяулатады. Зассенхаус алгоритміндегі экспоненциалдық күрделілік комбинаторлық проблемадан туындайды: дұрыс ішкі жиынтықтарды қалай таңдау керек. Қазіргі заманғы факторлау жүзеге асырулары Зассенхаусқа ұқсас жұмыс істейді, бірақ комбинаторлық проблема LLL арқылы шешілетін торлық проблемаға ауыстырылады. Бұл тәсілде LLL факторлардың коэффициенттерін есептеу үшін емес, керісінше {0,1} кірістері бар векторларды есептеу үшін қолданылады, олар иррационалды нағыз факторларға сәйкес келетін ішкі жиынтықтарды кодтайды.
The Zassenhaus algorithm proceeds as follows. First, choose a prime number such that the image of remains square free, and of the same degree as Then factor This produces integer polynomials whose product matches Next, apply Hensel lifting; this updates the in such a way that their product matches , where is large enough that exceeds : thus each corresponds to a well defined integer polynomial. Modulo , the polynomial has factors (up to units): the products of all subsets of These factors modulo need not correspond to "true" factors of in , but we can easily test them by division in This way, all irreducible true factors can be found by checking at most cases, reduced to cases by skipping complements. If is reducible, the number of cases is reduced further by removing those that appear in an already found true factor. The Zassenhaus algorithm processes each case (each subset) quickly, however, in the worst case, it considers an exponential number of cases. The first polynomial time algorithm for factoring rational polynomials was discovered by Lenstra, Lenstra and Lovász and is an application of the Lenstra–Lenstra–Lovász lattice basis reduction (LLL) algorithm A simplified version of the LLL factorization algorithm is as follows: calculate a complex (or p adic) root α of the polynomial to high precision, then use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm to find an approximate linear relation between 1, α, α2, α3, . with integer coefficients, which might be an exact linear relation and a polynomial factor of One can determine a bound for the precision that guarantees that this method produces either a factor, or an irreducibility proof. Although this method finishes in polynomial time, it is not used in practice because the lattice has high dimension and huge entries, which makes the computation slow. The exponential complexity in the Zassenhaus algorithm comes from a combinatorial problem: how to select the right subsets of State of the art factoring implementations work in a manner similar to Zassenhaus, except that the combinatorial problem is translated to a lattice problem that is then solved by LLL. In this approach, LLL is not used to compute coefficients of factors, but rather to compute vectors with entries in {0,1} that encode the subsets of corresponding to the irreducible true factors.