서론
최근 finite field 위에서는 univariate polynomial을 빠르게 풀 수 있다는 소프트웨어 멤버십 노규민 님의 말씀을 들었습니다.
일반적인 합성수 modulus 위에서 Coppersmith method 등을 통해서 작은 값을 가지는 해를 구하는 방법에 대해서만 접해보았기 때문에, 이 방법에 흥미를 느끼고 한 번 정리해보게 되었습니다.
본론
찾아보니 해를 구하는 것은 Polynomial factorization과 밀접한 관련이 있어서, 유명한 Polynomial factorization 알고리즘인 Cantor–Zassenhaus algorithm을 알아보고, 이를 바탕으로 해를 구하는 방법에 대해서 알아보려고 합니다.
Cantor–Zassenhaus algorithm
Cantor–Zassenhaus algorithm의 메인 아이디어는 equal-degree factorization, 즉 같은 차수를 갖는 여러 개의 distinct한 irreiducible polynomial의 곱으로 구성되어 있을 때 이를 확률적으로 인수분해하는 것에 있습니다.
만약 어떤 polynomial $P$가 degree $d$를 갖는 서로 다른 Irreducible polynomial $P_1, P_2, \dots, P_k$의 곱으로 구성된다고 합시다. 그러면 직관적으로 $\text{F}_q[X]/(P)$ 는 $\text{F}_q[X]/(P_1) \times \text{F}q[X]/(P_2) \times \ldots \times \text{F}q[X]/(P_k)$ 와 isomorphic할 것입니다. (중국인의 나머지 정리 비슷한 느낌으로) 그러면 이 집합은 또 $\text{F}{q^d} \times \ldots \times \text{F}{q^d}$ 와 isomorphic할 것이므로, 우리는 $\text{F}_q[X]/(P)$ 의 원소 $x$에 대해서 $x^{q^d} - x = 0$이 성립한다는 것을 알 수 있습니다. $x^{q^d} - x = 0$은 $x^{q^d} - x = x (x^{(q^d - 1) / 2} - 1)(x^{(q^d - 1) / 2} + 1) = 0$ 으로 다시 나타낼 수 있으므로 이러한 결론을 내릴 수 있습니다: $x$에 대해서 $\gcd(x^{(q^d - 1) / 2} - 1, P)$를 계산하면 $\gcd(x^{(q^d - 1) / 2} - 1, P_k)$가 자명하지 않은 식이 나오지 않는 $k$들에 대해서 곱한 결과를 얻을 수 있으며, 이는 확률적으로 $P$를 절반 정도로 나누게 될 것입니다.
그러므로 무작위로 계속 $x$를 고르면서 $\gcd(x^{(q^d - 1) / 2} - 1, P)$를 계산하면서 degree $d$인 식으로 구성될 때까지 진행하게 되면, 언젠가는 인수분해가 끝나게 될 것입니다.
Solving Univariate Polynomial over Finite Field
어떤 polynomial $P$에 대해서 해 ${x_1, x_2, \ldots, x_k}$를 구한다고 합시다. 이는 곧 $P$가 $(x - x_1)(x - x_2) \ldots (x-x_k)$를 인수로 가짐을 의미합니다. $P$와 $x(x-1)(x-2)\ldots (x-q+1)$의 GCD를 구하게 되면 해당 식은 degree가 1인 식들의 곱으로만 이루어진 식이 될 것이며, 이에 대해서 Cantor–Zassenhaus algorithm를 적용하면 $(x - x_1)(x - x_2) \ldots (x-x_k)$를 얻어낼 수 있을 것입니다.
곧, finite field 위에서 univariate polynomial를 효율적으로 풀어낼 수 있게 됩니다!
코딩
이를 직접 실험해보기 위해서 sage를 통해서 코딩해보도록 하겠습니다. 이미 sage 내부에는 f.roots()와 같은 훌륭한 방법이 있지만, 이해를 위해서 코딩해보는 것도 나쁘지 않은 선택이라고 생각했습니다.
import random
def gcd_poly(f, g):
if g == 0:
return f
while f % g != 0:
f, g = g, f % g
return g
p = random_prime(2^512-1,False,2^511)
F = GF(p)
PR.<x> = PolynomialRing(F)
f = (x - 1) * (x - 2) * (x - 3)
g = pow(x, p, f) - x
if g != 0:
f = gcd_poly(f, g)
queue = [f]
result = []
while queue:
print(queue, result)
f, queue = queue[0], queue[1:]
t = x - random.randint(0, p - 1)
t = pow(t, (p - 1) // 2, f) - 1
g = gcd_poly(f, t)
h = f // g
for t in [g, h]:
if t.degree() == 1:
result.append(t)
elif t.degree() > 1:
queue.append(t)
print(result)
for f in result:
print(F(-f[0]) / F(f[1]))
실행시켜보니 다음과 같이 결과가 잘 나오는 것을 확인할 수 있었습니다.
[x^3 + 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406955*x^2 + 11*x + 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406955] []
[x^3 + 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406955*x^2 + 11*x + 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406955] []
[x^3 + 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406955*x^2 + 11*x + 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406955] []
[7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406960*x^2 + 4*x + 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406958] [7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406960*x + 2]
[7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406960*x + 2, 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406960*x + 1, x + 7010341668852982843614316960675681640167304511002256621666367190071164961421494972748197388083980317300271206633421191023419615687316572210806136425406958]
2
1
3
이제 여기에서 한 발 더 나아가서, 무작위로 생성한 식에 대해서 잘 구하는지 확인해보고자 했습니다. 이 때는 sage의 roots 메소드를 사용해서 실제로 잘 나오는지 서로 비교해보았습니다.
import random
def gcd_poly(f, g):
if g == 0:
return f
while f % g != 0:
f, g = g, f % g
return g
def solve_poly(f, p, x):
g = pow(x, p, f) - x
if g != 0:
f = gcd_poly(f, g)
queue = [f]
result = []
while queue:
f, queue = queue[0], queue[1:]
t = x - random.randint(0, p - 1)
t = pow(t, (p - 1) // 2, f) - 1
g = gcd_poly(f, t)
h = f // g
for t in [g, h]:
if t.degree() == 1:
result.append(t)
elif t.degree() > 1:
queue.append(t)
for f in result:
res = -int(f[0]) * inverse_mod(int(f[1]), p) % p
print(res, f(res))
p = random_prime(2^512-1,False,2^511)
F = GF(p)
PR.<x> = PolynomialRing(F)
for _ in range(10):
f = 0
for i in range(10):
f += x^i * random.randint(1, p - 1)
print("===========================================================")
print(f)
solve_poly(f, p, x)
print(f.roots())
결과는 다음과 같이 잘 나오는 것을 보실 수 있습니다.
===========================================================
1200264044203226801696929180798957982006209218858586485968057272931893198130487421196245236565708295955524063872832105983722642496036304807000771139835868*x^9 + 914263287180536604008388352346836647277343067125681869402388501638732260937609075067735394465771566491747235455554352145249545996085663788187840607080182*x^8 + 3230416859400717097409842100024678723655731572410585045361132703225506330014871418026907401514186081096764491942380015691051262665951035070909631328883984*x^7 + 42027776970286193965738840867681400228973328701162803906366908989692956287849300347151700319719886241904451854976130892959102573736568264892480831309978*x^6 + 6786896262380823869385560200877862278888694905520927387101984458822222420604347991924114266303937516274150392062919001917467470889321733827333091656873953*x^5 + 6940057861165892630655004018124411723823344085082801145768750659430433288982290936353693258550297460077262739992397952156902468205386644911586985395692022*x^4 + 6147608603948532380953204195492088712909288681433159197400772666756811852502881937085363927148570489616303596904071337121000049342606123194744567078032598*x^3 + 262081608539011211363524464053323426509658648017982707551715156159046818116122562390140525109908531720386754451573831684108701416136887997490554698826946*x^2 + 3339874277556227267009790979341254043102343666025225933109830122896746395272295237746365003162542961213241065227304071496361448279199613388295303056219470*x + 5140112101455419173558498120656406154542540047756193140891046282701629139287834417516130050033322885210986838756865577535891553752257268735024657762656668
3954065931870405447552131970914856261782623604959917319154200629277956473726750762380996790594274030438302040796596755128605639794188334684080057432774671 0
[(3954065931870405447552131970914856261782623604959917319154200629277956473726750762380996790594274030438302040796596755128605639794188334684080057432774671, 1)]
===========================================================
2543966872060270992845875491071781533612402826959862264606234445541444531362981399903286091267381612597490906459351463537198748529069746126553238150061039*x^9 + 3867008638530097001508337155054478702695661356374677652793523826293825440338682421958654076477194588776088573234584175033369330328622679986254589556100178*x^8 + 2979398969477863997647537407400697381543286701262573049536116469978049947126910313199214138967228998499678583096723719406773341648690406411450786145526680*x^7 + 9228944566237755943021548546413444224342464974204062757051615626174426585681845383598340506481051896145546852308824506970036464640740706749458884453710518*x^6 + 5254978984930049114798483061392983607656271088936340220164518903392868084258024964205027432336038230220820510315316550142645714779234429128567795122268296*x^5 + 8616046139677934977164498848753659052764030628228443230081525991008407395331248524167649323336300422437343763095142214298689921497213371236550688871126678*x^4 + 8254527439551310227250155585617377950965377005056930799855033080260737274734572279378104550514637717696684860711714559114061275433261742741764180886350200*x^3 + 3842054530009035932335438756551693075512885038807090910546691024266788132464411516732500756003077905077258590045191126720900954434405896094252317908044308*x^2 + 3817990544880013773266352110815312738956356582959936185675440747696630736173482990714279364419115913301071327074564812506490627729605750483065095841219710*x + 9469730781251249133829478005934811294974023186377122687036668248496153164405244348743790505025040588828072935741566431794028731303162634816206623080987894
7398754972849892015132902065852993334746593528360278131042649911574089608371659769067483609612579090914199717583008162682208764427829010672324159055120024 0
9346721734475437952597400910730703487508524189419186486146559176192917224406654603566790423101443484345634681837754422103607343175958279508248801741791878 0
8216850795214593256270259774770159117278358271109314818488356195607884805577865294100246386723465940018226742130724351798938977874981930830962788743138065 0
[(9346721734475437952597400910730703487508524189419186486146559176192917224406654603566790423101443484345634681837754422103607343175958279508248801741791878, 1), (8216850795214593256270259774770159117278358271109314818488356195607884805577865294100246386723465940018226742130724351798938977874981930830962788743138065, 1), (7398754972849892015132902065852993334746593528360278131042649911574089608371659769067483609612579090914199717583008162682208764427829010672324159055120024, 1)]
===========================================================
7914265698875247803642168071463144850714056100172272340512137539928433395342012377975843816393117490322081774917360649462938056415564026679339333426740310*x^9 + 678453396732591142618319476252558638216040867071242463939764060316327885598815687301633205123735494696967849438038452624245343260935544436317230730250467*x^8 + 6966439536215397414718340041719400246226290566747524890505414655779097230354603464893135704889692486617701352357059483204440282076155288459734987023427074*x^7 + 4696544723843869088313425942361650752082891039665807553249070403348225635589009106768059651923577185809753059696446327410229417203513445394139797881660268*x^6 + 740790225960893826891720079484003523332290566504896780635381462097919772029431280469838908817693496691255471294709252788492291909366464239896807619625320*x^5 + 10523315976449979151446646927761763995393643590634072970873329772914184960571711792860139287408820201266543938511673153056918525464484865981455559980269144*x^4 + 9031320116413613892725167538950473617527017162208054766915915186068621546059818175144447351825231503271380503849238060669395071899044343343717891626707704*x^3 + 8204630198757613511596729106589345877156294407225525254396497306525925107828421437182056489765155676231237215695785160008526336996462968708307100898804623*x^2 + 6372736855248520178771125308555755679686463056097065529245249645370117203040747238291412003613315589129177989493130307359470461122269445282403153176154170*x + 5194281929250170927042372072694792640606253043051912226638596477919029517527140139771000374828421429714961769553191848747872621041737299138052367883405682
7520548755493103055543221558105366612670386074725819862570906774656845810073524778988184470577323852655538294834821569003735772609990580493534483037031268 0
8633812048254565803676574072768634098394735988320800361386523207154514035973891608508765900899472585207381145754707133440064309979703555283349460356990864 0
4640621729811878086353502507279692300412200417073441847653471108133463934863980572653438935024690916979018912151177804489662312598349727788035203615051369 0
2156542012593046364430655592652735073390277532058326618785523287945442571720655612851775820122182082448260707992748818830070217604955099959706021494589669 0
[(8633812048254565803676574072768634098394735988320800361386523207154514035973891608508765900899472585207381145754707133440064309979703555283349460356990864, 1), (7520548755493103055543221558105366612670386074725819862570906774656845810073524778988184470577323852655538294834821569003735772609990580493534483037031268, 1), (4640621729811878086353502507279692300412200417073441847653471108133463934863980572653438935024690916979018912151177804489662312598349727788035203615051369, 1), (2156542012593046364430655592652735073390277532058326618785523287945442571720655612851775820122182082448260707992748818830070217604955099959706021494589669, 1)]
===========================================================
1904713715415335371469715741985941900930578283827250533910351029726751580571116806978834206092546974370073939286369178931152843282960293401473106605667525*x^9 + 2048507603065708495580780128896956299855524948364944660673580910919027157404762668041038462514834997846947043811532092533723053457600446084837593883639971*x^8 + 4237176805337612256656805189586916707208736935324172191176659505458778015867893562135149952981794963007915572680952392660180212380466119214968677044319479*x^7 + 3789972025498660810325922883192302303803288640777826150097664496894323636576580046113614744075677590752757774266483565826522929866896673074220250261990798*x^6 + 1889415098576910613685325275643342020900495764691745083807292275787627654256019686472540711858434293900450932300108139384014062560194720106223569051652552*x^5 + 5606746252937083574755282191740545669642164657057079806943552624202640190777264466678969139773707273213881762204043112204011513348634675974605084358008421*x^4 + 4798827425708863006004873671176008289503761834927239218396741028334025136850251073530269855814859035773692905632292694370490107931599730689741666305104960*x^3 + 10479355482563130429375016695364792532413366093927449834550583569411267609325186117514491931091311250625158044868721169923356882974407726477501389067592201*x^2 + 5301499146036044644362407086221923571632095868101006514671984960589222887068308530867248380899422430664907532178295757641197102724657655256723971794646190*x + 4529877044113012885707137166691346112579151500945294649564317052190351844843556908087160372292972085037336521942462617429533873335151258885772573900035910
[]
===========================================================
8282112416886144508395200124654766025141837984656401033050621347036857936750549424246913754824167015612481231714630071337501655373669002718642952601708075*x^9 + 83153289475357780855669895154315721643155964444087940649343329821349284446498476565095530890953499683532017057877879164739442100368148070737776495318332*x^8 + 6040553206751915175440468312028283777193215099307110016785983720219316777319004912726794765526857599437521174505026245653627459067178568662241007352119200*x^7 + 7654189215934682911328438347108783426624319500346283590966358523222498849907801669092386395505345993565956825860461337527406156733369831115403237167925907*x^6 + 4945971405702579112599251416631691347269580986718133149583334686066170413615561526582499843398136148916348146707986734381073923288870768458497234504729425*x^5 + 7658353290773491596032407383661055097109154078415354772761792939783176010679008312411978829039764074289522690776166813921190632280506380536612550560516140*x^4 + 1698741740588519070105865527248312801542850369873975862371363139738571112908323878683221069580605619193230918928327571030096866032583766768921974479866831*x^3 + 6166757774215476818417929916073144206949602021398070201900750467804023367397403304178977643416370496490005247981278702331216380057055068358387471770746293*x^2 + 8786714816229003089999719639086359659915021943604360195358566905951058123082528453084068393020638590396102702612556569642694536668200505029597647122121401*x + 1112950348949891808453002714859275885594133672234467921356258189530600515831084601641304495753050729797393404263054551758956031818923479436678496695194471
2921248940056530679704354603422052517442670085374225352987577001594148164328244609722221806328606428490995170929736569622728937440697613351999198544579667 0
[(2921248940056530679704354603422052517442670085374225352987577001594148164328244609722221806328606428490995170929736569622728937440697613351999198544579667, 1)]
===========================================================
518236739987144779388640178675289390574638196699625338002564424870793755906896523707022489706368375789898721972281365991258368318623789336021980780457035*x^9 + 4372656574591151968142346012789178113893725952830257393352936183042188117101860382424004276505589122658604625549890057947417827448933902754850968233203046*x^8 + 4842035366984019130102139548608080760027066085518908589678764003845202871598579978784571277908184741476245846085869290145261720473126054561274443395812939*x^7 + 5873466384956558613953507691593609513175173072627380530137255424592264659184382552155110978121998890801353942961071348947279080422373053313457370408581511*x^6 + 7573030384702580070587502045129791238011248596535457038373437732154016365253717269685185767602751007967927404007462051410238521603249985864138291043753488*x^5 + 1949219487839794173908614668739331130532220877717128931625792805734167523581873375337112643208491044477771026709888197215152147704988641862996487521084343*x^4 + 4321212240525864685138558271388959157841513062828236303345187083799297285618054499775202482253150830969481586358615849421905048664581415660266035430279823*x^3 + 6896634781254924491165527391638641541268233787320700986079861171419066170788923011596011943982254931076758658167343751186756810994246915685775226424125538*x^2 + 10594898771419754551739969701804465218770736926799896940379044690625309828678240712888871508945925294878586412453460693917516557250366525449850117366584173*x + 10199013750440434433980400437748646963143621279424275632698868061976769013837607626283938527420921823037939391603924692660441774229177364187730607425155976
[]
===========================================================
1266955788455048206512343046473368282552999116694349221951031922683015835951774383324308014327000615455695682070589687189894014677538768139476549608830146*x^9 + 8504245882296495320797777271471790198384855431217631336381703043323927906607439991884310111415976638847244641326289329744367985981402303826540918400414206*x^8 + 1223788976072651320128611791233318219802746477766236664829929795160335484974058618400699890074640708299486575835601746120758765856850687767880052797059729*x^7 + 342145786653613544667737489463662594131271577351720504785914006291372922916479174257639848945417574623914364935900689282220612055378133757673144503334223*x^6 + 231354253348581982460163476013405091381397707895018080772933243948173400311861281105055929654877949772548641064602487770737824937002631754842988072428928*x^5 + 6977861175293714771318569669596960047956318102483941363424610338151689525015326150812423430533074243403175743988740502002847487564073726534835466830744925*x^4 + 6299731989936589762732648595967850297745979373576046118268554479575279626130768946784708323675717579870875521582029350806826779923463854653480224177164585*x^3 + 6768061838432473189601436387728942483247943057789102209752377368930151084506322834050175558476295175220288662124121162546264833549676282657754106350758054*x^2 + 7277434078479216708897288332653652261466209852833278328121718173598614368444777766614275811116637276358728934524058551067343023563978139035100557312539180*x + 2683632310847337161090999550521266396077671338546077529845355818293443104176112844233487619823449132697603047353552340028922923212010878813132186023381293
5595886057160520736406945690161505044736606764820393394299755139021957388067889322540467248107222945626267704864593736537310339934410660083723816307835390 0
565501365398381724860037134374842022392034037653612258634632385082298759489654769598269346585754200785896939217574811466427030872938645845808009388061772 0
[(5595886057160520736406945690161505044736606764820393394299755139021957388067889322540467248107222945626267704864593736537310339934410660083723816307835390, 1), (565501365398381724860037134374842022392034037653612258634632385082298759489654769598269346585754200785896939217574811466427030872938645845808009388061772, 1)]
===========================================================
1076275542766846889954095884026163605559574449810037858411754121384334123901234330223209416495519979136769566236931765692693673186830920755266821846096696*x^9 + 4633984000132851917187122820170036362531836496596934860410781013129907175467413416029095533505203242069464968515590857565221181307593914453258981754428392*x^8 + 336603796050192933467524978402033721787132085260590071257934140172081414896528544752960441453416283162173988833659428893027434545728794249192156700890748*x^7 + 6469327015995602914420270728199580338406726487328939543238664635762345750798551458347813475336720928166352183144258066090134764275509862276285781731702497*x^6 + 9950802185340274152604937240732664100599806455515923034523079323849773522275782769212793653248149616518115644529965871312522666514894729873245708668383869*x^5 + 2867259191466210193185027193545461537035239545389253057271599867107009458483879574946258391886156107803452804183870753407909561151757658583526408493319143*x^4 + 7598456629617947778721052458664226861380337279498857890853685758971049423684855829362108739113681046599380373029023495179431134855797890590366642179456130*x^3 + 10105573251204277909402229379160886416960028834895370118813191053871308853507238295649850183052624254994378255520849779782353971204748727744209871268285801*x^2 + 10386176782027740953271655777716332610409398891939951312689091650025295985917714208206868864059044822596111262378128223077297315014634488710001858314290470*x + 9341920183899603102825732086093986335153602697728264931685101695775073672291882621861474200327032607514412250043363668350614966492350527979487405407580755
5004602855869194638936600631280967512786936771956452125400313608487406890177751478697855927132757415603131701550709567632194519919343317273140201972941715 0
[(5004602855869194638936600631280967512786936771956452125400313608487406890177751478697855927132757415603131701550709567632194519919343317273140201972941715, 1)]
===========================================================
9443142832900881568885231868929471571261014696814680308994996627093268694379533767693284836404521206015372181319214640774294566699358668496437500190845025*x^9 + 1574262969438931868528418813692904658451192207484341582112609582162744253924301676040371049871504347028965532294554760205141271488774849581595842615168824*x^8 + 4172235667733681596697237215712655021819149214287052585195075829946180395135503767060656004027570712991485463883098358350264441335726776759578777881650173*x^7 + 2991562774924834997806297071463687819495059970686245945257744988741469635885173974688169146571743930047846097248185312729854563528991794752325043864291757*x^6 + 2250039470884249445616768758964259741878707775701270782786041884511802977496969553307322506763237429288795251129570578205854902664724014355082398222364071*x^5 + 10200943218934030807297267551189390513387846246288701394376469637668997843227988692426729866811642700028009734518488697193089463879622815456422629216666528*x^4 + 8531149596554932064935689511477743512221463290073570425170218633157994408730453977588759262219146901290908079464947740168529643573838146730624888645091733*x^3 + 456404960707954647697076390614508121682201557337890387189180008469661436657780929969505751604555787108115478119935799116801213909077331836216801728790970*x^2 + 148692308130615381835190947816563241240550527195833437091799668627059816758904524487971692279557552838628099338818487305813595268402020032551830740512776*x + 6780803446634137846040165453519582537276171474499862755765245767054189131946487741272596604119759854303503578436441429103832317176993777725004851360256972
5902906994452943886554671009107026139327182468030527833144748516045138394260504144097485123441511655543481320357510316381298834994699227421570304268063533 0
[(5902906994452943886554671009107026139327182468030527833144748516045138394260504144097485123441511655543481320357510316381298834994699227421570304268063533, 1)]
===========================================================
10001121504206983994608312286030719506728442389921726944921239028888323699124808500783064481620126647687972042050068275295111828442276461393678310342450523*x^9 + 4098303336999735583989183539240365843634260823132476986801143981382446849563707682215303689518698456697873227341655722636330683363311258585494738130162633*x^8 + 10624312814557168635938557381773256095142038155353640621060778111612743445073768532871158836089624562200014908682960735743067699649077439992849740603014465*x^7 + 1441457211460859347586104646067093645425240272214656297408988133405825427831043533393240864228188590901773407871756121311781788696458061708460364514069440*x^6 + 6449201578725819433910629872802402446064716276563318131857014290770180005188959850952993500189243724573658814641369660624148158564149353687586027915414107*x^5 + 10215311370031125778661916847615772995816765506417724645271787685628088462262324346242072010533852072532687412905311310530504341634665270813441899853316966*x^4 + 584110424653607675728213843888348452551238748910927656110563349375916951661907886599655909265385054626688374749723286252931308983994301527148241598574041*x^3 + 9004203702957729715716876871307991005545397517492604963184257698619664551277409872047324592367829861254601014429712932766222848356252785069979256097817730*x^2 + 2369114728650831226239916398891109805017131112014904560210127061017910031998962487426828615173677174874624919746399760820940041367829069582115868948757276*x + 2603439009285414316113842391486772426617590504681009107350149773403238956222440431526099170836595740405471861068520716755255827584874703338978843708797540
7740343181509951126368907503704141568539029972642852736174508150837246643083999987852140050737491058395672043794094553917514124686102703335682161593012069 0
[(7740343181509951126368907503704141568539029972642852736174508150837246643083999987852140050737491058395672043794094553917514124686102703335682161593012069, 1)]
결론
이번 기회에 finite field 위에서 univariate polynomial을 푸는 것이 생각보다 어렵지 않은 과정이라는 것을 배울 수 있었습니다. 이에 대해서 귀띔해주신 노규민 님에게 다시 한 번 감사의 말씀을 드립니다.
참고 문헌
- Univariate polynomial factorization over finite fields https://www.sciencedirect.com/science/article/pii/S0304397597800011
- Cantor–Zassenhaus algorithm https://en.m.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm