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)

$\displaystyle x^{5} + x^{3} + 1$
$\displaystyle x^{3} + x + 1$
$\displaystyle x^{8} + x^{5} + x^{4} + x + 1$
$\displaystyle x^{3} + x + 1$
$\displaystyle x^{8} + x^{5} + x^{4} + x + 1$
fiOfN=(2^5-1)*(2^3-1)
fiOfN

$\displaystyle 217$
M=1*a^7+(0*a^6)+(0*a^5)+(0*a^4)+(1*a^3)+(1*a^2)+(0*(a^1))+(1*(a^0))
M

$\displaystyle a^{6} + a^{3} + a^{2} + 1$
eM=M^e
eM


$\displaystyle a^{7} + a^{6} + a^{4} + a^{2} + a$
d,u,v=xgcd(fiOfN,e)
v

$\displaystyle -58$
dM=eM^(v+fiOfN)
dM
M

$\displaystyle a^{6} + a^{3} + a^{2} + 1$
$\displaystyle a^{6} + a^{3} + a^{2} + 1$
numM=16346

lM=numM.digits(2)
lM

[$\displaystyle 0$, $\displaystyle 1$, $\displaystyle 0$, $\displaystyle 1$, $\displaystyle 1$, $\displaystyle 0$, $\displaystyle 1$, $\displaystyle 1$, $\displaystyle 1$, $\displaystyle 1$, $\displaystyle 1$, $\displaystyle 1$, $\displaystyle 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

$\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

$\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)

$\displaystyle a^{13} + a^{12} + a^{11} + a^{10} + a^{9} + a^{8} + a^{7} + a^{6} + a^{4} + a^{3} + a$
a^fiOfN

$\displaystyle 1$