Notes on the LVP and CVP in $p$-adic Fields

Abstract

This paper explores computational methods for solving the Longest Vector Problem (LVP) and Closest Vector Problem (CVP) in $p$-adic fields. Leveraging the non-Archimedean property of $p$-adic norms, we propose a polynomial time algorithm to compute orthogonal bases for $p$-adic lattices when the $p$-adic field is given by a minimal polynomial. The method utilizes the structure of maximal orders and $p$-radicals in extension fields of ${\mathbb{Q}}_p$ to efficiently construct uniformizers and residue field bases, enabling rapid solutions for the LVP and CVP. In addition, we introduce the characterization of norms on vector spaces over ${\mathbb{Q}}_p$.

16 pages