Question $3.$ Bob's public key is $q_2,h_2($given in Sage as q$2,$h$2).$ Alice has

sent Bob a message encrypted as e$2.$ Recall that we discussed in lecture that

if we can find integers $RF*(1,h_2)-R*(0,q_2)=(F,G)(f_2,g_2)=(F,G)(F,G)L=Z(1,h_2)+Z(0,q_2)(1,h_2)(0,q_2)q_2(F,G)\sqrt[\phantom{2}]{q_2}$$$7\mathrm{.}12(F,G)L=Z(1,h_2)+Z(0,q_2)e20$ and $R$ satisfying

$F*(1,h_2)-R*(0,q_2)=(F,G)$

then $we$ will $be$ likely $to$ have recovered Bob's private key $in$ the form $(f_2,g_2)=$

$(F,G).$ The vector $(F,G)$ lies $in$ the lattice $L=Z(1,h_2)+Z(0,q_2),$ and $aswe$

mentioned $in$ lecture, $itis$ a short vector relative $to$ the basis vectors $(1,h_2)$

and $(0,q_2),$ both $of$ which have length roughly $q_2,$ whereas $(F,G)$ will have

length $on$ the order $of\sqrt[\phantom{2}]{q_2}.$ Implement Gauss' method $of$ lattice reduction

from lecture $(see$ also $$7\mathrm{.}12in$ the textbook, and the helpful Sage code $in$

$hw9-$data.$txt)to$ find the smallest vector $(F,G)in$ the lattice $L=Z(1,h_2)+$

$Z(0,q_2)$ and find Bob's private key. Use this $to$ decrypt the message $e2$ that

Alice has sent $to$ Bob.

def encode$($s$)$:

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

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

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

return

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

def decode$($n$)$:

n $=$ Integer$($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$

q