bahupadatthile ettavum valia pothuvaayi vibhajichirikkunna ghadakam

beejaganithathil, rund bahupadangalude ettavum valia pothuvaaya bhajakam (palappozhum jii. sii. dii ennu churukkipparayunnu) saadhyamaaya ettavum uyarnna digriyulla oru bahupadamaanu, athu rund yadhaartha bahupadangaludeyum oru gadakamaanu. eee ashayam rund poornnasamkhyakalude ettavum valia pothuvaaya bhaajakathinu samaanamaan.
oru feeldile univariot polynomialukalude pradhana saahacharyathil, poornnasankhyayaaya jii. sii. dii. pole, deergha vibhajanam upayogichu euclidean algoritam vazhi polynomial jii. sii. dii kanakkakkaam. polynomial gcd oru invertible sthiraangam kondu gunikkunnathuvare maathrame nirvachikkappedunnulla.
poornnasankhyayaaya jii. sii. diyum polynomial jii. sii. diyum thammilulla saamyam euclidean algoritam, euclidean division ennivayil ninnu kanakkakkavunna ellah gunangalum ekathaanamaaya polynomialukalilekku vyaapippikkaan anuvadikkunnu. koodaathe, beejaganithatthinte vividha mekhalakalil athine oru adisthaana ashayamaakkunna prathyeka gunangalundu bahupadamaaya jii. sii. dii. kku. saadhaaranayaayi, rund bahupadangalude jii. sii. diyude verukal rund bahupadangalude pothuvaaya verukalaanu, ithu avaye kanakkukoottathe thanne verukalekkurichulla vivarangal nalkunnu. udaaharanathinu, oru polynomialinte onniladhikam verukal polynomialinteyum athinte derivativinteyum jii. sii. diyude verukalaanu, kooduthal jii. sii. dii kanakkukoottalukal polynomialinte square free factorisation kanakkukoottaan anuvadikkunnu, ithu polynomialukal nalkunnu, avayude verukal yadhaartha polynomialinte thannirikkunna gunithatthinte verukalaanu.
ettavum valia pothuvaaya vibhaajakathe nirvachikkukayum nilanilkkukayum cheyyaam, kooduthal pothuve, oru feeldilo poornnasamkhyakalude valayathilo ulla multiveriyettu polynomialukalkkum koodaathe oru advitheeya factorisation domainilum. gunakangalude valayathil oraalkk oru jii. sii. dii algoritam labhichaaludan avaa kanakkakkaan algorithangal undu. euclidean algorithathinte oru vakabhedathilekku prashnam kuraykkunnathinu veriyabilukalude annathekkurichulla aavarthanathiloode eee algorithangal munnott pookunnu. avaa computer beejaganithatthile oru adisthaana upakaranamaan, kaaranam computer beejaganita samvidaanangal bhinnasamkhyakal lalithamakkaan avaye chittayayi upayogikkunnu. neremarichu, computer beejaganita samvidaanangalude kaaryakshamathayude aavasyakatha niravettunnathinaanu bahupada jii. sii. diyude aadhunika sidhaantham vikasippicheduthath.
pothuvaaya nirvachanam.
oru avibhaajya domainil, saadhaaranayaayi oru feeld allengil poornnasamkhyakalilulla gunakangalulla bahupadangalaayirikkatte. 
oro pothuvaaya bhajakan vibhajikkukayum vibhajikkukayum cheiyunna oru bahupadamaanu ettavum valia pothuvaaya bhaajakavum. oro jody polynomialukalkkum (randum poojyamalla) oru advitheeya factorisation domaine aanenkil maathram oru jii. sii. dii undu.
oru feeld aanenkil poojyamallengil, oru polynomial randum vibhajikkukayaanenkil maathram, eee propertyulla polynomialil ettavum valia digri undengil, athu ettavum valia pothuvaaya bhajakamaanu. jii. sii. dii 0 aanenkil, chila rachayithakkal eee saahacharyathil ithu nirvachikkappettittille karuthunnu.
ettavum valia pothuvaaya vibhaajakavum saadhaaranayaayi soochippikkappedunnathu.
ettavum valia pothuvaaya vibhaajakan advitheeyamalla oru gcd aanenkil, polynomial mattoru gcd aanu, atharam oru vipareeta ghadakam undengil maathram 
oppam 
mattoru vidhathil paranjaal, oru invertible sthiraangam kondu gunikkunnathuvare jii. sii. dii savisheshamaan.
poornnasamkhyakalude kaaryatthil, eee anishchithathvam jii. sii. dii. aayi, positteev aaya advitheeyamaayathu thiranjedutthaanu pariharichathu (mattonn undu, athu athinte vipareethamaanu). eee kanvenshanil, rund poornnasamkhyakalude jii. sii. dii ettavum valuthaanu (saadhaarana kramatthinu) pothuvaaya vibhaajakavum. ennirunnaalum, oru integral domainil polynomialukalkku swaabhaavika motham kramam illaathathinaal, oraalkk ivide athe reethiyil munnott pookaan kazhiyilla. oru feeldile ekathaanamaaya bahupadangalkku, oraalkk jii. sii. dii monic aayirikkanamenn aavasyappedaam (athaayath ettavum uyarnna digriyude gunakamaayi 1 undaayirikkanam), ennaal kooduthal pothuvaaya kesukalil pothuvaaya kanvenshan illa. athinaal, "gcd of and" umm "and" umm vaayikkendathum athupole thanne athe koottam gcd-kalullathumaaya notteshan polullatho allengil saadhaarana durupayogangalumaanu thulyatha. prathyekichum, invertible sthiraangangal maathramaan pothuvaaya devisorukal ennaanu ardhamaakkunnathu. eee saahacharyathil, poornnasankhya kesumaayi saadrishyam kaanichu, oraal athu parayunnu.
kaikondu kanakkukoottal vazhi jii. sii. dii.
rund bahupadangalude ettavum valia pothuvaaya vibhaajakathe kandethaan niravadhi vazhikalundu. avayil randennam
factoring.
factoring upayogichu rund polynomialukalude jii. sii. dii kandethaan, rund polynomialukalum poornnamaayum factor cheyyuka. thudarnnu, ellah pothuvaaya gadakangaludeyum uthppannam edukkuka. eee ghattathil, namukk oru monic polynomial undayirikkanamennilla, athinaal avasaanamaayi ithine oru sthiraangam kondu gunichu oru monic polynomialaakkuka. ellah pothuvaaya vibhaajakangalum ulppedunna monic aayathinal ithu rund polynomialukalude jii. sii. dii aayirikkum.
udaaharanam onnu aandu-nte jii. sii. dii kandethuka.
athinaal, avarude jii. sii. dii.
euclidean algoritam.
factoring polynomialukal budhimuttaayirikkum, prathyekichu polynomialukalkku valia alavil undengil. euclidean algoritam eathu jody polynomialukalkkum pravartthikkunna oru reethiyaanu. ithu euclidean vibhajanam aavarthichu upayogikkunnu. rund akkangalil eee algoritam upayogikkumbol, oro ghattathilum akkangalude valuppam kurayunnu. polynomialukal ullappol, oro ghattathilum polynomialukalude alavu kurayunnu. aavashyamenkil monic akkia avasaanathe poojyamallaatha sheshikkunna bhagam rund bahupadangalude jii. sii. dii aanu.
kooduthal vyakthamaayi paranjaal, rund bahupadangalude jii. sii. dii. kandethunnathinum, oraalkk (allengil, jii. sii. dii.) oohikkaavunnathumaanu,
euclidean division rund bahupadangal nalkunnu, "koshyant", "bakkiyullava" enningane
oru polynomial randum vibhajikkukayaanenkil maathram, randum vibhajikkunnu. angane
krameekaranam 
puthiya polynomialukal labhikkaan oraalkk euclidean vibhajanam aavarthikkaam. oro ghattathilum nammal 
athinaal kramam oduvil oru pooyintil ethum 
oraalkk jii. sii. dii labhichu 
udaaharanam aandu-nte jii. sii. dii kandethuka
poojyamallaatha avasaanathe seshikkunnathinaal, ithu yadhaartha bahupadangalude oru jii. sii. dii aanu, monic jii. sii. dii. 
eee udaaharanathil, randaam ghattathinu munbu 12 ennam factor outtu cheythukondu denominatorukal avatharippikkunnath ozhivakkaan prayasamilla. suedo-remainer sequenceukal upayogichu ithu ellaayppozhum cheyyaan kazhiyum, pakshe, sradhikkaathe, ithu kanakkukoottalinide valare valia poornnasamkhyakal avatharippikkam. athinaal, computer kanakkukoottalinayi, chuvade vivarichirikkunna mattu algorithangal upayogikkunnu.
kanakkukoottalinide sambhavikkunna gunakangalude poojyathilekkulla thulyatha parisodhikkaan kazhiyumenkil maathrame eee reethi pravartthikkoo. athinaal, praayogikamaayi, gunakangal poornnasamkhyakal, yukthisahamaya samkhyakal, oru parimithamaaya feeldinte gadakangal allengil munbathe feeldukalilonninte parimithamayi srishtikkappetta eathenkilum feeld ekstenshanil ulppettathayirikkanam. ekadesham maathram ariyappedunna yadhaartha samkhyakale prathinidheekarikkunna floating-pooyint nambarukalaanu coffificientukal ennu paranjaal, nannayi nirvachikkapetta kanakkukoottal phalam labhikkunnathin oraal jii. sii. diyude digri arinjirikkanam (athu samkhyaaparamaayi sthirathayulla falamaanu; eee sandarbhangalil mattu saankethikavidyakal upayogikkaam, saadhaaranayaayi ekavachana moolya vighadanathe adisthaanamaakki.
oru feeldil gunakangalulla ekathaanamaaya bahupadangal.
oru feeldil univariot polynomialukalude cases niravadhi kaaranangalal prathyekichum pradhaanamaan. onnamathaayi, ithu ettavum praadhamikamaaya kesaanu, athinaal beejaganithatthile mikka aadya kozhsukalilum ithu prathyakshappedunnu. randaamathaayi, ithu poornnasamkhyakalude kaaryavumaayi valare saamyamullathaan, eee saamyam euclidean domaine enna aashayathinte uravidamaanu. moonnaamathe kaaranam multiveriyettu kesinum oru advitheeya factorisation domainile kofifishyantukalkkumal sidhaanthavum algorithangalum eee prathyeka kesine shakthamayi adisthaanamaakkiyullathaanu ennathaanu. avasaanatheth, polynomial jii. sii. dii algorithangalum deriwade algorithangalum oru polynomialinte verukalekkurichu avaa kanakkukoottathe upayogapradamaaya vivarangal nedaan oraale anuvadikkunnu.
euclidean division.
jii. sii. dii. kall kanakkukoottunnathin yooklidinte algorithathil upayogikkunna polynomialukalude euclidean division poornnasamkhyakalude euclidean divisionumaayi valare saamyamullathaan. athinte nilanilpp inipparayunna sidhaanthathe adisthaanamaakkiyullathaanu oru feeldil nirvachichirikkunna rund eaka variot polynomialukal "a", "b" ≤0 enniva nalkiyaal, thripthippeduthunna rund polynomialukal "q" ("koshyant"), "r" ("bakkiyullava") enniva nilavilundu.
oppam
evide "digg (...) "digri soochippikkunnu, poojya polynomialinte digri negatteevu aayi nirvachikkappedunnu. koodaathe, "q", "r" enniva eee bandhangalal savisheshamaayi nirvachikkappedunnu.
poornnasamkhyakalude euclidean vibhajanathil ninnulla vyathyasam, poornnasamkhyakale sambandhichidatholam, degrick pakaram kevala moolyam nalkunnu, koodaathe savisheshatha labhikkaan "r" negatteevu allennu karuthanam. atharamoru sidhaantham nilanilkkunna valayangale euclidean domainukal ennu vilikkunnu.
poornnasamkhyakaleppole, polynomialukalude euclidean vibhajanam deergha vibhajana algoritam upayogichu kanakkakkaam. eee algoritam saadhaaranayaayi paper-aandu-pensil kanakkukoottalinayi avatharippikkunnu, ennaal inipparayunna reethiyil aupachaarikamaakkumbol ithu computerukalil nannayi pravartthikkunnu (veriyabilukalude perukal pensil-aandu-paper kanakkukoottalil paper sheettinte pradesangalumaayi krithyamaayi poruthappedunnuvennu shradhikkuka). thaazhepparayunna kanakkukoottalil "digg" ennathu athinte vaadathinte alavine (kanvenshanumaayi) soochippikkunnu, "elsie" ennathu veriyabilinte ettavum uyarnna alavinte gunakamaaya leading coffificientine soochippikkunnu.
eee algorithathinte saadhuthayude thelivu, "vail" lupe muzhuvan samayat, oro aavarthanathilum kurayunna oru noonn-negatteevu poornnasankhya namukkund enna vasthuthaye aasrayichirikkunnu. athinaal eee algorithathinte saadhuthayude thelivum euclidean vibhajanathinte saadhuta theliyikkunnu.
yooklidinte algoritam.
poornnasamkhyakale sambandhichidatholam, jii. sii. dii. kall computed cheiyunnathinulla yooklidinte algoritam nirvachikkaan euclidean division namme anuvadikkunnu.
a", "b" ennee rund bahupadangalil ninnu aarambhich, yooklidinte algoritam aavarthichu jodiye maattisthaapikkunnu (ivide "" muun vibhaagathinte algoritam kanakkakkiya euclidean vibhajanathinte sheshikkunna bhaagathe soochippikkunnu), "b" = 0 vare. gcd avasana poojyamallaatha sheshikkunnathaan.
yooklidinte algoritam recursive prograaming shailiyil aupachaarikamaakkaam
imperative prograaming shailiyil, oro intermediat seshikkunnathinum oru peru nalkikkond athe algoritam maarunnu
digri kramam karsanamaayi kurayunnu. athinaal, paramavadhi, ghattangalkk sesham, oraalkk oru poojyamaaya sheshi labikkum. ore devisorukal ullathinaal, pothuvaaya divaisarukalude koottam yooklidinte algoritam mattunnilla, athinaal ellah jodikalkkum ore koottam pothuvaaya devicerukalundu. athinaal aandu 0-nte pothuvaaya bhajakangal. athinaal aandu-nte oru jii. sii. dii. aanu.
ithu yooklidinte algoritam jii. sii. dikal kanakkakkunnuvennu theliyikkuka mathramalla, jii. sii. dikal nilavilundennu theliyikkukayum cheiyunnu.
besouttinte identityum extended jii. sii. dii. algorithavum.
besouttinte aidantitti oru jii. sii. dii. yumayi bandhapetta sidhaanthamaanu, thudakkathil poornnasamkhyakalkku theliyikkappettittund, ithu ellah pradhana ideal domainukalkkum saadhuthayullathaanu. oru feeldile ekathaanamaaya bahupadangalude kaaryatthil, athu inipparayunna reethiyil prasthaavikkam.
polynomialukalude kaaryatthil eee phalatthinte thalpparyam polynomialukal kanakkakkaan kaaryakshamamaya oru algoritam undu ennathaanu, looppinte oro aavarthanathilum cheiyunna kurachu kanakkukoottalukaliloode eee algoritam yooklidinte algorithathil ninnu vyathyasthamaan. athinaal ithine extended jii. sii. dii algoritam ennu vilikkunnu. yooklidinte algorithavumaayulla mattoru vyathyasam, baakkiyullavaykk pakaram euclidean divishante "kwo" ennu soochippikkunna bhaagavum ithu upayogikkunnu ennathaanu. eee algoritam thaazhepparayunna reethiyil pravartthikkunnu.
algoritam athinte outtputtu specification thripthippeduthunnu ennathinte thelivu, oronninum namukk undu enna vasthuthaye aasrayichirikkunnu. 
randaamathethu samathvam soochippikkunnu 
oro aavarthanathilum, digriyude alavu kurayumbol paramavadhi degree vardhanavum undaakumenna vasthuthayil ninnaan digrikalekkurichulla avakaashavaadam pinthudarunnathu.
eee algorithathinte rasakaramaaya oru savisheshatha, besouttinte aidantittiyude gunakangal aavashyamullappol, oraalkk inputt polynomialukalude bhagangal avarude jii. sii. dii vazhi soujanyamaayi labikkum ennathaanu.
beejaganita vipuleekaranangalude ganithashaasthram.
beejaganita feeld ekstenshanukalil vibhajanam kanakkakkaan oraale anuvadikkunnu ennathaanu extended jii. sii. dii algorithathinte oru pradhana prayogam.
kuranja polynomialinu digri ulla oru ghadakam srishtikkunna oru feeldinte beejaganita vipuleekaranam anuvadikkuka. ithinte gadakangale saadhaaranayaayi prathinidheekarikkunnath athinekkaal kuranja digriyil univariot polynomialukalaanu.
kootticherkkal ennathu polynomialukalude kootticherkkalaanu
gunanam ennathu polynomialukalude gunanavum thudarnnu vibhajikkunnathum aannu
poojyamallaatha oru moolakatthinte vipareethamaanu besouttinte aidantittiyile coffificient, ithu extended jii. sii. dii algoritam upayogichu kanakkakkaam. (ettavum kuranja polynomial irreducible aayathinal jii. sii. dii 1 aanu). extended jii. sii. dii algorithathinte specificationile digri asamathvam kaanikkunnath digri () <digri () labhikkunnathin kooduthal vibhajanam aavasyamilla ennaanu.
upa phalangal.
ekathaanamaaya bahupadangalude kaaryatthil, ettavum valia pothuvaaya vibhaajakangalum phalapraapthikalum thammil sakthamaaya bandhamund. kooduthal krithyamaayi paranjaal, "p", "q" ennivayude gcd sthiramallengil maathram poojyamulla "p", "q" ennivayude gunakangalude oru bahupada pravarthanamaanu "p", "q".
rund bahupadangalude jii. sii. dii. yeei pothuvaayi chithreekarikkaan anuvadikkunna eee savisheshathayude saamaanyavalkkaranamaanu subressaltant sidhaantham, athinte falamaayi 0-aam subressaltant polynomialaanu.
p", "q" ennee rund bahupadangalude "i"-th "subressaltant polynomial" "si" ("p", "q") ennathu "i" enna digriyude oru polynomialaanu, athinte gunakangal "p", "q" ennivayude gunakangalude polynomial functionukalaanu, koodaathe "i"-th "pradhana subressaltant coffificient" "si" ("p", "q") ennathu "" si "(" p "," q ") nte digri" i "yude gunakamaanu. p", "q" ennivayude gcd-kku oru digri "d" undengil maathram avarkk oru property undu. 
eee saahacharyathil, "sd" ("p", "q") ennathu "p", "q" ennivayude oru gcd aanu.
subursultant polynomialukalude oro gunakavum "p", "q" ennivayude silvesttar maatriksinte oru submatricsinte nirnnaayakamaayi nirvachikkappedunnu. ithu soochippikkunnathu sub resultantukal nannayi "specialise" cheiyunnu ennaanu. kooduthal krithyamaayi paranjaal, eathu commutative ring "r"-nuu mukalilum polynomialukalkkaayi subursultantukal nirvachikkappedunnu, koodaathe inipparayunna property undu.
φ" ennathu "r"-nte mattoru commutative ringukalilekkulla oru ring homomorphysamyricate. ithu mattoru homomorphysathylake vyaapikkunnu, ithu "r", "s" ennivaykku mukalilulla polynomial valayangalkkidayil "φ" ennum soochippikkunnu. appol, "p", "q" enniva "r"-ll gunakangalulla ekathaanamaaya bahupadangalaanenkil, 
oppam 
appol "p", "q" ennivayude "φ" kondu nirmmichirikkunna chithrangalaanu "φ" ("p"), "φ" ("q") ennivayude subursultant polynomialukalum pradhana subursultant coffificientukalum.
poornnasankhya gunakangalulla rund bahupadangalude jii. sii. dii. yude computerukalile kanakkukoottalin adisthaanamaaya rund pradhana gunangalaanu sub rasaltantukalkullathu.
onnamathaayi, nirnnaayakangaliloodeyulla avayude nirvachanam hudmard asamathvathiloode, jii. sii. diyude gunakangalude valuppam parimithappedutthaan anuvadikkunnu.
randaamathaayi, eee bandhithavum nalla specialisationte savisheshathayum modular computationiloodeyum chainees reminder sidhaanthathiloodeyum (chuvade kaanuka) poornnasankhya gunakangalulla rund polynomialukalude jii. sii. dii. kanakkukoottaan anuvadikkunnu.
saankethika nirvachanam.
anuvadikkuka. 
k" enna feeldil gunakangalulla rund ekathaanamaaya bahupadangal aayirikkuka. namukk 36 enna soothravaakyam upayogichu soochippikkaam, "i"-nekkaal kuranja digriyulla polynomialukalude "i" alavilulla "k" vekttar space. i" ≤ "m", "i" ≤ "n" enningane negatteevu allatha poornnasankhyayaaya "i"-nuu, 
rekheeya bhoopadam angane aayirikkuka
p", "q" ennivayude falamaanu silvesttar maatriksinte nirnnayakam, ithu "x" nte shakthikalude adisthaanathil formula _ 39 nte (square) matricks aanu. athupole, "i"-subresultant polynomial nirvachichirikkunnathu formula _ 40-nte maatriksinte submatrisukalude nirnnaayakangalude adisthaanathil aanu.
namukk eee maatriksukale kooduthal krithyamaayi vivarikkaam;
i" <0 allengil "i"> "m" ennathinu "p" "i" = 0 ennum "i" <0 allengil "i"> "n" ennathinu "q" i "= 0 ennum karuthuka. silvesttar matricks ("m" + "n") × ("m" + "n")-matricks aanu, athaayath "i"-th variyudeyum "j"-th nirayudeyum coffificient "p" "m" + "j"-"i" "" j "≤" n "" num "q" "j" − "" i "" "j"> "" n "" num aannu
42" enna soothravaakyathinte matricks "ti" ennathu ("m" + "n" − "i") × ("m" + "n" − 2 "i")-"s" nte upamatrics aanu, ithu "s" nte "n" − "i", "n" + 1 muthal "m" + "n" − "i" vareyulla nirakalude upamaatriksile poojyangalude avasana "i" varikal neekkam cheythukondu labikkum (athaayath oro blockileyum "i" nirakalum poojyangalude "i" avasana varikalum neekkam cheiyunnu). tii" yude "m" + "n" −2 "i" aadya varikalude nirnnaayakamaan "pradhana upa-falagunakam" "sii" ".
vi" ennathu ("m" + "n" −2 "i") × ("m" + "n" − "i") matricks ayirikkatte. aadyam nammal ("m" + "n" −2 "i" −1) × ("m" + "n" −2 "i" −1) aidantitti maatriksinte valathuvashath poojyangalude nirakal ("i" + 1) cherkkunnu. thudarnnu ("m" + "n" − "i" −1) poojyangal ulkkollunna oru variyum thudarnnu "xi", "x" "i" −1, umm chernnukondu naam thathfalamaayundaakunna maatriksinte adiyil athirthi pankidunnu..., x", 1:
eee notteshan upayogichu, "i"-th "subressaltant polynomial" aanu matricks ulppannamaaya "vitti" yude nirnnayakam. m" + "n" −2 "i" −1 aadya varikalum ("m" + "n" − "i" − "" j ")-th variyum ulkkollunna" ti "yude square submatricsinte nirnnaayakamaan athinte digri" j "enna gunakam.
thelivu varacha chithram.
nirvachichathupole, sub resultantukalkku aavasyamulla gunangalundennu vyakthamalla. ennirunnaalum, leanier algibrayudeyum polynomialukaludeyum gunangal orumichu cherkkukayaanenkil thelivu valare lalithamaanu.
nirvachichathupole, maatriksinte nirakal "ti" ennathu formula _ 42-nte chithratthilulla chila bahupadangalude gunakangalude vektarukalaanu. "i"-th subursultant polynomial "si"-nte nirvachanam kaanikkunnath athinte gunakangalude vector eee koolam vektarukalude oru rekheeya samyojanamaanennu, athinaal "si" formula _ 40-nte chithrathintethaanu.
gcd yude digri "i" nekkaal kooduthalaanengil, soothravaakyathinte chithratthile poojyamallaatha oro polynomialinum "i" nekkaal valia digri undennu besouttinte aidantitti kaanikkunnu. ithu soochippikkunnathu "sii" = 0 ennaanu.
maruvashathu, jii. sii. diyude digri "i" aanenkil, "m" + "n" − "i" ll thaazheyulla digri ulla jii. sii. diyude gunithangal formula _ 42-nte chithrathilaanennu theliyikkaan besouttinte aidantitti veendum anuvadikkunnu. eee gunithangalude vekttar spacinu "m" + "n" −2 "i" enna alavumundu, koodaathe "i"-nekkaal cheruthallaatha jody thirichulla vyathyastha digrikalude polynomialukalude aditharayundu. ithu soochippikkunnathu "tii" yude kolatthile ekkaloon roopathile "emm" + "enn" −2 "aii" aadya varikalude submatrics aidantitti maatriksaanennum athinaal "sii" 0 allennum. athinaal "sii" ennathu soothravaakyathinte chithratthile oru polynomialaanennum, ithu jii. sii. diyude gunithavum ore digriyumaanennum. athinaal ithu ettavum valia pothuvaaya vibhajakamaanu.
jii. sii. diyum root kandethalum.
square free factorisation.
mikka root-finding algorithangalum onniladhikam verukalulla polynomialukalumaayi moshamaayi pravartthikkunnu. athinaal oru root-finding algoritam vilikkunnathinu munbu avaa kandethukayum neekkam cheyyukayum cheiyunnathu upayogapradamaanu. oru bahupadatthinte onniladhikam verukal bahupadatthinteyum athinte derivativinteyum jii. sii. diyude verukalayathinaal onniladhikam verukalude nilanilpp kandethaan oru jii. sii. dii kanakkukoottal anuvadikkunnu.
polynomialinte jii. sii. dii. yum athinte derivative kanakkukoottiyathinusesham, kooduthal jii. sii. dii kanakkukoottalukal polynomialinte poornnamaaya "square free factorisation" nalkunnu, ithu oru factorisationaanu. 
ivide, oro "i"-num, "f"-nuu "i" enna gunithatthinte verukalonnumillenkil allengil "f"-nte "i" enna gunithatthinte verukalulla oru chaturarahita bahupadamaanengil (athaayath onniladhikam verukalillaatha oru bahupadamaanu) bahupadamaaya "f"-nte "i"-nte verukalaanu (yooninte algoritam kaanuka).
angane chathura rahita factorisation onniladhikam verukalulla oru polynomialinte root-finding kuraykkunnu, thaazhnna digriyilulla niravadhi chathura rahita polynomialukalude root-finding vare. mikka polynomial factorisation algorithangaludeyum aadyapadi square free factorisation koodiyaanu.
staram sequence.
yadhaartha gunakangalulla oru polynomialinte "staram sequence" ennathu polynomialil prayogikkunna yooklidinte algoritam vakabhedam nalkunna avashishtangalude sreniyaanu. staram sequence labhikkunnathin, oraal nirddeshathe maattisthaapikkunnu 
yooklidinte algoritam 
a" enna binduvil vilayiruthumbol "v" ("a") ennathu shreniyile chinnangalude maattangalude ennamaayirikkatte. v" ("a") − "v" ("b") ennathu ["a", "b"] enna edavelayile bahupadatthinte yadhaartha verukalude ennamaanennu sturminte sidhaantham urappichu parayunnu. athinaal oru nischitha edavelayil yadhaartha verukalude ennam kanakkakkaan staram sequence anuvadikkunnu. oro upavidhikalilum paramavadhi oru root adangiyirikkunnathuvare edavelaye upavibhaagamaakkunnathiloode, ithu yadhaartha roottukale ekapaksheeyamaaya cheria neelatthinte edavelakalil kandethunna oru algoritam nalkunnu.
oru valayathinum athinte bhinnasamkhyakalude mekhalaykkum mukalilulla jii. sii. dii.
eee vibhaagathil, oru advitheeya factorisation domaine "r", saadhaaranayaayi poornnasamkhyakalude valayam, athinte bhinnasamkhyakalude feeld "f" ennivayil polynomialukal pariganikkunnu, saadhaaranayaayi yukthisahamaya samkhyakalude feeld, eee valayangalile oru koottam veriyabilukalile polynomialukalude valayangale "r" ["x"], "f" ["x"] ennivaye soochippikkunnu.
aadima part-ulladakka factorisation.
kondu (" "p" ")" ennu soochippikkunna oru bahupadatthinte "" ulladakkam "," p "ω" r "[" x "], athinte gunakangalude gcd aanu". oru bahupadamaaya "q" ± "f" ["x"] ezhuthaam.
ivide "p" ω "r" ["x"] umm "c" ω "r" umm "q" (udaaharanathinu avayude gunakam), "p" = "cq" ennivayude gunakangalude ellah denominatorukaludeyum gunithangal "c" edukkaan ithu mathiyakum. q"-nte "ulladakkam" ingane nirvachikkappedunnu
rund saahacharyangalilum, ulladakkam "r" nte oru yoonit kondu gunikkunnathuvare nirvachikkappedunnu.
r" ["x"] allengil "f" ["x"] ennathile oru bahupadatthinte "aadima bhagam" nirvachichirikkunnathu 
rund saahacharyangalilum, ithu "r" ["x"] leeii oru polynomialaanu, athaayath "premitteevu", athaayath 1 athinte gunakangalude oru gcd aanu.
athinaal "r" ["x"] allengil "f" ["x"] ennivayile oro polynomial ingane factorise cheyyaam 
ulladakkathe "r" enna yoonit kondu gunikkunnathinum aadima bhaagathe eee yoonittinte vipareethathaal gunikkunnathinum eee factorisation savisheshamaan.
rund aadima bahupadangalude gunanaphalam aadimamaanennu gassinte lemma soochippikkunnu. athu thudarnnu 
oppam
r" nuu mukalilulla gcd yum "f" nuu mukalilulla gcd yum thammilulla bandham.
munvashathe vibhaagathile bandhangal soochippikkunnathu "r" ["x"] leeii gcd-kalum "f" ["x"]-leeii gcd-kalum thammilulla sakthamaaya bandhamaan. avyakthathakal ozhivakkaan, "jii. sii. dii" enna notteshan thaazhepparayunna reethiyil, jii. sii. dii kanakkukoottunna ring vazhi soochikappeduthum.
q" 1 umm "q" 2 umm "f" ["x"] ll pedunnuvenkil,
p" 1 umm "p" 2 umm "r" ["x"] ll pedunnuvenkil,
oppam
athinaal bahupada gcd-yude kanakkukoottal adisthaanaparamaayi "f" ["x"] nuu mukalilum "r" ["x"] nuu mukalilum ore prasnamaanu.
yukthisahamaya samkhyakalkku mukalilulla ekathaanamaaya bahupadangalkku, yooklidinte algoritam jii. sii. dii anakkukoottunnathinulla soukaryapradamaaya reethiyaanennu oraal chinthichekkaam. ennirunnaalum, athil poornnasamkhyakalude dhaaraalam bhinnasamkhyakal lalithamaakkunnath ulppedunnu, thathfalamaayundaakunna algoritam kaaryakshamamalla. ekkaaranathaal, poornnasamkhyakalkku mukalilulla bahupadangalumaayi maathram pravarthikkunnathinu yooklidinte algoritam parishkkarikkunnathin reethikal roopakalppana cheythittundu. bhinnasamkhyakal avatharippikkunna euclidean divisione "suedo-division" ennu vilikkappedunna oru "suedo-division" ennu maattisthaapikkukayum yooklidinte algoritam bakkiyulla seekwansine "suedo-remainer sequence" ennu vilikkukayum cheiyunnu (chuvade kaanuka).
multiveriyettu polynomialukalkku jii. sii. dii nilavilundennathinte thelivu.
r" ["x"] leeii bahupadangalude gcd "r", "f" ["x"] ennivayile gcd-kalil ninnu kanakkaakkaamenn munbathe vibhaagathil nammal kandu. thelivu sookshumamaayi parishodhichaal, "r" ["x"] lum "f" ["x"] lum ullava undengil, "r" ["x"] ll gcd-kalude nilanilpp theliyikkaan ithu namme anuvadikkunnuvennu kaanikkunnu. prathyekichum, "r" ll gcd-kall nilavilundenkil, "x" oru variable churukkukayaanenkil, ithu "r" ["x"] ll gcd-kall nilavilundennu theliyikkunnu (yooklidinte algoritam "f" ["x"] ll gcd-kall undennu theliyikkunnu).
n" veriyabilukalile oru polynomial ("n" −1) veriyabilukalile polynomialukalude valayathinu mukalilulla oru univariot polynomialaayi kanakkakkaam. athinaal veriyabilukalude annathekkurichulla oru aavarthanam kaanikkunnath jii. sii. dii. kall nilavilundenkil avaa "r" ll kanakkaakkaamenkil, avaa nilanilkkukayum "r" nuu mukalilulla ellah multiveriyettu polynomial ringukalilum kanakkaakkukayum cheyyaam. prathyekichum, "r" ennathu poornnasamkhyakalude valayamo feeldo aanenkil, aanenkil "r" ["x" 1 ll nilavilundu..xn",], koodaathe munpullava avaa kanakkukoottaan oru algoritam nalkunnu.
oru advitheeya factorisation domaininu mukalilulla oru polynomial ring oru advitheeya factorisation domainanennathinte thelivu samaanamaan, pakshe ithu oru algoritam nalkunnilla, kaaranam oru feeldil univariot polynomialukal factor cheiyunnathinu pothuvaaya algoritam illa (univariot polynomialukalkku factorisation algoritam nilavilillaattha feeldukalude udaaharanangalund).
suedo-remainer sequenceukal.
eee vibhaagathil, oru avibhaajya domaine "z" (saadhaaranayaayi poornnasamkhyakalude ring z), athinte bhinnasamkhyakalude feeld "q" (saadhaaranayaayi yukthisahamaya samkhyakalude feeld q) enniva nammal pariganikkunnu. a", "b" ennee rund bahupadangal univariot polynomial ring "z" ["x"] ll nalkiyaal, "a"-nte euclidean division ("q"-nuu mukalil) "b"-nte oru bhaagavum "z" ["x"]-ll ulppedaatha oru seshiyum nalkunnu.
kaaranam, oraal yooklidinte algoritam inipparayunna bahupadangalil prayogikkukayaanenkil 
oppam
yooklidinte algoritam thudarchayaayi avasheshikkunnath
inputt polynomialukalude gunakangalude cheria degree cheria valipavum undaayirunnittum, valia valippathilulla poornnasankhya bhinnasamkhyakal kaikaaryam cheyyukayum lalithamaakkukayum cheyyendathundennu oraal kaanunnu.
yooklidinte algorithathinte oru vakabhedam anuvadikkunnathinaayi "suedo-division" avatharippichu, athinaayi avasheshikkunna ellah gadakangalum "z" ["x"] ll ulppedunnu.
formula _ 64 umm formula _ 65 umm "a" ≤ "b" umm aanenkil, "a" nte suedo division "b" kondu primil ("a", "b") soochippikkunna suedo-remainer aanu 
bii" yude ("x" bii "yude) pradhana gunakam evideyaanu?
z" ["x"] leeii rund bahupadangalude suedo divishante suedo-remainer ellaayppozhum "z" ["x"]-ntethaanu.
nirddeshangal maattisthaapichu labhicha (suedo) avasheshikkunna "r" "i"-nte sreniyaanu suedo-remainer sequence. 
yooklidinte algoritam 
nyoomarettarinte oro gunakatheyum krithyamaayi vibhajikkunna "z"-nte oru gadakamaanu "α". α" yude vyathyastha choisukal adutha upavibhagangalil vivarichirikkunna vyathyastha suedo-remainer sequenceukal nalkunnu.
polynomialukale invertible konsttant kondu gunichaal ("q" ll) rund polynomialukalude pothuvaaya devisorukal maaraathathinaal, oru suedo-remainer seekwansile avasana poojyamallaatha padam inputt polynomialukalude oru gcd ("q" ["x" "ll) aanu. athinaal, suedo-remainer sequenceukal "q" ll bhinnasamkhyakal avatharippikkathe "q" ["x"] ll gcd-kall computed cheyyaan anuvadikkunnu.
chila sandarbhangalil, suedo-remainerinte pradhana gunakathinte adayaalam niyanthrikkendathu athyaavasyamaanu. phalangalum upafalangalum kanakkukoottumbozho starminte sidhaantham upayogikkumbozho ithu saadhaaranayaayi sambhavikkunnu. eee niyanthranam onnukil suedo-remainer enna nirvachanathil athinte kevala moolyam upayogichu maattisthaapikkukayo allengil adayaalam niyanthrikkukayo cheyyaam (oru remainerinte ellah gunakangalum vibhajikkukayaanenkil, athu sariyaanu).
nissaramaaya kapada-avasheshikkunna kramam.
bakkiyullava nirvachikkaan ettavum lalithamaaya kramam ellaayppozhum edukkunnathaanu. praayogikamaayi, ithu rasakaramalla, kaaranam inputt polynomialukalude alavu anusarichu gunakangalude valuppam ganyamaayi valarunnu. ithu munvashathe bhaagatthinte udaaharanathil vyakthamaayi kaanapedunnu, athinu thudarchayaaya kapada-avashishtangal 
thudarchayaaya sheshikkunnavayude gunakangalude akkangalude ennam algorithathinte oro aavarthanathilum erattiyiladhikamaanu. ithu nissaramaaya suedo-remainer seekwansukalude saadhaarana swabhaavamaanu.
aadima suedo-remainer sequence.
premitteevu suedo-remainer sequence" nyoomarettarinte ulladakkam "α" edukkunnathil ulppedunnu. athinaal ellah "r" i "umm aadima bahupadangalaanu.
ettavum cheria gunakangal srishtikkunna suedo-remainer sreniyaanu premitteevu suedo-remainer shreni. ennirunnaalum ithinu "z" ll niravadhi gcd-kall kanakkaakkendathund, athinaal praayogikamaayi upayogikkaan paryaapthamalla, prathyekichu "z" oru polynomial ring aayirikkumbol.
muun vibhaagangalile athe inputt upayogichu, thudarchayaaya avasheshikkunnavar, avayude ulladakkam vibhajichathinusesham 
gunakangalude cheria valippam niravadhi poornnasamkhyakal gcd yum gcd kondu divisionukalum kanakkakkiyittundenna vastutha marachuvekkunnu.
upa falamaaya suedo-remainer sequence.
suedo-remainer upayogichu oru sub resultant sequence kanakkakkaam. oro "r" "i" umm oru sub resultant polynomial aayirikkunna vidhathil "α" thiranjedukkunnathil eee prakriya ulppedunnu. athisayakaramennu parayatte, "α" yude kanakkukoottal valare eluppamaanu (chuvade kaanuka). maruvashathu, algoritam krithyathayude thelivu budhimuttaanu, kaaranam thudarchayaaya rund avasheshikkunnavarude digrikalude vyathyasathinulla ellah saadhyathakalum ithu kanakkiledukkanam.
upa-phala shreniyile gunakangal apoorvvamaayi maathrame aadima suedo-remainer shreniyekkaal valuthaakunnulloo. z" leeii gcd kanakkukoottalukal aavasyamillaathathinaal, suedo-remainer ulla subursultant sequence ettavum kaaryakshamamaya kanakkukoottal nalkunnu.
muun vibhaagangalile athe inputt upayogichu, thudarchayaaya sheshippukal ivayaanu
gunakangalkk nyayamaaya valippamund. krithyamaaya divisionukal maathram, oru jii. sii. dii kanakkukoottalum illaathe avaa labikkum. ithu eee algoritam aadima suedo-remainer seekwansukalekkaal kooduthal kaaryakshamamakkunnu.
suedo-remainer upayogichu sub resultant sequence kanakkukoottunna algoritam chuvade nalkiyirikkunnu. eee algorithathil, inputt "z" [x] leeii oru jodi polynomialukalaanu. z" [x]-leeii thudarchayaaya suedo avasheshikkunnavayaanu "i" enna variableukal, avaa negatteevu allatha poornnasamkhyakalaanu, greak aksharangal "z"-leeii gadakangale soochippikkunnu. cocks _ 1, cocks _ 2 ennee functionukal oru polynomialinteyum euclidean divisionte sheshikkunna bhaagathinteyum alavine soochippikkunnu. algorithathil, eee bakkiyullava ellaayppozhum "z" [x]-laanu. avasaanamaayi soochippikkunna/ellaayppozhum krithyathayulla divisionukalkku "z" [x] allengil "z" ll phalam labikkum.
 avasaanippikkukayaanenkil
avasanippikkuka.
kurippu "elsie" ennathu veriyabilinte ettavum uyarnna digriyude gunakamaaya leading coffificientine soochippikkunnu.
eee algoritam ettavum valia pothuvaaya vibhaajakathe (avasaanathe poojyamallaatthava) mathramalla, ellah upa-phalabhooyishtamaaya bahupadangaleyum kanakkaakkunnu bakkiyullava-th upa-phalabhooyishtamaaya bahupadamaanu. - th sub resultant polynomial aanenkil. matellaa upa-phala bahupadangalum poojyamaanu.
suedo-remainermar ulla staram sequence.
staram seekwansukalude athe gunangalulla sequenceukal nirmmikkunnathin oraalkk suedo-remainers upayogikkaam. staram seekwansile athe adayaalangal undaakunnathin ithinu thudarchayaaya suedo-remainermaarude adayaalangal niyanthrikkendathundu. oru parishkaricha suedo-remainerine inipparayunna reethiyil nirvachichukondu ithu cheyyaam.
formula _ 64 umm formula _ 65 umm "a" ± "b" umm aanenkil, "a" nte suedo-division "b" kondu parishkkaricha suedo-remainer prem 2 ("a", "b") aanu 
evide |ell. sii. ("bii")| bii" yude ("x" bii "yude) pradhana gunakathinte kevala moolyamaanithu.
poornnasankhya gunakangalulla inputt polynomialukalkku, ithu poornnasankhya gunakangalulla polynomialukal adangiya staram sequenceukal veendedukkaan anuvadikkunnu. upaphalamaaya suedo-remainer sequence samanamaaya reethiyil parishkkarikkam, eee saahacharyathil avasheshikkunnavarude adayaalangal yukthikalude adisthaanathil kanakkakkiyavayumaayi poruthappedunnu.
mukalil nalkiyirikkunna suedo-remainer sequence anakkukoottunnathinulla algoritam formula 85 nuu pakaram formula 84 upayogikkukayaanenkil thettaaya suedo-remainer polynomialukal kanakkaakkumenn shradhikkuka.
modular jii. sii. dii. algoritam.
f", "g" enniva "f" ["x"] leeii polynomiyalukalaanenkil, avayude gcd anakkukoottunnathinulla ettavum swaabhaavika maarggam euclidean algoritam aanu. ennirunnaalum, intermediat expression veekkam enna prathibhasam kaaranam "f" parimithamaanengil maathrame aadhunika computer beejaganita samvidaanangal ithu upayogikkunnulloo. euclidean algoritam samayat digri kurayunnundengilum, "f" parimithamallengil, kanakkukoottalukalil bahupadangalude bitt valuppam vardhikkum (chilappol naadakeeyamaayi) kaaranam "f"-leeii aavarthichulla ganitha pravartthanangal valia padaprayogangalilekku nayikkunnu. udaaharanathinu, "bii" kondu parimithappedutthiyirikku rund yukthisahamaya samkhyakal kootticherkkunnathu "bii" 2 kondu parimithappedutthiyirikku oru yukthisahamaya samkhyayilekku nayikkunnu, athinaal ettavum mosham saahacharyathil, oru pravartthanatthiloode bitt valuppam ekadesham erattiyaayekkaam.
kanakkukoottal vegathilaakkaan, "f", "g" enniva "d" ["x"] ll ulla oru ring "d" edukkuka, koodaathe "d"/"i" oru parimithamaaya ring aaya oru ideal "i" edukkuka. thudarnnu euclidean algoritam upayogichu eee parimithamaaya valayathinu mukalilulla jii. sii. dii kanakkaakkuka. punarnirmmaana saankethikavidyakal (chainees reminder sidhaantham, yukthisahamaya punarnirmmaanam muthalaayava) upayogikkunnu.) oraalkk "f", "g" ennivayude gcd athinte imej modulukalil ninnu niravadhi idealukal "i" veendedukkaan kazhiyum. minimum allatha digri ulla modular emejukal upekshikkukayum oru pramukha coffificient aprathyakshamaakunna ideal "i" modulo ozhivaakkukayum cheythaal ithu pravarthikkunnuvennu oraalkk theliyikkaan kazhiyum.
formula _ 86, formula _ 87, formula _ 88, formula _ 89 enniva edukkukayaanengil formula _ 91 oru parimithamaaya valayamaanu (formula _ 92 formula _ 93 ll paramavadhi allaathathinaal oru feeldalla). formula 95-leeii formula 94-nte chithrangalil prayogikkunna euclidean algoritam vijayikkukayum 1 nalkukayum cheiyunnu. ithu soochippikkunnathu formula 97-leeii formula 94-nte gcd yum 1 aayirikkanam ennaanu. eee udaaharanam eathu reethiyilum eluppathil kaikaaryam cheyyaan kazhiyumennathu shradhikkuka, kaaranam padaprayogam veengaan digri valare cheruthaanu, ennaal rund polynomialukalkku gcd 1 undengil, modular algoritam orotta ideal formula _ 92 nuu sesham avasanikkaan saadhyathayundennu ithu vyakthamaakkunnu.

