Мы можем использовать второстепенный вариант Детский шаг / гигантский шаг найти $д$ с в порядке $3\,2^{n/2}$ добавление точек (и нормализация к уникальному точечному представлению). Мы делаем детские шаги из $X_1$, и гигантские шаги от $X_2$ (в обе стороны для более позднего, чтобы компенсировать неизвестный знак $x_1-x_2$). Вот оно:
- позволять $m=\lceil2^{n/2}\rceil$
- позволять $W_0:=X_1$
- за $я$ от $1$ к $м-1$ (Шаги малыша)
- установлен $W_i=W_{i-1}+G$
примечание: здесь $W_i=X_1+i\,G$
- позволять $Н=м\,G$ (который можно получить как $H=W_{m-1}+G-W_0$ )
- позволять $U:=X_2$ и $V:=X_2-H$
- позволять $j=0$
- повторить (Гигантские шаги)
примечание: здесь $U=X_2+(j\,m)\,G$ и $V=X_2-((j+1)\,m)\,G$
- если $U$ находится в $W_i$
- вывод $|j\,m-i|$ и остановись
- если $В$ находится в $W_i$
- вывод $(j+1)\,m+i$ и остановись
- позволять $U:=U+H$ и $V:=V-H$
- позволять $j:=j+1$
Если из условий, изложенных в примечаниях, следует, что этот алгоритм всегда останавливается с выходом $д$ примерно после $d/2^{n/2}$ (в большинстве $м$) итераций повторяющегося цикла. Обратите внимание, что при использовании соответствующей структуры данных стоимость поиска $U$ и $В$ в таблице $W_i$ по существу постоянна относительно $n$, таким образом, основные вычислительные затраты — это добавление точек (и нормализация их результата так, чтобы $W_i$ можно эффективно искать).
Проблема в том, что для этого требуется много памяти для таблицы $W_i$, и алгоритм, как указано, является последовательным. Эту проблему можно решить и распределить поиск между несколькими машинами, используя методы, описанные Полом К. ван Оршотом и Майклом Дж. Винером. Параллельный поиск столкновений с помощью криптоаналитических приложений, в Журнал криптологии, 1999 г..
