Editați | ×: Lasă-mă să încerc să explic mai departe. Se datorează faptului că algoritmul caută soluții restricționate pe care le găsește în medie unu al $$\frac{(2^{d/3})^4}{2^d}=2^{d/3}$$ solutii prezente in liste $L_i$ după cum se alege mai jos. Acesta este prețul plătit pentru complexitate $2^{d/3}$ in loc de $2^{d/2}$ complexitatea lui Shamir Schroeppel.
Luând cazul $k=4,$ care este atunci când cauți o soluție
$$x_0+x_1+x_2+x_3=0,\quad x_i \in L_i$$ Wagner generează aleatoriu 4 liste $L_i~(1\leq i\leq 4)$ de mărime $2^{d/3}$ Unde $d$ este lungimea bitului.
Prin argumente statistice ai avea un soluție unică cu probabilitate constantă delimitată de zero atunci când listele sunt de dimensiune $2^{d/4}$ (luați în considerare faptul că există $(2^{d/4})^4=2^d$ 4-sume care pot fi extrase din aceste liste si cu probabilitate constanta valoarea $0$ va fi lovit). Dar ideea este că nu există o modalitate eficientă de a găsi această soluție unică, cu excepția metodei Shamir-Schroeppel, care are memorie eficientă, dar complexitate în timp. $2^{d/2}.$
Ceea ce face Wagner este să genereze recursiv soluțiile, dar soluțiile au o structură specială. Prima treime din biți ai candidaților din $L_0,L_1$ sunt potrivite, la fel pentru $L_2,L_3$ etc.
Pentru că soluțiile sunt structurate, trebuie Genera mai multe soluții decât numărul minim necesar, astfel încât algoritmul dvs. să găsească o singură soluție cu o bună probabilitate.
