4446
правок
Квантовый алгоритм для решения задачи поиска коллизий: различия между версиями
Материал из WEGA
Квантовый алгоритм для решения задачи поиска коллизий (посмотреть исходный код)
Версия от 22:40, 13 января 2023
, 13 января 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
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 нет коллизий). | 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 нет коллизий). | ||
5. | 5. Найти <math>(x_0, F(x1)) \in L</math>. | ||
6. Вывести результат в виде коллизии | 6. Вывести результат в виде коллизии <math> \{ x_0, x_1 \} </math>. | ||
== Применение == | == Применение == | ||
