Question $2.$ Let $L$ be the lattice generated by the basis

$B=\{(3,1,-2),(1,-3,5),(4,2,1)\}.$

Which of the following sets are also bases for the same lattice $L?$

$(1)B_1=\{(5,13,-13),(0,-4,2),(-7,-13,18)\}$

$(2)B_2=\{(4,-2,3),(6,6,-6),(-2,-4,7)\}$

Prove your answer for each. If the basis generates the same lattice, find the

change of basis matrix A such that the matrix $B$ whose columns are the

vectors of $B($in order$)$ and matrix $B_i$ the matrix with columns given by $B_i,$

then $B=B_{i}A.$ In this case, compute the Hadamard constants of each basis,

and determine which is the better basis for $L.$

Alice and Bob use the GGH cryptosystem to communicate. Alice's private

key, the dimension $n,$ the matrix of column vectors $V=([v_1,v_2,$cdots,$v_n]),$ and

public key $W=VE$ where $E$ is a matrix of elementary column operations, is

given in the file hw$10-$data.txt$.$ Encoding and decoding functions, encode

and decode, are also given. Bob sends Alice an encrypted message e given by

$e=Wm+r$

where $m$ is the vector correspoding to the encoded message. Notice that since

$W$ is also a basis for $L,$ and $min{Z}^n,$ the vector WminL$=Z{v}_1+$cdots$+Z{v}_n.$

####################### FUNCTIONS #######################

### You can safely run this entire block at any point ###

### until you see the next block begin below. ###

def H$($m$)$:

$"""$

This function returns the Hadamard constant of the $($assumed square$)$

matrix m$.$

$"""$

n $=$ m$.$dimensions$()[0]$

return RR$($abs$($m$.$det$())/$prod$([$RR$($norm$($m$.$column$($i$)))$ for i in range$($n$)]))^(1/$n$)$

def encode$($s$)$:

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

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

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

return

return vector$($ZZ$,[$ord$($s$[$i$])-64$ for i in range$($len$($s$))]+[-64$ for i in range$($n$-$len$($s$))])$

def decode$($s$)$:

v $=[]$

for i in range$($len$($s$))$:

if s$[$i$]==-64$:

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

v$.$append$($chr$($s$[$i$]+64))$

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

def printmatrix$($M$)$:

$"""$

This gives an output you can copy$/$paste and get back

as a matrix by saying matrix$(($the output here$))$

$"""$

return $[[$ x for x in M$.$row$($i$)]$ for i in range$($n$)]$

def KnapsackMatrix$($M$,$ S$)$:

$"""$

Return the row matrix which corresponds to the knapsack problem

$"""$

v $=[]$

n $=$ len$($M$)$

for i in range$($n$)$:

t $=[0$ for j in range$($n$+1)]$

t$[$i$]=2$

t$[$n$]=$ M$[$i$]$

v$.$append$($t$)$

t $=[1$ for j in range$($n$+1)]$

t$[$n$]=$ S

v$.$append$($t$)$

### End of functions block ###

###################################################

#################### PROBLEMS $1-9$ ####################

V $=$ matrix