0
$\begingroup$

I need the gcd of two polynomials,

pol2 = 96282968693199378612620657496531395238062854267416785769892810279581114080886331694029430818620691344975031*x^20 + 49724244652126958463052030288606098491675196767447384169499844060229072636921770492157673134942311588983700*x^19 + 99925851504102267917936523001683527097256147290115954427464066098384650582929354903387348743199493089583591*x^18 + 44637808644667939776632890954594781591364385577657273239488479857280193632735804116541218214220655799087878*x^17 + 37241674745583430286444331690048638507172367337331687512683030840146074437700928913272852684572117713709425*x^16 + 3401852462908679628484998036474510600452064756695644696971258738094014633067354656071803281968956376835073*x^15 + 93479598911461415675632416366093709981985170461356865125975084700683170408266004012345678920508327696426721*x^14 + 58445961978282241491382218316271776559850115693526701684006095006236329770645431995697872671678894389367347*x^13 + 7740445054400030630179580354335889323963233238574035376923674694851212532508346011454083834061864035423505*x^12 + 39951817357934807606522019485064289032263139743346444901688397675617488528704326960326063650829578316982358*x^11 + 95518650748905516824711294616070160160408765643814857614995964357696925717363843904870255880003368893739626*x^10 + 33840830296791685244991091974048562008281820720047391410046609176611147568632212710306695691757446399359326*x^9 + 67575476495664320492605955802527533498363583026454910904889627165651870160439587173466656289655008131991628*x^8 + 94767680247812960532591623372545498848145915526305265393910624080821923821312491404886351604670007336919229*x^7 + 17128287737294033506216971743714672592340474862251842767736279732636013393300176185985359911937597423991781*x^6 + 71058236810239615009802169953347382955195284068061748586259495318824688171425585233324788676814098042780618*x^5 + 78009736557879383158962846791320985630962899074214342149779356497892765893798764343254215797964608867779233*x^4 + 42031788223871165450733861840401273643239533206445063251621372446481599583043741911683904618918804268222746*x^3 + 64197674987684118435293124478457577684195224137725264152258081642643853658232811226240437662261688519681660*x^2 + 52002351299374656375907942415544129315495063265014164845948777368801196697388549548459288453739497121899799*x + 103083623103444976305109679628810718701595361758309293600367245461722916099625332442144506094890679521744403
pol3 = 29713774661318425150937452414500521557610124208545026290216258423888330013328697089106011620711069798173115*x^18 + 84641590273263050356751947874343000634049706471406163401163977389467416147484369772169947742593138259567019*x^17 + 69384036233543933852317705273266420209467758339018551394439169979699111506818737815446302313531312858358125*x^16 + 45409048572120624405621695947663268386151245933838909713336695778078934429966161780473206621866755650639813*x^15 + 107832327881680039007761773485633484147184967687056775539077737395563134422121480515027411797013554787913224*x^14 + 83582254119577830795660383075600228391262661217022668517112888741823410356267289961803829147693873522581230*x^13 + 108909346047151447466887497688675948996028867618436487289380506938667263925971498721805269446592018491780876*x^12 + 57371516075539333017878221585964157852948599292830418819912406167688280126371151723817437358536811493185547*x^11 + 88891978752112066866734608133858844283673215149475905600648279864562232489283464416056934091094512563734859*x^10 + 81059990063522360269727474528848207590923107633022077156950668718799183563173536744699078891393724092983397*x^9 + 114130406457462429467691026095868751204387196011186952575629164407101231782805065288804070632220800458469708*x^8 + 12932592696654539692060532336072132425419003322545027366197030287215817319291806315646993183241833004974525*x^7 + 66739688094094535415388670829742869616263082422739457073139191757534428110718537986610069429327972391515320*x^6 + 25198443688790938784689243819703187276854082041645468584901519427317041101043293299450661466467674270493378*x^5 + 94108231475417739360083689508058432664574876948398654906352666194933573357607556385939805580816399948491101*x^4 + 86556041747261425472921683887381176923795387332162955489352894566838591459423158505865821787508998341971081*x^3 + 90617953691432195378722748955669887726761048669260390402218412961955109931608473947995423679056169983359132*x^2 + 82200250932203010128485336947232599251959861407787419841852755411192383982435970294982197287395144238097400*x + 23238588036534921821044385086167776956215864833084299345498541413163307323240985898060959204826534308718935

... with a composite modulus

N = 115562352485561032060492039891121716550780298338103887552727636854507966397297661571103692796981504393840901

Unfortunately, I don't have a strong mathematical background.

Improve this question
$\endgroup$
5
  • $\begingroup$ To save time FactorInteger returns these factors of the modulus: {{659, 1}, {29184719, 1}, {341947687, 1}, {198940026730323544152757, 1}, {88327024610313770734311025569662465584663773142386571916825483059, 1}} $\endgroup$
    – flinty
    Feb 9 at 11:22
  • $\begingroup$ ok now that I have the factors how do i plug them in the polynomialGCD? $\endgroup$
    – PorkyPhoenix091
    Feb 9 at 12:02
  • $\begingroup$ because it gives me this error PolynomialExtendedGCD::modp: Value of option Modulus -> {{659,1},{29184719,1},{341947687,1},{198940026730323544152757,1},{88327024610313770734311025569662465584663773142386571916825483059,1}} should be a prime number or zero. $\endgroup$
    – PorkyPhoenix091
    Feb 9 at 12:04
  • $\begingroup$ You can use this answer to compute the GCD now you have those factors. cfs[p1_, p2_, x_, p_] := Reverse[CoefficientList[PolynomialGCD[p1, p2, Modulus -> p], x, 1 + Min[Exponent[p1, x], Exponent[p2, x]]]] FromDigits[ChineseRemainder[Transpose[ cfs[pol2, pol3, x, #[[1]]] & /@ factors], factors[[All, 1]]], x] We get g = 5580663105752620685954134285372965836116627561909658592478114145306084 4190655478639845159974034843623875040 + x and you can verify: Mod[pol2 /. x -> (x - g), n] and Mod[pol3 /. x -> (x - g), n] are 0. $\endgroup$
    – flinty
    Feb 9 at 12:32
  • $\begingroup$ So the answer is 5580663105752620685954134285372965836116627561909658592478114145306084 4190655478639845159974034843623875040 + x $\endgroup$
    – flinty
    Feb 9 at 12:32

0

Reset to default