Leiden University Student Repository

Woerden, W.P.J. van (2016)

The closest vector problem in cyclotomic lattices

Bachelor thesis | Wiskunde (BSc)

In this thesis we are interested in constructing an efficient algorithm for solving the closest vector problem (CVP) in the cyclotomic lattices and their duals. We will show that every cyclotomic lattice can be constructed by direct sums and tensor products from the lattices A ∗ n (n ≥ 1). For the prime power cases this results in a linear CVP algorithm for the cyclotomic lattice and its dual. For the composite case n = p · q with p and q prime we will construct a subexponential CVP algorithm and for its dual a polynomial CVP algorithm. Both of these algorithms can efficiently be extended to the n = p kq l case.

Author

Woerden, W.P.J. van

Faculty

Faculty of Science

Supervisors

Ducas, L.
Bonsangue, M.M.

ECTS Credits

24

Language

en