Question $4.$ Decrypt Bob's response e$3.$

Let $R=Z\frac{x}{x^N-1}$ where $N>1.$ Remember, in this ring, we work

modulo the polynomial $x^N-1,$ or equivalently, with the relation that $x^N=$

For $p>1$ any modulus $($not necessarily prime$),$ we denote by $R_p=$

$(\frac{Z}{p}Z)\frac{x}{x^N-1},$ so in other words, we reduce the coefficients modulo

$p,$ and keep the same relation on $x.$ We do not assume $p,q$ are prime below

unless otherwise stated. Finally, we let $T(d,e)$ denotes the set of $f(x)inR$

which have $d$ coefficients equal to $+1,e$ coefficients equal to $-1,$ and the re$-$

maining coefficients are equal to $0.$ As an example, $x^3+x-\frac{1}{i}nT(2,1)$ when

$N4,$ and $-x^5+x^2+x+\frac{1}{i}nT(3,1)$ for $N6.$

def encode$($s$)$:

s $=$ str$($s$)$

if len$($s$)>71$:

print$(\text{'}$Error$,$ string too long.$\text{'})$

return $0$

return sum$($ord$($s$[$i$])*(128**$ i$)$ for i in range$($len$($s$)))$

def decode$($n$)$:

n $=$ int$($n$)$

v $=[]$

while n $!=0$:

v$.$append$($chr$($n $\%128))$

n $//=128$

return $\text{'}\text{'}.$join$($v$)$

q $=2227931092922619159088137825860917778654908962259364260724799634482871993679344024477214037820250089114550582112658547035427887568025339234287716719310475274676925427488455341264359399933469547884104546673995772201433027461094946187102932478528326005620630416132860562672779096576947422455142739470761$

f $=626346493922296891962453123852828762226840739369641575566811218944994465423391699556882442728756781708398121951194799184723646669035568862933089972532$

g $=977000403491994460922837866629768065514748480840502199588478427171542192931318741506250139746005024832848394512867819725451407771971457631489150320807$

h $=$ mod$($f$,$q$)^(-1)*$mod$($g$,$q$)$

e $=78718410001068529677588572614497505845736983903998613145157719609579915026054651042742971468860259386790104756141288441579114641145660779208031511331352898518118466155496980362017676866087191935146013866713673612565156506113920877930874410944039265560871107404980288749922814814885918909569495979623042532040822272019812413569842170256723818746065909730713382503129868557825346347038766126043524590160376367091553994881762361291104351498414443598243$

e$3=1483322386654454587495018401466856358270021160509001725744622618980646039957815384765921577945979388255939805665289064215370310789868218779822555861806994459095498038225083313865694507736240943443495754222854085327209824275075557181208838536828375329242566221950127047314388792614649773136280238755453$

##### EXAMPLE CODE FOR GAUSSIAN LATTICE BASIS REDUCTION ########

# In this code I will reduce the lattice

# L $=\{$ k$(1,$h$2)+$ l$(1,$q$2)$ : k$,$l in Z $\}$

# It is important call h$2$ an Integer so that

# Sage does not do modular arithmetic here

v$1=$ vector