Квантовый алгоритм для решения задачи поиска коллизий: различия между версиями

1. Выбрать произвольное подмножество <math>K \subseteq X</math> мощности k. Построить таблицу L размера k, каждый элемент которой содержит отдельную пару (x, F(x)), <math>x \in K</math>.

3. Проверить, содержит ли L коллизию – то есть существуют ли отдельные элементы <math>(x_0,F(x_0)),(x_1, F(x_1)) \in L</math>, для которых <math>F(x_0) = F(x_1)</math>. Если да, перейти к шагу 6.

4. Вычислить <math>x_1 = Grover(H, 1)</math>, где <math>H: X \to \{ 0, 1 \}</math> обозначает функцию, определяемую следующим образом: H(x) = 1 тогда и только тогда, когда существует <math>x_0 \in K</math>, такой, что <math>(x_0; F(x)) \in L</math>, но <math>x \ne x_0</math>.  (Заметим, что если <math>x_0</math> существует, то он является уникальным, поскольку мы уже проверили, что в L нет коллизий).