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

'''Теорема 1. Пусть дана функция типа «r к 1» <math>F: X \to Y, r \ge 2</math>, и целое число <math>1 \le k \le N = |X|</math>. Алгоритм Collision(F, k) возвращает коллизию после ожидаемого числа <math>O(k + \sqrt{N/(rk)})</math> оценок F с использованием <math>\Theta(k)</math> ячеек памяти. В частности, при <math>k = \sqrt[3]{N/r}</math> алгоритм Collision(F, k) использует <math>O(\sqrt[3]{N/r})</math> ожидаемых оценок и <math>\Theta(\sqrt[3]{N/r})</math> ячеек памяти.'''

'''Следствие 2'''. Существует квантовый алгоритм, способный найти коллизию в произвольной функции <math>F: X \to Y</math> для любого <math>r \ge 2</math>, используя объем памяти S и ожидаемое число O(T) оценок F для каждого <math>1 \le S \le T</math> при условии <math>S T^2 \ge |F(X)|</math>, где F(X) обозначает образ F.

Алгоритм использует в качестве процедуры версию алгоритма поиска Гровера. Если дана функция H с размером области n и цель y, алгоритм Grover(H, y) возвращает x, такой, что H(x) = y, за ожидаемое число <math>O(\sqrt{n})</math> оценок H.

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 нет коллизий).