The k-XOR problem introduced by Wagner in 2002 is to find k elements \(e_i \in l_i\) such that \(\bigoplus _{i=0}^{k-1} e_i = 0\) , where \(l_i\) is a list of elements drawn at random from \(\{0, 1\}^n\) . How to design a k-XOR algorithm with an efficient Time-Memory Tradeoff (TMTO) formula remains an open problem. The current method involves first applying a preparation algorithm to generate the initial lists of the k-XOR algorithm with partial collisions, followed by running a k-XOR algorithm. In this paper, we focus on designing an efficient k-XOR algorithm after the preparation phase through a decomposition-and-reconstruction strategy. The main idea of our strategy is to consider all possible decompositions of k, i.e. \(k = \sum _{0 \le i \le r-1} k_i\) ( \(1 \le k_i \le k-1\) , \(2 \le r \le k-1\) ), and then use the \(k_i\) -XOR algorithms and the r-XOR algorithm to reconstruct the k-XOR algorithm. Our design strategy has two improvements. On the one hand, we consider all possible decompositions of k, which is equivalent to exploring all potential designs of the k-XOR algorithms. On the other hand, in the reconstruction of the k-XOR algorithms, we utilize the on-the-fly technique and the layered technique to improve the merging efficiency of lists and balance the time complexity of each component as much as possible, aiming to decrease the total time complexity of the k-XOR algorithm. As a result, the k-XOR algorithms we designed have the current most effective TMTO formulas. For example, the TMTO formula for the 8-XOR algorithm is \(N = TM^2\) \((M \le T \le M^5)\) , which extends the effective interval of Dinur’s result \(N = TM^2\) \((M^2 \le T \le M^5)\) . In addition, after combining the preparation algorithms, we improve the best previous formula from \(N = T^2\,M^{3\lceil \frac{\log k}{2} \rceil - 2 - (\log k \bmod 2)}\) to \(N = T^3\,M^{3\lceil \frac{\log k}{2} \rceil - 4 - (\log k \bmod 2)}\) when \(k = 2^i\) ( \(i \ge 3\) ) and \(M^2 \le T \le M^{k/2 - \lfloor \frac{\log k/2}{2} \rfloor -\log k + 2}\) . As an application, our efficient algorithms can improve the complexity of solving the Parity Check Problem compared to existing results.
