An Upper Bound on the Calls to Vector Exchanges for the Crystal Motif Reduction in the AE algorithm: A Complexity Result

This paper introduces and proves a complexity theorem on the total number of calls to vector exchanges during the reduction of the crystal motif performed in the Abdelalim-Elmouki algorithm (AE), first published in 2023. For this, in this work we focus on finding that number when we use, for example, a Gram-Schmidt orthogonalization process. As a result, we find that the calls to exchanges cannot exceed a bound in terms of the crystal dimension, a maximum value on the norms of the bad vectors, and the crystal reduction parameter.