{'fraction_non_alphanumeric': 0.027702089009990917, 'fraction_numerical': 0.01634877384196185, 'mean_word_length': 4.7973684210526315, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algorithms for the closest and shortest vector problems on general lattices

The shortest vector problem (SVP) and closest vector problem (CVP) are the most widely known problems on point lattices. SVP and CVP have been extensively studied both as purely mathematical problems, being central in the study of the geometry of numbers and as algorithmic problems, having numerous applications in communication theory and computer science. 
There are two main algorithmic techniques for solving exact SVP and CVP: enumeration and sieving. The best enumeration algorithm was given by Kannan in 1983 and solves both problems in nO (n) time, where n is the dimensionality of the lattice. Sieving was introduced by by Ajtai, Kumar and Sivakumar in 2001 and lowered the time complexity of SVP to 2O(n ), but required 2O( n) space and randomness. This result posed a number of important questions: Could we get a deterministic 2O( n) algorithm for SVP? Is it possible to acquire a 2O(n ) algorithm for CVP? 
In this dissertation we give new algorithms for SVP and CVP and resolve these questions in the affirmative. Our main result is a deterministic O(22n) time and O (2n) space that solves both SVP and CVP and by reductions of (Micciancio, 2008) most other lattice problems in NP considered in the literature. In the case of CVP the algorithm improves the time complexity from nO (n) to 2 O(n ), while for SVP we achieve single exponential time as sieving, but without using randomization and improving the constant in the exponent from 2.465 (Pujol and Stehle, 2010) to 2. The core of the algorithm is a new method to solve the closest vector problem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. We also present our earlier results on sieving algorithms. Although the theoretical analysis of the proposed sieving algorithm gives worse complexity bounds than our new Voronoi based approach, we show that in practice sieving can be much more efficient. We propose a new heuristic sieving algorithm that performed quite well in practice, with estimated running time 20.52n and space complexity 20.2n.