CoCalc Public FilesFinite Rings and Fields / polyRSA.sagews
Authors: Jesus Jimenez, michelle freed
Views : 35
Description: 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$
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$]