Université BORDEAUX 1 U.F.R. Mathématiques et Informatique
MAI 932 EX2 (épreuve de J.Bétréma) 23 janvier 2004
Master Crypto 2
Cryptologie appliquée, complexité

Durée: 1 heure 30
Tous documents interdits.

Exercice 1

Voir le corrigé.

  1. Que peut-on dire des classes de complexité des problèmes COMPOSITE (un entier a-t-il des facteurs non triviaux) et PRIME (un entier est-il premier) ? Chacune des parties de la réponse devra être accompagnée d'une preuve sommaire. Note : une réponse correcte comporte plusieurs résultats, et occupe environ une page, répondre "AKS" ne suffit pas…
  2. Le problème de la factorisation d'un entier peut se réduire polynomialement à un problème de décision D ; énoncer D, et prouver l'affirmation qui précède.
  3. Que peut-on dire des classes de complexité de D ? Note : une réponse correcte comporte plusieurs résultats, et occupe environ une page (la réciproque n'est pas vraie, une réponse d'une page peut ne rapporter aucun point…)

Exercice 2

Voir le corrigé.

  1. Rappeler la définition de la classe de complexité RP, et prouver que RP est inclus dans NP. Note : RP est une classe de complexité liée aux algorithmes du type Miller-Rabin ; on confond souvent, et c'est légitime, la définition de RP et celle de co-RP ; mais on peut retrouver qui est qui, en sachant que le problème de l'inclusion de co-RP dans NP est ouvert.
  2. ZPP est la classe des problèmes de décision qui peuvent être résolus par un algorithme probabiliste polynomial avec zéro erreur :

    Prouver que ZPP est l'intersection de RP et co-RP.


Corrigé

Exercice 1

Voir l'énoncé.

  1. La réponse comporte plusieurs parties :
  2. 3 points.Soit D (n, k) le problème de décision suivant (appelé HAS-FACTOR en cours) : n possède-t-il un facteur inférieur à k ? Le problème de la factorisation d'un entier se réduit polynomialement à D, en utilisant une recherche dichotomique du plus petit facteur de n : soit m = n1/2, on commence par calculer D (n, m) ; si la réponse est 0, n est premier ; sinon on calcule D (n, m/2) ; si la réponse est 0, on calcule D (n, 3m/4), sinon on calcule D (n, m/4) ; et ainsi de suite… Le nombre d'appels à D est borné par le logarithme binaire de m, soit la moitié du logarithme binaire de n, qui est la taille de l'entier n.
  3. La réponse comporte plusieurs parties :

    Note : une grande partie de la cryptologie moderne repose sur la difficulté du problème de la factorisation, et donc de D ; elle repose aussi sur la facilité (relative) de PRIME (test de primalité), car pour produire de grands nombres difficiles à factoriser, il faut produire efficacement de grands nombres premiers. Confondre les classes de complexité de ces deux problèmes est donc inadmissible dans le contexte de ce master.

Exercice 2

Voir l'énoncé.

  1. 4 points. RP est la sous-classe de NP obtenue en exigeant qu'il existe un nombre significatif de certificats, de telle sorte que la recherche au hasard d'un tel certificat ait une probabilité significative de succès. Un langage L est dans RP si et seulement s'il existe un algorithme probabiliste polynomial A tel que :

    x appartient à L ⇒ proba [ A (x, r) = 1 ] > λ > 0
    x n'appartient pas à L ⇒ proba [ A (x, r) = 0 ] = 1

    où λ désigne une constante (qu'on peut choisir égale à 1/2), et r une variable aléatoire, qui sert de certificat pour x lorsque A (x, r) = 1 ; les probabilités font référence à cette variable aléatoire r, et comme il s'agit de probabilités discrètes, la seconde condition peut aussi s'écrire :

    x n'appartient pas à L ⇒ ∀r A (x, r) = 0

    ou encore, en prenant la contraposée

    A (x, r) = 1 ⇒ x appartient à L.

    Note : lorsque x n'appartient pas à L, autrement dit lorsque la "bonne réponse" est 0, l'algorithme A répond toujours 0 ; il ne faut pas en déduire malencontreusement que lorsque A répond 0, c'est une réponse "sûre" ; au contraire, comme on vient de le voir, c'est la réponse 1 qui est sûre, même si c'est déconcertant à première vue !

    Terminologie : on peut remplacer le langage L par sa fonction caractéristique χ , et énoncer, de façon équivalente, que le problème de décision χ est dans RP si et seulement s'il existe un algorithme probabiliste polynomial A tel que :

    χ (x) = 1 ⇒ proba [ A (x, r) = 1 ] > λ > 0
    χ (x) = 0 ⇒ ∀r A (x, r) = 0

    Pour comparer rigoureusement RP et NP, on peut rappeler que L est dans NP si et seulement s'il existe un vérifieur polynomial V tel que :

    xL ⇔ ∃c V (x, c) = 1

    c désigne un certificat. Démontrer l'inclusion RPNP revient à utiliser A comme vérifieur, et à remarquer que, lorsque xL :

    proba [ A (x, r) = 1 ] > λ > 0 ⇒ ∃r A (x, r) = 1

    tandis que réciproquement, comme on l'a remarqué ci dessus, on a :

    A (x, r) = 1 ⇒ xL.

  2. 5 points. Montrons d'abord ZPPRP. Soit L un langage dans ZPP, et A un algorithme probabiliste polynomial avec zéro erreur qui reconnaisse L ; on peut alors construire un nouvel algorithme B comme suit :

    B (x, r) = ì
    í
    î
    A (x, r) si A (x, r) = 0 ou 1
    0 si A (x, r) = 2

    Alors, si xL, A (x, r) vaut 1 ou 2, donc :

    proba [ B (x, r) = 1 ] = 1 - proba [ A (x, r) = 2 ] > 1 - λ

    Inversement, si x n'appartient pas à L, A (x, r) vaut 0 ou 2, donc B (x, r) = 0, ce qui achève de prouver LRP. On montre de la même façon ZPPco-RP : il suffit de choisir, ci-dessus, B (x, r) = 1 lorsque A (x, r) = 2.

    Reste à montrer, réciproquement, RPco-RPZPP. Soit L un langage dans RPco-RP, reconnu par deux algorithmes probabilistes polynomiaux A et B, correspondant aux définitions respectives de RP et co-RP ; en particulier, comme on l'a vu dans la réponse à la première question, les réponses A = 1 et B = 0 sont sûres, autrement dit :

    A (x, r) = 1 ⇒ x appartient à L
    B (x, r) = 0 ⇒ x n'appartient pas à L

    On peut alors construire un nouvel algorithme C comme suit :

    C (x, r) = ì
    ï
    í
    ï
    î
    0 si B (x, r) = 0
    1 si A (x, r) = 1
    2 si A (x, r) = 0 et B (x, r) = 1

    C fournit donc une réponse sûre lorsque celle-ci vaut 0 ou 1 ; reste à borner la probabilité de la réponse 2 ; supposons xL (l'autre cas est symétrique), d'où B (x, r) = 1, et :

    proba [ A (x, r) = 1 ] > λ

    proba [ C (x, r) = 2 ] = proba [ A (x, r) = 0 ] < 1 - λ