Редактировать: Позвольте мне попытаться объяснить дальше. Это потому, что алгоритм ищет ограниченные решения, которые он находит в среднем один принадлежащий $$\frac{(2^{d/3})^4}{2^d}=2^{d/3}$$ решения, присутствующие в списках $L_i$ как выбрано ниже. Это цена, заплаченная за сложность $2^{д/3}$ вместо $2^{д/2}$ сложности Шамира Шреппеля.
Берем дело $к=4,$ когда ищешь решение
$$x_0+x_1+x_2+x_3=0,\quad x_i \in L_i$$ Вагнер случайным образом генерирует 4 списка $L_i~(1\leq i\leq 4)$ размера $2^{д/3}$ куда $д$ это битовая длина.
По статистическим аргументам у вас будет единственное решение с постоянной вероятностью, отделенной от нуля, когда списки имеют размер $2^{д/4}$ (учитывайте тот факт, что существуют $(2^{д/4})^4=2^д$ 4-суммы, которые можно извлечь из этих списков, и с постоянной вероятностью значение $0$ будет поражен). Но дело в том, что нет эффективного способа найти это единственное решение, кроме как методом Шамира-Шреппеля, который имеет эффективную память, но временную сложность. $2^{д/2}.$
Что делает Вагнер, так это рекурсивно генерирует решения, но решения имеют особую структуру. Первая треть битов кандидатов из $L_0,L_1$ совпадают, аналогично для $L_2,L_3$ и т.д.
Поскольку решения структурированы, вам необходимо генерировать больше решений, чем минимально необходимое число, чтобы ваш алгоритм нашел единственное решение с хорошей вероятностью.
