Wiki du cours

Rédacteur: Filipe Moreira Da Silva

A traiter [Modifier]

• Stratégie pour résoudre des problèmes en temps quantique aléatoire ([1] Section 5).
• Structures linéaires cachées ([1], Section 2).
• Enoncés des Théorèmes 1 and 2 ([1] Section 2).
• Comment résoudre le problème du logarithme discret en temps quantique aléatoire en utilisant les Théorèmes 1 et 2 ([1] Section 3).

Stratégie pour résoudre des problèmes en temps quantique aléatoire [Modifier]

Pour résoudre un problème en un temps quantique aléatoire on va procéder a une expérience \( \epsilon\). A chaque expérience on obtient une valeur observable.
Soit \( \mathcal{V}\) l'ensemble de toutes les valeurs observables possibles.
On veut que les trois conditions ci-dessous soient satisfaites :
1. Pour toutes valeurs dans \(\mathcal{V}\) on peut résoudre le problème donné en un temps polynomial.
2. La probabilité d'observer une valeur observable spécifique de \(\nu\) est au moins \(1/Wn^c\), avec W un entier et \(c\) une constante.
3. La cardinalité de l'ensemble \(\mathcal{V}\) est au moins \(W/n^{c'}\) pour une constante \(c'\).

On appelle les valeurs de \(\mathcal{V}\), les "bonnes" observables.
Par les conditions 2 et 3, la probabilité d'obtenir une valeur de \(\mathcal{V}\) est au moins \(1/n^{O(1)}\).
Et donc, quand une valeur sera obtenue, on l'utilisera pour résoudre le problème, et par la première condition, on sait que le problème sera résolu en un temps polynomial.
Il est important de remarquer qu'on ne sait pas si une valeur appartient a l'ensemble \(\mathcal{V}\).
Quand on obtient une valeur, il suffit de vérifier que cette valeur permet de résoudre le problème comme si elle était dans \(\mathcal{V}\).
On vérifie, alors, que le résultat est correct, s'il ne l'est pas on recommence avec une nouvelle valeur.

Structures linéaires cachées [Modifier]

Définition : Une fonction h : \(\mathbb{Z}\ \rightarrow S\) est q-périodique si \(h(x+q) = h(x)\).

Une telle fonction h peut être vue comme une fonction de \(\mathbb{Z}_q\) dans S.
On dit que h est d'ordre au plus m si pour tout z \(\in S\), \(| h^{-1}(z) (mod \) \(q) |\) \(\leqslant m\).

Définition : Soit \(f(x_1,...,x_n)\) une fonction d'entiers \(\mathbb{Z}^{k}\) dans un ensemble arbitraire S.
\(f\) possède une structure linéaire cachée sur q si :
\(f(x_1,...,x_n)\) = \(h(x_1+\alpha_2x_2+... +\alpha_nx_n)\) pour tout entier \(x_1,...,x_n\)

On dit que \(f\) est d'ordre au plus m si h est d'ordre au plus m.

Enoncés des Théorèmes 1 et 2 [Modifier]

Théorème 1 :
Soit \(f(x_1,...,x_n)\) une fonction ayant une structure linéaire cachée sur q d'ordre au plus m. On impose deux conditions :
1. Soit n = \(logq\), alors m et k sont au plus \(n^{O(1)}\)
2. Soit p le plus petit premier qui divise q, alors \(m<p\)
Pour une telle fonction f, dans un temps quantique aléatoire dans n, on peut retrouver les valeurs \(\alpha_2\),... ,\(\alpha_n (mod\) \(q)\).

Théorème 2 :
Soit h : \(\mathbb{Z}\ \rightarrow S\) une fonction périodique. Soit q la plus petite période positive de h et on assume que l'ordre de h est au plus m. On impose deux conditions :
1. Soit n = \(logq\), alors m est au plus \(n^{O(1)}\)
2. Soit p le plus petit premier qui divise q, alors \(m<p\)
Pour une telle fonction f, dans un temps quantique aléatoire dans n, il est possible de retrouver la période q de h.

Comment résoudre le problème du logarithme discret en temps quantique aléatoire en utilisant les Théorèmes 1 et 2 [Modifier]

Soit h : \(\mathbb{Z}\ \rightarrow G\) un homomorphisme et \(\beta = h(\alpha) \). Etant donné \(\beta\) on veut trouver le plus petit entier positif x tel que \(\beta = h(x) \) car \(h(x) = h(1)^x\) et donc ce x est la solution du logarithme discret \(h(1)^x = \beta \) .
Soit d l'ordre de \(h(1)\) dans G, donc l'homomorphisme \(h\) est d-périodique.
On définit la fonction \(f :\mathbb{Z}^{2} \rightarrow G\) telle que \( f(x,y) = h(x+ \alpha y) \). La fonction f possède une structure linéaire d'ordre 1.
Comme h est un homomorphisme, f peut être évaluée comme ci-dessous:
\( f(x,y) = h(x)h(\alpha y) = h(x)h(\alpha)^y = h(x) \beta^y \)

En général pour résoudre le problème du logarithme discret, il faudra d'abord utilisé le théorème 2 pour trouver d, la période de l'homomorphisme \(h\). On peut utiliser le théorème car l'ordre de \(h\) est 1.
On applique ensuite le théorème 1 pour trouver un entier \(x < d\), tel que \(x = \alpha (mod\) \(d)\).
Comme \(x\) est le plus petit entier positif tel que \(h(\alpha) = h(x)\), c'est la solution du problème du logarithme discret.

Références [Modifier]

[1] Dan Boneh, Richard J. Lipton, Quantum cryptanalysis of hidden linear functions
[2] Peter W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer