F:=X^12+100/3*X^11+450*X^10+3100*X^9+10975*X^8+15000*X^7-14500*X^6-49000*X^5+
15375*X^4+57500*X^3+7500*X+625;

# F is obtained from the polynomial given in:
#   Matzat, B. H., Zeh-Marschke, A. (1986).
#   "Realisierung der Mathieugruppen M11 und M12 als
#    Galoisgruppen ueber Q", J. Number Theory, 23, 195-202.


f := `galois/rsetpol`(F,X,6):	# Maple 6 command to determine
				# the 6-set resolvent polynomial. Note:
				# this takes quite a while.

# f has degree binomial(12,6) = 924. It takes 1 megabyte to store f.
#
# It factors as (degree 132)*(degree 792).
#
# The 5-set resolvent polynomial `galois/rsetpol`(F,X,5) is irreducible.
# This proves that the Galois group of F over Q is the Mathieu group M12.
# See: http://for.mat.bham.ac.uk/atlas/html/M12.html for details on M12.

# Factorization in Maple took 55000 seconds and 174 Mb of memory on
# a SUN sparc Ultra-4, most of which was spent on Hensel lifting.
# Verifying irreducibility of the 5-set resolvent polynomial can be done
# in much less time and memory because we need less Hensel lifting, we
# only need Hensel lifting to construct an irreducibility proof but not
# to construct factors.

# The factor of degree 132 is given below. The factor of degree 792 is
# omitted because it is so large (about 740 kilobyte) but it can be found
# by computing normal(f/f132).


# Group M12 is generated by the following two permutations given in
# disjoint cycle notation:
#
#	g1 = [[1, 3, 4, 2], [7, 9, 10, 8]]
#	g2 = [[4, 5, 7, 6], [8, 9, 11, 12]]
#
# These g1 and g2 act on the complex roots of F if we order these roots
# in the following way:
#
# [-7.69962172, -7.10342551 + .872778441 I, -7.10342551 - .872778441 I,
#
#   -5.47856184, -3.40578613 - 1.54263859 I, -3.40578613 + 1.54263859 I,
#
#   -1.42549440, .0502211630 + .347077243 I, .0502211630 - .347077243 I,
#
#   -.0795730205, 1.13394930 - .444401237 I, 1.13394930 + .444401237 I]
#
# Note that you can use this information to calculate the complex roots of
# polynomial f132 below, and if you use sufficiently many digits then f132
# can be reconstructed from that. This gives a second method to find
# f132. However, the factorization algorithm does not use such information
# because it will usually not be available, in general we do not know
# the Galois group in advance nor its action on the complex roots.

# Mark van Hoeij, July 2000.

