This thesis investigates lattice compression of polynomial matrices
over finite fields. For an m x n matrix, the goal of lattice
compression is to find an m x (m+k) matrix, for some relatively
small k, such that the lattice span of two matrices are
equivalent. For any m x n polynomial matrix with degree bound
d, it can be compressed by multiplying by a random n x (m+k)
matrix B with degree bound s. In this thesis, we prove that
there is a positive probability that
L(A)=L(AB) with k(s+1)=\Theta(\log(md)). This
is shown to hold even when s=0 (i.e., where B is a matrix of
constants). We also design a competitive probabilistic lattice
compression algorithm of the Las Vegas type that has a positive
probability of success on any input and requires
O~(nm^{\theta-1}B(d)) field operations.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/2778 |
| Date | January 2007 |
| Creators | Li, Chao |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | 283031 bytes, application/pdf |
Page generated in 0.0019 seconds