Heuristic Number Geometry Method for Finding Low-Weight Codeword in Linear Block Codes

The article introduces a novel method for finding low-weight words in linear block binary and ternary codes by leveraging the Number Geometry. The methodology involves employing a set of heuristics related to vector lengths, lattice densities, dual space operations, permutations of lattice basis, and the search for short vectors within it. Notably, this proposed method secured the top position in the international low-weight codeword search competition organized by prominent institutions, including the French National Center for Scientific Research (CNRS), Inria Paris, and the National Research Institute for Mathematics and Informatics in the Netherlands (CWI). In a remarkable display of its effectiveness, the method successfully discovered a codeword of weight 212 in the parity-check matrix of a block binary code with a rate of 0.5 and a code length of 1280. Importantly, this accomplishment was realized within a timeframe of 4,147,201 seconds, utilizing an Intel 7700K 64GB system with a 1070 8GB video card. The search specifically excluded automorphisms and other symmetry properties, such as cyclicity and quasi-cyclicity. Furthermore, when applied to the low-weight word search problem (weight 228) in the mentioned competition, our proposed method exhibited a remarkable acceleration, being 3172.9 times faster than the Brouwer-Zimmerman algorithm implemented in the MAGMA Version 2.22-3 package. Additionally, it surpassed the best standalone implementation with vectorization and parallelization by 899 times. This noteworthy speedup underscores the efficiency and competitiveness of the introduced approach in effectively addressing the intricate task of identifying low-weight codewords in linear block codes.