f132 := 150094635296999121*X^132+1545974743559090946300*X^131+
5487272248164166614858750*X^130-76147276802358912495803437500*X^129-\
179964232676065508558504565234375*X^128+85593063910743073548390847500000000*X^
127+24178922178769584559744227896484375000*X^126+
40834639921225525317034348947363281250000*X^125+
940936106967354395306054442288248291015625000*X^124-\
767574381894174096199710342922617736816406250000*X^123-\
566060191953724710517864835659679063415527343750000*X^122+
1371036158731569493755261673898692463607788085937500000*X^121-\
1412766133067225848424981696998349768702030181884765625000*X^120+
240686136300300927894273972097829721365189552307128906250000*X^119+
937717395085434227947706120273554242059305608272552490234375000*X^118-\
1378368748895616559488240774143141812123147442936897277832031250000*X^117+
1325355002877664036541822192135878562397130873426795005798339843750000*X^116-\
982567062890584642247174210105744457763062579506076872348785400390625000*X^115
+655280440582925741358670317402328928382708457142114639282226562500000000000*X
^114-4065141938710386922873528724173507277510969950935541419312357902526855468\
75000*X^113+227008114781832269040979754880803727647637736184561799746006727218\
627929687500000*X^112-11211276766373130038437323007720441388200516493616500883\
9452639222145080566406250000*X^111+4763029282295589048882702222509669629409916\
3255852528209288720972836017608642578125000*X^110-1716347268074204064114981090\
1278941797863576797852779693585034692659974098205566406250000*X^109+5223701933\
305013821060914777765738221168134548280807020233851289958693087100982666015625\
000*X^108-13540957604346697231607871313774237248459646546549772974145753323682\
58386850357055664062500000*X^107+300774028216493702000398519367759467800639232\
953395857846565775162162026390433311462402343750000*X^106-56867059080730438441\
559683711892888604282821220383826257037007678718509851023554801940917968750000
*X^105+89845091080628293381416466831685588358974441395077410121058902880974983\
41812752187252044677734375000*X^104-117535876104332297128902960755296161150484\
1935629096854591054133187810748495394363999366760253906250000*X^103+1207263985\
050331417150923581098979143297220236245408719604243000245169525896926643326878\
54766845703125000*X^102-636253059794013530256898535157700290349694044302178247\
3735235147183075810062291566282510757446289062500000*X^101-2571812873041869657\
306701234214933398204930342322830494904817365091342917793326705577783286571502\
68554687500*X^100+153694414091571913359042409239559834885723074002092934528838\
726244460988201723239399143494665622711181640625000*X^99-251711250641588220616\
501647360220668139236220142492609909308032923929906998772310089407255873084068\
29833984375000*X^98+1305435182253817444212501614003694736754986844308470594101\
499855031723283660394230309975682757794857025146484375000*X^97-345866038480611\
751799335818569585271783844480981288534559551174386283990593721204831467730400\
618165731430053710937500*X^96-336722400659146932203597622293938983757549814156\
02934705557306400537187583005271918068501690868288278579711914062500000*X^95-\
143819551103193806287014225623068279026037026566809600008224453430804983813332\
6814304524532417417503893375396728515625000*X^94-30843766112193102077360347555\
769725704124904746111667743756181989769002630276222010063946754598873667418956\
7565917968750000*X^93+61725747363250993191514349683689135289762130040063601552\
5651413391724539779449772158859133242003736086189746856689453125000*X^92-74278\
345123046085835518917649507913975058649041934642824414941917527843687155000938\
07713177795903902733698487281799316406250000*X^91-1008794413928556499339956836\
986235274738694162362725022426285362980647074778051553844288035222120925027411\
43107414245605468750000*X^90-4023964735882724608425106167919422660536476387113\
959410854293522811813267097725432428975689269634585798485204577445983886718750\
0000*X^89-19653933672479666618424759103248677275433272082626999811345673900604\
69171617645599934730456237463869229031843133270740509033203125000*X^88-1450965\
429827349050572270584920944230012903238333782577535688417683079399592374501852\
17414497240717707882140530273318290710449218750000*X^87+3436676662396116167170\
493625946896197447139763852460387666666071414968152041136556971088458680568811\
2320922300568781793117523193359375000*X^86+60797128998593264200624220069619270\
410524581586901878741468044005415680598990516938596552281529744599097853097191\
54611229896545410156250000*X^85+4787075136150386997438828645287684441280708990\
573263994517561550984879545163760004730450872993327560145360166643513366580009\
46044921875000000*X^84+1520720072860366647803448991843804347648492941200806784\
375782334784104948153019374871086924937352898717923821436670550610870122909545\
8984375000*X^83-49701087486863063537929448338756391435632935134701715734694496\
205671796564379192492044123085422231700380990560006466694176197052001953125000\
0000*X^82-91783259604988889136382905677145695198982995798151045675024416778251\
153306230107896085585457016106712517522492333910122397355735301971435546875000
*X^81-580042753383703464674224560756959212925621288792131773454265065988296445\
8040383550080663874753102642956373302673966918518999591469764709472656250000*X
^80-27373197405416696102922576992706653153050804132361697381724675967323137979\
2649421295328979206142624140294869472533889620535774156451225280761718750000*X
^79-11422250103099886176855532286107229866056068933184392523729900714282801633\
207527540011991288994233049674631268188829125165284494869410991668701171875000
*X^78-353102326919956296563199905064645095013938555934624695789286008351196885\
523527213695502542140138899085644421174667861862417339580133557319641113281250\
000*X^77-188159907498835209017341266283441314686429429023449386020051090085218\
535125524233508502394099032680528588233181269684379799400630872696638107299804\
6875000*X^76+51682886505040495671176215260096809956512088183609518700019211602\
029153712724778711183987892229860324145907001305855210659956355812028050422668\
4570312500000*X^75+31625815913592777191299827401884167446713129173132801181261\
368478492744497213394856553806241078547315952482703966738841749872790387598797\
678947448730468750000*X^74+958012782818709403674421571789346404960570131858929\
398210308391690821392017881499362655935585000435143548752175675711773017440009\
425627067685127258300781250000*X^73+105554537299224691866806381270869357578372\
261950008063757703774053726835709722831777978464800599739040872934925434324313\
07603991399446385912597179412841796875000*X^72-4849018890096787912693361646008\
060543314289438973573023987724634936506087172014141146385621452911281161685940\
25964808449935539158559549832716584205627441406250000*X^71-3043962119384570742\
951736521148706972013115804214449042511533887444382703714406278220395718812834\
4193988259531726965861735123564102423188160173594951629638671875000*X^70-78323\
854345347349287254782583696056337633415787489659662706024058827299174951678007\
100904805064635376455636431681313260749766058665954915340989828109741210937500\
0000*X^69-37294128410145899863973592211230395703453576568625736693195575545205\
833068596007431377182376757619241393400826495772703444726153820809599892527330\
66678047180175781250*X^68+4856649208631768316279955195914471667548106690723426\
351205789574279531026410686534517016568354232759738428323950049303936102318424\
16169456555508077144622802734375000000*X^67+1912425518608831437299335257871142\
084370247975095757208957563277723839806672971546359339575293434623638136302267\
9184924045123639829713013682521705050021409988403320312500*X^66+30354057553948\
551976749719974465447922175666817021414695036184839247068915066790840731353552\
213954748365177024687808149600639490151010591034719254821538925170898437500000\
0*X^65-14568018910213242134364684457511873321661553347119428395779521697346028\
542420315402881711865920945016169297197849911212283096153836253749958018488541\
71112179756164550781250*X^64-1912203475228206769708368715422267000430503315124\
259269109033790498713358763468701345236933717398324620498936320344562030023585\
41664928992531713447533547878265380859375000000*X^63-4644717589392960728380945\
619428568988057122503989332645433859081183445287650156064179070615864310332334\
634327961267984273547907120120725732448363487492315471172332763671875000*X^62-\
462438477525404731053672947502904943782261794946057608031055892461443527905656\
255831373750825205925098579973245587166261611498983916807015148719983699265867\
47169494628906250000*X^61+6291540700151007882762335614613852356575266239047531\
113487707022054602844102551447032598543202861490301664765205045003478291029572\
15689773118327821066486649215221405029296875000*X^60+3568875725637038810828408\
493806967157723643376897757493742959170381804525918817145238280056361110639361\
8462688314754954465383291595638806659174235846876399591565132141113281250000*X
^59+73634590752405992688843578570252674274875617523521187671603095900483300204\
419984613903347032793209226691356636506362915388012282521461131234996599914666\
1488339304924011230468750000*X^58+75208498317865444800083373062220649381214881\
117353097506593929723063998554025280043692310416706983704565074005667491598665\
88358390731162278486365835306060034781694412231445312500000*X^57-1711304389562\
748920228307418105408166288083785033899275913891779830178485331309580110449988\
742699865984725267310474777148550862246999682957787625170453793543856590986251\
8310546875000*X^56-20071543469837041389109794241940397513072784700774758209109\
109449809516577461591492436954362127545385058307441265007006587514955534377197\
61638580173723767074989154934883117675781250000*X^55-4057998418396339764362157\
711057658767848035428892356621492574473920030311975724949040508451856451106349\
734654155564728187245469424273022578369268797970903506211470812559127807617187\
5000*X^54-60780708034206423435558301876972316153515239217334670000446985510141\
080187340594530660315798740761326145436321274104689690481552511164338339737234\
2180631221708608791232109069824218750000*X^53-80497102509194876734131074530043\
005860971595643045785808159668093849709841763655910904849338131964483438925176\
87757246656887188215552127835495169194679476731835165992379188537597656250000*
X^52-7960928756922399611473022968984877764576143007436204660899650776607473892\
153818061802812837501201289520026898831147308746351472863962992934205430833882\
7439683882403187453746795654296875000*X^51-26943013514074526652130729339094543\
934507601910800591733609384820697576397253467188625996570410041722145217443083\
0845580816759374774046190874690620553622011357219889760017395019531250000000*X
^50+51524000210547628453834472509515792744780364044839440612852906342410217192\
483260747767400728404838325191153545748060946956043360112541833295242898679844\
32333969380124472081661224365234375000*X^49+1013702590325310840974917998079765\
806254203067660112583876353244937399079953276813830741920917701870550134865835\
201479413502109547932447652511837518640724908891570521518588066101074218750000\
00*X^48+8046433025043490929519865915907519889402179945385514691852858185284204\
701764442204564905872697789798532574669492363772566495643694033341665126891299\
04800644510487472871318459510803222656250000*X^47+2842752306747514061472940531\
862910808692392530696178508205014390716278829186700155550173531209318120405240\
901744444408798136434074401876893086791946683999920963969998410902917385101318\
359375000*X^46-750131545648658549978876679458235933850051213478251699858414543\
526788143242196295266724637518810573954954045164060926931515239491977501264570\
1324108180041427829110034508630633354187011718750000*X^45-63505284743274638406\
065934331351601936878084351960549896853830462543813630325227222495388324105873\
023985532070060362858687850927590928685793004703223803286693538439067197032272\
815704345703125000*X^44-812633206816224209832594006483319981023254720156953073\
089964225225241066367209554870784315848932965750185983371281886802329421028390\
790769355019041147308866968046459078323096036911010742187500000*X^43-127327755\
928572985619930742841855671898019338934264723330790101358687274268272749102160\
785448844014839445471096255072875525334724356419638472720336284764452994267003\
3051399514079093933105468750000*X^42-58595282572084862787555013519395661438027\
448267615697813011418425765350714956035493125468839657234827850200944598494065\
009090951160473648834779272954889975388859113536454970017075538635253906250000
*X^41+304331430877610381852169964300873929015775570259829451689993303067714906\
839070527852806822401179680293223176996524097375513784783609228958477284686997\
1558991796456439260509796440601348876953125000*X^40-95044692405038353412721692\
780924965188613807837160627054266858449216884859332280035894134591143337971291\
306070055803524317950967114299394098128412677948910480818511814504745416343212\
1276855468750000*X^39-27698638005797127212106922265755257549831351613863522038\
036200097695926465064777801743069640764202273900211520363750617298474380220789\
32861997785936565585375446207905270057381130754947662353515625000*X^38-4053148\
464846296251805925731615306081968738425997846539521381785241029098372395383136\
045707015069222223633505608969328435134471128266930974940926362895402337849226\
6260764154139906167984008789062500000*X^37-26020068760015553386045629578472639\
076395808686495232225936646509937449076021854281949510846180425085979100352660\
287729515712114989605242828413272973040419730125782926677402429049834609031677\
2460937500*X^36+61381267284161028577337631683459514618309646934967053821362572\
636194414023030151350433563316806205243178217765220711798650625311732002662511\
1831729662910015453414214192662257119081914424896240234375000*X^35-73971288291\
899961344754204253838472838392943695978139701556873497198999493667398756056240\
257767783538020087806136832768630611930995123836876054036141606796766687081934\
32166808634065091609954833984375000*X^34+2822920554962252555067462598690447757\
290603682596487592211520959287563490820425301658352001023398725884656753813299\
268064792058603720474529479252222436998622043941020720581036584917455911636352\
5390625000*X^33-29522963902663620057968546114233675297941864601644083364969260\
144199051187827045961914799118215579637002953871160784956838972778224536615559\
799027511906259555862080956600834724667947739362716674804687500*X^32-456489183\
032994391855493885413988226011068839870022219002782981113670149332577071559073\
486523196711704001800441581253017303109035110280531428902298993363856414312573\
761549174378160387277603149414062500000*X^31+541355893851420265280092922129521\
865226660530882136916743358925630786247652934159905545382266569896902353033523\
190870875542420645567098529065772461345453247822268744160467690562654752284288\
4063720703125000*X^30-32940568537614562143397385165339709263849618665639782866\
341931045771514118222525350612129502069456512366021679129082267486663629316923\
813289469816774965373490932987743384785517264390364289283752441406250000*X^29+
157374735198009683740007057094191730935279347163171149572206391829926791236085\
577214510811885277010861371087141418962755300330129459671510386483474763566326\
498263024669110876629929407499730587005615234375000*X^28-622560332503876616787\
919357904455273672882403956807987938412691628136823325659309983628656994066237\
696332792074309086104347619742779097175309276105548337789150721219288975305516\
942171379923820495605468750000*X^27+205797941332305577604514087052729190900843\
596662447083785112175613263682783108781431568179838693136794237177846730953594\
207581167570554841489033406079972498146555236198107508016619249247014522552490\
2343750000*X^26-57906869801203859682224911213559193456353513065981772982106074\
996453627499758104517142328901224231383071955286401974183570015757390082550457\
25744503264976517349724854932802031726168934255838394165039062500000*X^25+1396\
172618337801718198049305776044966694911458285872798139938513978313553023885042\
759985598197327335957000828834179865307254280150227858844064891150915598653821\
5110139005137313006343902088701725006103515625000*X^24-28671202552324262683042\
154006864481825652933186058013120452553858139018450148793281337185260323415303\
604270926664616553892542302513517905556785286491293829165902121505760113961969\
182128086686134338378906250000*X^23+497283460111539404718112848958889034688410\
823069885058709218930331938148789699258511319126688580581935694849328771455110\
572554943518589195357205690999550723940884596266376327378111454891040921211242\
67578125000*X^22-7315699437558263565554779177696669062752471282823863333203739\
298975608354086434487175387294433618311285268171741075061445967647327277417172\
1197751655919836153053751118258141161732055479660630226135253906250000*X^21+92\
581066603613250374361011694930753674053253341911366906773813099727166705335589\
758477256611982875292750336496267889572263792168233191139363967013748065283851\
209749527155778991982515435665845870971679687500000*X^20-103618315842636999755\
804601506635999471227435987372910911662045136621380035419603410946440922438091\
168490244779118991127225153996427962922160453733973797180935953461504428485540\
074689197354018688201904296875000*X^19+104392196941596850971987231390775804264\
045249160696946574687617689417683412008775436585704845923280817982190914768258\
099557862850596158896227258170301759011237147101169853158353362232446670532226\
562500000000000*X^18-978324775022601197773899476289923098272424310866564381423\
811430580985325159962684331167938194741234121174352550803516833823095373454335\
29335065951975449352769664324892817663936739336350001394748687744140625000*X^
17+824770443149740073122324328609166120244949975073162051685635283498031758870\
924161819805369624394165339776000187197173317977747032314676646008865115027071\
60107525146894302814359889453044161200523376464843750000*X^16-5361006114314855\
965954687898607493410794848355033009214723327385428679533357305780972660970737\
463665980907943308892831594932466500326807241921333788641575045753819191152178\
5470995382638648152351379394531250000*X^15+22794647171612537027811840448031204\
021258971879843199635327809627660059004244802873002750819122276074565345549413\
965184199784711340885190029186694328650951096065422306347070247056763037107884\
883880615234375000*X^14+365672242032749463936253026204326651502003756896927753\
585836810119186032384492255586262013759422748968594139937671334515504272316134\
1429643983175546485752839808444983327184729660075390711426734924316406250000*X
^13-13415016525454945621311609371805210324554793115779339412252383890917874468\
394189683182667083700058090878181282220654177270638955015148414908411071104071\
250436655057293455772793322466895915567874908447265625000*X^12+813672920445118\
934642075846800965024177800410878540308453306082006119355720091190479141575988\
164277984103861855458646157197287395046239799918423027315657777668164371553949\
3655342084821313619613647460937500000*X^11-20996339456540580932202354323215013\
806503153782665590724950702381288885230821474405695828957539194143052097728918\
567021232260526469612153886211011567743184735195579454503089777972490992397069\
93103027343750000*X^10-1779432261519978907530331596200320013540784562006451857\
478311973941212318648052467763860006806513054096709894042322764523512221981200\
665402477118615190027586288193731101081596079893643036484718322753906250000*X^
9+1363330466940307958920027853948785490634250768618001844776178060239742157793\
714636026283186811155545308229845053532238123040474446198406115788389567778623\
250615698848930978925864110351540148258209228515625000*X^8+3697853944260640595\
786860212660055343881136814064273901389031617582184721232247896981523806172087\
246343260740249378971504113547167701433939657262290924868750161165487089220960\
1151989772915840148925781250000*X^7+136847849826789322924160626066585362713139\
011833478983811610458619423792421872247797438658584177228340581120863393072298\
731721228034017081847516437362167489088854085976798558021982898935675621032714\
84375000*X^6+30277473365202881057562030521001361217915150479425562525401902676\
711996767153967058741856570687190202900143240251912320690077280176193692726694\
492716164083378344029640061307873111218214035034179687500000000*X^5-3978755705\
033566977717948861604199119406519527148081837666966534556822025097030888202072\
124706920975511591990783669681311124590389534572220296493008084108422126761502\
7295416751940138055942952632904052734375*X^4-105219314796256750552327015239080\
128281233055995791562395615861125970943602216957001762245769377549377696500223\
248720829744403114052265397067215048207042241523007618242413485631914227269589\
90097045898437500*X^3+47389008042837775568894722025755266279074995006146102121\
107706520727638030560197712011948651622149154016498527355542885303199139929178\
7381945133933040073959396280486866537273726862622424960136413574218750*X^2+834\
456154205951188770840833017538965833200753176915327806970590425504618789568223\
123265755653072342952046252319489335177322376895528671322534769294340062533213\
95168986995827253849711269140243530273437500*X+5063447537657470805648306025591\
862656754858939180311455139384650640197929548350868466418420224953537330377744\
657095480444917335531120578413439134067597466827754561224939067187733598984777\
927398681640625;