NOTES ON THE GENERALIZED GAUSS REDUCTION ALGORITHM
Baissalov Y. Nauryzbayev R.
January 2025L.N. Gumilyov Eurasian National University
Eurasian Mathematical Journal
2025#16Issue 223 - 29 pp.
The hypothetical possibility of building a quantum computer in the near future has forced a revision of the foundations of modern cryptography. The fact is that many difficult algorithmic problems, such as the discrete logarithm, factoring a (large) natural number into prime factors, etc., on the complexity of which many cryptographic protocols are based these days, have turned out to be relatively easy to solve using quantum algorithms. Intensive research is currently underway to find problems that are difficult even for a quantum computer and have potential applications for cryptographic protocols. Our article contains notes related to the so-called generalized Gauss algorithm, which calculates the reduced basis of a two-dimensional lattice [8], [2]. Note that researchers are increasingly putting forward difficult algorithmic problems from lattice theory as candidates for the foundation of post-quantum cryptography. The majority of algorithmic problems related to lattice reduction become NP-hard as the lattice dimension increases [3], [1]. Fundamental problems such as the Shortest Vector Problem (SVP), the Closest Vector Problem (CVP), and Bounded Distance Decoding (BDD) are conjectured to remain hard even for quantum algorithms [4], [6]. Although the generalized Gauss reduction algorithm applies to two-dimensional lattices, where exact analysis is feasible (dimensions 3 and 4 are studied in [7], [5]), understanding such low-dimensional reductions provides important insights into the structure and complexity of lattice-based cryptographic constructions.
generalized Gaussian algorithm , lattice , reduced basis , well-ordered basis
Text of the article Перейти на текст статьи
Department of Mechanics and Mathematics L.N. Gumilyov Eurasian National University, 13 Kazhymukan St, Office 115, Astana, 010008, Kazakhstan
Department of Mechanics and Mathematics L.N. Gumilyov Eurasian National University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026