modular-binomials.md

Notice that $(ap + bq)^e = \binom{e}{0} (ap)^0 (bq)^e + \binom{e}{1} (ap)^1 (bq)^{e-1} + \ldots + \binom{e}{e-1} (ap)^{e-1} (bq)^1 + \binom{e}{e} (ap)^e (bq)^0$ by the Binomial Theorem, so all terms cancel out except for the first and last one similarly to the Freshman's Dream (although in this case the terms in the binomial are doing the canceling, not the binomial coefficients as in the Freshman's Dream theorem).

So $c_1 = (2p)^{e_1} + (3q)^{e_1} \pmod{N}$, and this applies similarly for $c_2$.

Now we can't directly combine the equations because they have different exponents on the terms. However, we can raise $c_1$ to the power of $e_2$ and vice versa to make the exponents on both equations $e_1e_2$.

Then, we can simply multiply $c_1$ by a modular inverse so that the coefficients of the $q$ terms in $c_1$ and $c_2$ are the same and then subtract and use another inverse to get $p^{e_1e_2}$.

Finally, since $p$ is present in both $p^{e_1e_2} \pmod{N}$ and $N = pq$ and the exponent of $p$ in $N$ is just $1$, we can just take the GCD of $p^{e_1e_2}$ and $N$ to get $p$. Then we can just divide $N$ by $p$ to get $q$.

Here's the code I wrote for this:

from math import gcd
N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

c1 = pow(c1, e2, N)
c2 = pow(c2, e1, N)

# c1 = (2*p)**(e1*e2) + (3*q)**(e1*e2) mod N
# c2 = (5*p)**(e1*e2) + (7*q)**(e1*e2) mod N
mul = pow(pow(3, -1, N) * 7, e1*e2, N)
c1 *= mul
pe = (c2 - c1) * pow(mul, -1, N)  * pow(pow(2, -1, N), e1*e2, N) # p**(e1*e2) mod N
p = gcd(pe, N)
q = N // p 
print(f"{p = }")
print(f"{q = }")