Fais une recherche sur « treewidth » (c'est un truc définit par N. Robertson et P.D. Seymour) puis sur « Bruno Courcelle » et « monadic second-order logic ».
En gros, on peut définir à quel point un graphe ressemble à un arbre. Un graphe complet, ça ne ressemble pas du tout à un arbre mais un truc plus « filandreux » si. Pour mesurer ça, on définit la treewidth d'un graphe. Tout graphe à une treewidth donnée. Savoir si un graphe G est de treewidth k est NP-complet.
Il y a des théorèmes qui disent que tout problème sur des graphes qui s'exprime en logique monadique du second ordre est linéaire sur une classe de graphe de treewidth bornée. En gros, la complexité est de l'ordre de O(n*2^k). Alors évidemment, ça fait joli mais il existe évidemment des graphes de taille n ayant une treewidth de l'ordre de n ce qui réduit beaucoup l'interet de ce genre d'approche.
Et pour revenir sur tes problèmes de chiffrement, rien que pour le problème de factorisation, il faut faire très gaffe. Il y a des algos qui marchent très bien quand il y a des facteurs petits, il y en a d'autre qui marchent très bien quand les facteurs sont de taille comparable... Bref, pour choisir une clef RSA qui ne se casse pas très vite, c'est pas évident du tout.
[^] # Re: Comparaison de neuf langages sur un micro-benchmark
Posté par fmaz fmaz . En réponse à la dépêche Comparaison de neuf langages sur un micro-benchmark. Évalué à 2.
Fais une recherche sur « treewidth » (c'est un truc définit par N. Robertson et P.D. Seymour) puis sur « Bruno Courcelle » et « monadic second-order logic ».
En gros, on peut définir à quel point un graphe ressemble à un arbre. Un graphe complet, ça ne ressemble pas du tout à un arbre mais un truc plus « filandreux » si. Pour mesurer ça, on définit la treewidth d'un graphe. Tout graphe à une treewidth donnée. Savoir si un graphe G est de treewidth k est NP-complet.
Il y a des théorèmes qui disent que tout problème sur des graphes qui s'exprime en logique monadique du second ordre est linéaire sur une classe de graphe de treewidth bornée. En gros, la complexité est de l'ordre de O(n*2^k). Alors évidemment, ça fait joli mais il existe évidemment des graphes de taille n ayant une treewidth de l'ordre de n ce qui réduit beaucoup l'interet de ce genre d'approche.
Et pour revenir sur tes problèmes de chiffrement, rien que pour le problème de factorisation, il faut faire très gaffe. Il y a des algos qui marchent très bien quand il y a des facteurs petits, il y en a d'autre qui marchent très bien quand les facteurs sont de taille comparable... Bref, pour choisir une clef RSA qui ne se casse pas très vite, c'est pas évident du tout.