SharedFinite Rings and Fields / polyRSA.sagewsOpen in CoCalc
RSA polynomial
R = PolynomialRing(GF(2),'x') # GF(2) is the field Z mod 2 and R is the polynomial ring F_2[x].
x = R.gen()
%typeset_mode True
p = x^5+x^3+1
q = x^3+x+1
e=101
n=p*q
S = R.quotient(n, 'a')
a = S.gen()
p
q
expand(n)
x5+x3+1\displaystyle x^{5} + x^{3} + 1
x3+x+1\displaystyle x^{3} + x + 1
x8+x5+x4+x+1\displaystyle x^{8} + x^{5} + x^{4} + x + 1

fiOfN=(2^5-1)*(2^3-1)
fiOfN
217\displaystyle 217
M=0*a^11+0*a^10+1*a^9+0*a^8+1*a^7+0*a^6+0*a^5+1*a^4+1*a^3+1*a^2+0*a^1+0*a^0
M
a7+a6+a5+a4+a3+a\displaystyle a^{7} + a^{6} + a^{5} + a^{4} + a^{3} + a
eM=M^e
eM

a7+a6+a5+a2+a\displaystyle a^{7} + a^{6} + a^{5} + a^{2} + a
d,u,v=xgcd(fiOfN,e)
v
58\displaystyle -58
dM=eM^(v+fiOfN)
dM
M
a7+a6+a5+a4+a3+a\displaystyle a^{7} + a^{6} + a^{5} + a^{4} + a^{3} + a
a7+a6+a5+a4+a3+a\displaystyle a^{7} + a^{6} + a^{5} + a^{4} + a^{3} + a
numM=16346
lM=numM.digits(2)
lM
[0\displaystyle 0, 1\displaystyle 1, 0\displaystyle 0, 1\displaystyle 1, 1\displaystyle 1, 0\displaystyle 0, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1]
c=lM[0]
for i in range(len(lM)):
    c=c+lM[i]*a^i
print(c)
a^13 + a^12 + a^11 + a^10 + a^9 + a^8 + a^7 + a^6 + a^4 + a^3 + a
mYES=c
mYES
a13+a12+a11+a10+a9+a8+a7+a6+a4+a3+a\displaystyle a^{13} + a^{12} + a^{11} + a^{10} + a^{9} + a^{8} + a^{7} + a^{6} + a^{4} + a^{3} + a
enc=mYES^e
enc
a602+a599+a598+a597+a595+a594+a593+a590+a589+a586+a584+a582+a581+a580+a579+a577+a575+a572+a568+a567+a559+a556+a555+a554+a552+a549+a548+a545+a539+a535+a533+a532+a530+a527+a526+a525+a524+a522+a521+a519+a515+a514+a513+a512+a510+a508+a507+a505+a503+a502+a501+a500+a499+a498+a493+a491+a490+a488+a487+a484+a480+a478+a476+a473+a470+a467+a466+a465+a463+a460+a458+a457+a455+a452+a451+a450+a449+a447+a446+a444+a443+a442+a441+a440+a438+a437+a436+a435+a434+a429+a427+a426+a424+a422+a419+a416+a413+a409+a407+a404+a403+a398+a397+a395+a394+a393+a391+a390+a387+a384+a381+a380+a379+a377+a375+a369+a365+a364+a362+a361+a360+a359+a350+a349+a348+a347+a342+a337+a336+a335+a334+a333+a332+a331+a326+a324+a322+a321+a320+a319+a318+a317+a314+a312+a311+a310+a309+a308+a307+a306+a305+a300+a299+a297+a292+a288+a285+a282+a281+a275+a273+a270+a266+a265+a263+a262+a260+a258+a257+a256+a255+a254+a253+a250+a248+a247+a246+a245+a244+a243+a242+a241+a236+a235+a233+a228+a224+a221+a219+a217+a211+a210+a208+a206+a205+a203+a202+a201+a199+a198+a195+a192+a189+a188+a187+a185+a183+a177+a173+a172+a170+a169+a168+a167+a158+a157+a156+a155+a150+a145+a144+a143+a142+a141+a140+a139+a134+a132+a130+a129+a128+a127+a126+a125+a122+a120+a119+a118+a117+a116+a115+a114+a113+a108+a107+a105+a102+a100+a98+a97+a92+a87+a84+a77+a76+a73+a71+a70+a69+a68+a65+a61+a60+a57+a54+a53+a51+a49+a48+a46+a45+a44+a41+a40+a36+a35+a33+a30+a28+a25+a23+a22+a16+a13+a12+a11+a9+a8+a6+a4+a+1\displaystyle a^{602} + a^{599} + a^{598} + a^{597} + a^{595} + a^{594} + a^{593} + a^{590} + a^{589} + a^{586} + a^{584} + a^{582} + a^{581} + a^{580} + a^{579} + a^{577} + a^{575} + a^{572} + a^{568} + a^{567} + a^{559} + a^{556} + a^{555} + a^{554} + a^{552} + a^{549} + a^{548} + a^{545} + a^{539} + a^{535} + a^{533} + a^{532} + a^{530} + a^{527} + a^{526} + a^{525} + a^{524} + a^{522} + a^{521} + a^{519} + a^{515} + a^{514} + a^{513} + a^{512} + a^{510} + a^{508} + a^{507} + a^{505} + a^{503} + a^{502} + a^{501} + a^{500} + a^{499} + a^{498} + a^{493} + a^{491} + a^{490} + a^{488} + a^{487} + a^{484} + a^{480} + a^{478} + a^{476} + a^{473} + a^{470} + a^{467} + a^{466} + a^{465} + a^{463} + a^{460} + a^{458} + a^{457} + a^{455} + a^{452} + a^{451} + a^{450} + a^{449} + a^{447} + a^{446} + a^{444} + a^{443} + a^{442} + a^{441} + a^{440} + a^{438} + a^{437} + a^{436} + a^{435} + a^{434} + a^{429} + a^{427} + a^{426} + a^{424} + a^{422} + a^{419} + a^{416} + a^{413} + a^{409} + a^{407} + a^{404} + a^{403} + a^{398} + a^{397} + a^{395} + a^{394} + a^{393} + a^{391} + a^{390} + a^{387} + a^{384} + a^{381} + a^{380} + a^{379} + a^{377} + a^{375} + a^{369} + a^{365} + a^{364} + a^{362} + a^{361} + a^{360} + a^{359} + a^{350} + a^{349} + a^{348} + a^{347} + a^{342} + a^{337} + a^{336} + a^{335} + a^{334} + a^{333} + a^{332} + a^{331} + a^{326} + a^{324} + a^{322} + a^{321} + a^{320} + a^{319} + a^{318} + a^{317} + a^{314} + a^{312} + a^{311} + a^{310} + a^{309} + a^{308} + a^{307} + a^{306} + a^{305} + a^{300} + a^{299} + a^{297} + a^{292} + a^{288} + a^{285} + a^{282} + a^{281} + a^{275} + a^{273} + a^{270} + a^{266} + a^{265} + a^{263} + a^{262} + a^{260} + a^{258} + a^{257} + a^{256} + a^{255} + a^{254} + a^{253} + a^{250} + a^{248} + a^{247} + a^{246} + a^{245} + a^{244} + a^{243} + a^{242} + a^{241} + a^{236} + a^{235} + a^{233} + a^{228} + a^{224} + a^{221} + a^{219} + a^{217} + a^{211} + a^{210} + a^{208} + a^{206} + a^{205} + a^{203} + a^{202} + a^{201} + a^{199} + a^{198} + a^{195} + a^{192} + a^{189} + a^{188} + a^{187} + a^{185} + a^{183} + a^{177} + a^{173} + a^{172} + a^{170} + a^{169} + a^{168} + a^{167} + a^{158} + a^{157} + a^{156} + a^{155} + a^{150} + a^{145} + a^{144} + a^{143} + a^{142} + a^{141} + a^{140} + a^{139} + a^{134} + a^{132} + a^{130} + a^{129} + a^{128} + a^{127} + a^{126} + a^{125} + a^{122} + a^{120} + a^{119} + a^{118} + a^{117} + a^{116} + a^{115} + a^{114} + a^{113} + a^{108} + a^{107} + a^{105} + a^{102} + a^{100} + a^{98} + a^{97} + a^{92} + a^{87} + a^{84} + a^{77} + a^{76} + a^{73} + a^{71} + a^{70} + a^{69} + a^{68} + a^{65} + a^{61} + a^{60} + a^{57} + a^{54} + a^{53} + a^{51} + a^{49} + a^{48} + a^{46} + a^{45} + a^{44} + a^{41} + a^{40} + a^{36} + a^{35} + a^{33} + a^{30} + a^{28} + a^{25} + a^{23} + a^{22} + a^{16} + a^{13} + a^{12} + a^{11} + a^{9} + a^{8} + a^{6} + a^{4} + a + 1
enc^(v+fiOfN)
a13+a12+a11+a10+a9+a8+a7+a6+a4+a3+a\displaystyle a^{13} + a^{12} + a^{11} + a^{10} + a^{9} + a^{8} + a^{7} + a^{6} + a^{4} + a^{3} + a
a^fiOfN
1\displaystyle 1