# A Finite Regime Analysis of Information Set Decoding Algorithms
## 3 A Finite Regime Analysis of Information Set Decoding Techniques
### Lee-Brickell
** The computational complexity is derived considering the number of iterations of the loops in the algorithm, taking into account the probability of the checks being taken. The spatial complexity is obtained as the sum of the size of the matrix \(H\), the size requirements of \(\mathcal{L}_{1}\) (as \(\mathcal{L}_{2}\) has the same size and can reuse its space) and the expected size of \(\mathcal{L}\) considering how many pairs may survive the check performed when building it. ### Becker-Joux-May-Meurer

The Becker-Joux-May-Meurer (BJMM) algorithm introduced in [PERSON] (1998) improves the MMT algorithm in two ways: the former is a recursive application of the list building strategy, and the latter is a change to the list element generation employed. We discuss the latter first, forsaking for the sake of clarity its recursive application at first. We then describe the adaptations needed to adopt the recursive splitting strategy without issues. The BJMM algorithm considers that it is possible to represent a vector \(e\) of weight \(p\), length \(k+\ell\), as the sum of two vectors \(e_{1},e_{2}\) of weight \(\frac{p}{2}+\varepsilon\), and with the same length, under the assumption that the \(\varepsilon\) extra ones cancel out during the addition. We recall that the MMT approach demands that both \(e_{1}\) and \(e_{2}\) have weight strictly equal to \(\frac{p}{2}\). The BJMM algorithm thus raises the number of valid pairs \(e_{1},e_{2}\) employed to represent \(e\) by a factor equal to \(\binom{k+\ell-p}{\varepsilon}\). Such an improvement is employed to further reduce the size of the lists of values which need to be computed to find \(e\) with a meet-in-the-middle approach on checking that the condition \(Ve_{1}+Ve_{2}=s_{\text{up}}\). Indeed, since \(R=\binom{p}{2}(k+\ell-p)\) pairs \((e_{1},e_{2})\) which respect \(e=e_{1}+e_{2}\) exist, searching a \(\frac{1}{R}\) fraction of the \(\binom{k+l}{\frac{l}{2}+e}^{2}\) exhaustively will yield (on average) a solution, assuming that the solution pairs are uniformly distributed over all the \(\binom{k+l}{\frac{l}{2}+e}^{2}\) ones. Willing to employ a strategy to enumerate only a \(\frac{1}{R}\) fraction of the pairs, while doing useful computation instead of a simple \(\frac{1}{R}\) sub-sampling of the space of the pairs, the BJMM algorithm opts for performing a partial check of the \(Ve_{1}+Ve_{2}=s_{\text{up}}\) equation, on a smaller number of bits than \(\ell\) and discarding the pairs which do not pass the check. Let us denote with \(V_{\text{up}[\rho]}\) the first \(\rho\) rows of \(V_{\text{up}}\) and with \(s_{\text{up}[\rho]}\) the first \(\rho\) bits of the syndrome \(s_{\text{up}}\) The BJMM algorithm thus employs the test \(V_{\text{up}[\rho]}e_{1}+V_{\text{up}[\rho]}e_{2}=s_{\text{up}[\rho]}\) to obtain a twofold objective: discard a fraction of the \((e_{1},e_{2})\) pairs, and select the portion to be kept among the pairs which at least have the first \(\rho\) bits of the sum of the columns of \(V_{\text{up}[\rho]}\) matching the value of the corresponding syndrome bits. Such an approach has the advantage over a random sampling that the pairs which are selected have already been checked for compliance on a part of the \(Ve_{1}+Ve_{2}=s_{\text{up}}\) equation, i.e., it performs a random subsampling while doing useful computation. The BJMM paper suggests that the value of \(\rho\) should be \(\rho\approx\log_{2}(R)\): under the assumption that the \(r\) bit sums being performed are made of random values, and that the sum should match a given \(r\) bit value, only a fraction equal to \(\frac{1}{2^{p}}\), i.e., \(\approx\frac{1}{R}\) survives. Note that, regardless of the choice of \(\rho\), a selection of the correct positions will always survive the preliminary checks on \(\rho\) bits, while wrong solutions are filtered out on the basis that they will not match on the first \(\rho\) bits.