polyRSA.sagews

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$

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^{7} + a^{3} + a^{2} + 1$

eM=M^e
eM

$\displaystyle a^{7} + a^{5} + a^{2}$

d,u,v=xgcd(fiOfN,e)
v

$\displaystyle -58$

dM=eM^(v+fiOfN)
dM
M

$\displaystyle a^{7} + a^{3} + a^{2} + 1$

$\displaystyle a^{7} + 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^6 + a^2 + a + 1

mYES=c
mYES

$\displaystyle a^{6} + a^{2} + a + 1$

enc=mYES^e
enc

$\displaystyle a^{7} + a$

enc^(v+fiOfN)

$\displaystyle a^{6} + a^{2} + a + 1$

a^fiOfN

$\displaystyle 1$

C = c.lift()

C

$\displaystyle x^{6} + x^{2} + x + 1$

C.coefficients(sparse=False)

[$\displaystyle 1$, $\displaystyle 1$, $\displaystyle 1$, $\displaystyle 0$, $\displaystyle 0$, $\displaystyle 0$, $\displaystyle 1$]