On Some Computational Problems in Local Fields

doi:10.1007/s11424-021-0074-8

Journal of Systems Science and Complexity ›› 2022, Vol. 35 ›› Issue (3): 1191-1200.DOI: 10.1007/s11424-021-0074-8

On Some Computational Problems in Local Fields

DENG Yingpu^1,2, LUO Lixia^1,2, PAN Yanbin^1,2, XIAO Guanju^1,2

1. Key Laboratory of Mathematics Mechanization, NCMIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; 2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

Received:2020-04-08 Revised:2020-04-08 Online:2022-06-25 Published:2022-06-20

PDF ( 14 ) Cited

DENG Yingpu, LUO Lixia, PAN Yanbin, XIAO Guanju. On Some Computational Problems in Local Fields[J]. Journal of Systems Science and Complexity, 2022, 35(3): 1191-1200.

Lattices in Euclidean spaces are important research objects in geometric number theory, and they have important applications in many areas, such as cryptology. The shortest vector problem (SVP) and the closest vector problem (CVP) are two famous computational problems about lattices. In this paper, we consider p-adic lattices in local fields, and define the p-adic analogues of SVP and CVP in local fields. The authors find that, in contrast with lattices in Euclidean spaces, the situation is different and interesting. The SVP in Euclidean spaces corresponds to the Longest Vector Problem (LVP) in local fields. The authors develop relevant algorithms, indicating that these problems are computable.

Key words: CVP, lattice, LVP, local field, SVP

[1] Fröhlich A and Taylor M J, Algebraic Number Theory, Cambridge University Press, Cambridge, 1991.
[2] Siegel C L, Lectures on the Geometry of Numbers, Springer, New York, 1989.
[3] Micciancio D and Goldwasser S, Complexity of Lattice Problems, A Cryptographic Perspective, Kluwer, Boston, 2002.
[4] https://csrc.nist.gov/Projects/Post-Quantum-Cryptography.
[5] Eisenträger K, Hallgren S, Lauter K, et al., Supersingular Isogeny Graphs and Endomorphism Rings:Reductions and Solutions, Eds. by Nielsen J B and Rijmen V, EUROCRYPT 2018, LNCS 10822, 2018, 329-368.
[6] Kohel D, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California, Berkeley, 1996.
[7] Koblitz N, p-adic Numbers, p-adic Analysis, and Zeta-Functions, Second edition, Springer, New York, 1984.
[8] Cassels J W S, Local Fields, Cambridge University Press, Cambridge, 1986.
[9] Serre J P, Local Fields, Springer, New York, 1979.
[10] Narkiewicz W, Elementary and Analytic Theory of Algebraic Numbers, Third Edition, Springer, New York, 2004.
[11] Weil A, Basic Number Theory, Third Edition, Springer, New York, 1974.
[12] Inoue H and Naito K, The shortest vector problems in p-adic approximation lattices and their applications to cryptography, Proceedings of Kyoto University Institute of Mathematics and Physical Sciences, 2015, 1963:16-23.

[1]	GAO Xiao-Shan,HUANG Zhang,WANG Jie,YUAN Chun-Ming. Toric Difference Variety [J]. Journal of Systems Science and Complexity, 2017, 30(1): 173-195.
[2]	NGUYEN The Vinh,PHAM Thi Hoai. New Results on System of Generalized Quasi-Ky Fan Inequalities with Set-Valued Mappings in Topological Semilattice Spaces [J]. Journal of Systems Science and Complexity, 2016, 29(6): 1585-1595.
[3]	PAN Yanbin,ZHANG Feng. Solving Low-Density Multiple Subset Sum Problems with SVP Oracle [J]. Journal of Systems Science and Complexity, 2016, 29(1): 228-242.
[4]	DONG Yanfang , WANG Jun. COMPLEX SYSTEM ANALYSIS OF MARKET RETURN PERCOLATION MODEL ON SIERPINSKI CARPET LATTICE FRACTAL [J]. Journal of Systems Science and Complexity, 2014, 27(4): 743-759.
[5]	Liyong SHEN;Engwee CHIONH;Xiao-Shan GAO;Jia LI. PROPER REPARAMETRIZATION FOR INHERENTLY IMPROPER UNIRATIONALVARIETIES [J]. Journal of Systems Science and Complexity, 2011, 24(2): 367-380.
[6]	Yu Mei MA. A REPRESENTATION THEOREM OF THE BOUNDED REGULAR OPERATORS FROM SOME SPACE X ONTO L_1(μ) [J]. Journal of Systems Science and Complexity, 2001, 14(3): 265-068.
[7]	SHU Guangfu. NECESSARY AND SUFFICIENT CONDITIONS FOR G-STRUCTURES WITH LOGICAL RELATIONS TO FORM BOUNDED LATTICES IN RECONSTRUCTABILITY ANALYSIS [J]. Journal of Systems Science and Complexity, 1993, 6(3): 252-258.
[8]	SHU Guangfu. BOOLEAN LATTICE CONDITIONS OF SYSTEM RECONSTRUCTABILITY ANALYSIS PROBLEMS WITH LOGICAL RELATIONS [J]. Journal of Systems Science and Complexity, 1993, 6(1): 88-096.

Viewed

Full text

Abstract