Notes on the LVP and the CVP in
p · 2025
Read Notes on the LVP and the CVP in by p (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24207.txt.
Introduction
Chi Zhang and Mingqian Yao solve two classic lattice problems in p-adic fields. The problems are the longest vector problem and the closest vector problem. P-adic norms are non-Archimedean. That property changes the geometry completely. Distances obey a stronger triangle inequality there.
The authors exploit that structure. They give a polynomial-time algorithm for orthogonal bases of p-adic lattices. The field must be given by a minimal polynomial. Maximal orders supply the needed structure. So do p-radicals in extension fields of the p-adic numbers. Uniformizers and residue field bases are built efficiently. With those in hand, both lattice problems become rapid to solve. The paper also characterizes norms on vector spaces over the p-adics. The notes serve readers working where number theory meets computation.
Catalog record
| CREATOR | p |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-24207
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Notes on the LVP and the CVP in p Abstract 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 LVP and CVP. In addition, we introduce the characterization of norms on vector spaces over \mathbb{Q}_{p} . 2010 Mathematics Subject Classification: Primary 11F85, Secondary 94A60. Key words and phrases: p -adic fields, orthogonal basis, longest vector problem (LVP), closest vector problem (CVP), maximal order. 1 Introduction The study of computational problems in non-Archimedean geometry, particularly over p -adic fields, has emerged as a significant area of intersection between algebraic number theory and theoretical cryptography. The Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP), central to lattice-based hardness assumptions in Euclidean spaces, extend naturally to p -adic vector spaces, where the non-Archimedean norm structure |\cdot|_{p} (satisfying |v+w|_{p}\leq\max\{|v|_{p},|w|_{p}\} ) enables qualitatively distinct geometric decompositions. These generalizations to p -adic vector spaces are the Longest Vector Problem (LVP) and the Closest Vector Problem (CVP). They are first introduced by Deng et al. [ 3 ] in 2018. These new problems are considered to be hard and potentially applicable for constructing public-key encryption cryptosystems and signature schemes. In 2021, by introducing a trapdoor function with an orthogonal basis of a p -adic lattice, Deng et al. [ 5 ] constructed the first signature scheme and public-key encryption cryptosystem based on p -adic lattices. The experimental results demonstrated that the new schemes achieve good efficiency. As for security, they did not give formal proofs for these schemes since the problems in local fields are relatively very new. Recently, much research has been done to analyze security of these schemes. In 2025, Zhang [ 12 ] improved the LVP algorithm in local fields. The modified LVP algorithm is a deterministic polynomial time algorithm when the field is totally ramified and p is a polynomial in the rank of the input lattice, hence can be utilized to break the schemes. This attack extremely reduced the security strength of the schemes. In order to avoid this attack, Zheng et al. [ 13 ] proposed a method to construct orthogonal bases in p -adic fields with a large residue degree, which is helpful to modify the p -adic signature scheme and public-key encryption cryptosystem. Nevertheless, these previous efforts ignored an essential aspect that given a minimal polynomial of a local filed, there are polynomial time algorithms to compute the maximal order of this field, such as the Round 2 Algorithm [ 1 ] and the Round 4 Algorithm [ 2 ] . Besides, unlike their real or complex counterparts, p -adic lattices admit orthogonal bases, see [ 11 ] . Orthogonal bases of p -adic lattices can be used to solve the LVP and the CVP in polynomial time [ 5 , 11 ] , and can be derived from maximal orders and uniformizers in p -adic fields. Combining together, they provide a framework to efficiently solve the LVP and the CVP in p -adic fields. Recent advancements in p -adic computational algebra have highlighted the role of p -radicals and residue field extensions in constructing orthogonal decompositions, yet algorithms for the general LVP or CVP instances remain underexplored. Existing deterministic methods for Euclidean lattices (e.g., LLL reduction) do not directly generalize due to the ultrametric inequality. We addresses this gap by presenting a polynomial time algorithm to compute orthogonal bases for p -adic lattices, thereby reducing the LVP and the CVP to tractable subproblems over orthogonal subspaces. Our contributions are : 1. Algorithmic Innovation: By integrating p -adic Gram-Schmidt orthogonalization with residue field computations, we design efficient solvers for the LVP and the CVP in p -adic fields, proving their polynomial time complexity under standard assumptions. 2. Practical Validation: A concrete example over \mathbb{Q}_{2}(\sqrt{5}) demonstrates the algorithm’s feasibility in computing orthogonal bases and solving lattice problems. The paper is structured as follows: Section 2 reviews p -adic norms, local fields, and lattice definitions. Section 3 introduces maximal orders and p -radicals as tools for enlarging subrings. Section 4 proves the existence of orthogonal bases via uniformizers and residue field extensions. Section 5 detail the LVP and the CVP algorithms, while Section 6 provides an example. Section 7 introduce the characterization of norms on vector spaces over \mathbb{Q}_{p} . By unifying algebraic techniques with computational efficiency, this work advances the theoretical understanding of p -adic lattice problems, with implications for post-quantum cryptography and the arithmetic of p -adic extensions. 2 Preliminaries 2.1 Norm and Orthogonal Basis Let p be a prime. Let V be a vector space over \mathbb{Q}_{p} . A norm on V is a function |\cdot|:V\rightarrow\mathbb{R} such that 1. \left|v\right|\geq 0 for any v\in V , and \left|v\right|=0 if and only if v=0 ; 2. \left|xv\right|=\left|x\right|_{p}\cdot\left|v\right| for any x\in\mathbb{Q}_{p} and v\in V ; 3. \left|v+w\right|\leq\max{\left\{\left|v\right|,\left|w\right|\right\}} for any v,w\in V . If |\cdot| is a norm on V , and if \left|v\right|\neq\left|w\right| for v,w\in V , then we must have \left|v+w\right|=\max{\{\left|v\right|,\left|w\right|\}} . Weil ( [ 8 ] page 26) proved the following proposition. Proposition 2.1 ( [ 8 ] ) . Let V be a vector space over \mathbb{Q}_{p} of finite dimension n>0 , and let \left|\cdot\right| be a norm on V . Then there is a decomposition V=V_{1}+V_{2}+\cdots+V_{n} of V into a direct sum of subspaces V_{i} of dimension 1 , such that \left|\sum_{i=1}^{n}{v_{i}}\right|=\max_{1\leq i\leq n}{\left|v_{i}\right|} for any v_{i}\in V_{i} , i=1,2,\dots,n . Weil proved the above proposition for finite-dimensional vector spaces over a p -field (commutative or not). For simplicity, we only consider the case \mathbb{Q}_{p} . Thus, we can define the orthogonal basis. Definition 2.2 (orthogonal basis [ 8 ] ) . Let V be a vector space over \mathbb{Q}_{p} of finite dimension n>0 , and let |\cdot| be a norm on V . We call \alpha_{1},\alpha_{2},\dots,\alpha_{n} an orthogonal basis of V over \mathbb{Q}_{p} if V can be decomposed into the direct sum of n 1 -dimensional subspaces V_{i}={\rm Span}_{\mathbb{Q}_{p}}(\alpha_{i}) (1\leq i\leq n) , such that \left|\sum_{i=1}^{n}{v_{i}}\right|=\max_{1\leq i\leq n}{\left|v_{i}\right|} for any v_{i}\in V_{i} , i=1,2,\dots,n . Two subspaces U , W of V are said to be orthogonal if the sum U+W is a direct sum and it holds that \left|u+w\right|=\max\left\{\left|u\right|,\left|w\right|\right\} for all u\in U , w\in W . 2.2 Basic Facts about Local Fields In this subsection, we recall some basic facts about local fields. More details about local fields can be found in [ 6 , 7 ] . Let p be a prime. For x\in\mathbb{Q} with x\neq 0 , write x=p^{t}\cdot\frac{a}{b} with t,a,b\in\mathbb{Z} and p\nmid ab . Define \left|x\right|_{p}=p^{-t} and \left|0\right|_{p}=0 . Then |\cdot|_{p} is a non-Archimedean absolute value on \mathbb{Q} . Namely, we have: 1. \left|x\right|_{p}\geq 0 and \left|x\right|_{p}=0 if and only if x=0 ; 2. \left|xy\right|_{p}=\left|x\right|_{p}\left|y\right|_{p} ; 3. \left|x+y\right|_{p}\leq\max{\left\{\left|x\right|_{p},\left|y\right|_{p}\right\}} . If \left|x\right|_{p}\neq\left|y\right|_{p} , then \left|x+y\right|_{p}=\max{\left\{\left|x\right|_{p},\left|y\right|_{p}\right\}} . Let \mathbb{Q}_{p} be the completion of \mathbb{Q} with respect