Actualité - En bref : un nouvel algorithme déjoue les systèmes de cryptographie

[V5bot]

Dans une étude récente, des chercheurs du CNRS ont réussi à déjouer le logarithme discret, l’un des systèmes de protection les plus difficiles à résoudre. Ce travail permet d'ores et déjà de...

Lire la suite : En bref : un nouvel algorithme déjoue les systèmes de cryptographie

[Noress]

" sa complexité est bien meilleure : ceci signifie qu'il est à même de résoudre des problèmes de logarithmes discrets de plus en plus grands, en voyant son temps de calcul croître beaucoup plus modérément."

Bonjour,
Dans l'hypothèse d'un algorithme NP complet, est-il raisonnable d'envisager un temps NP d'exécution constant lorsque le problème NP complet traité croît en difficulté ? Merci.

[CM63]

Bonjour,

Et c'est quoi le principe?

[Noress]

"Et c'est quoi le principe?"

Bonjour il y a plus de détails dans la discussion suivante :

http://forums.futura-sciences.com/mathematiques-superieur/737033-temps-np.html

[A voir en vidéo sur Futura]

[Schrodies-cat]

(...)
Bonjour,
Dans l'hypothèse d'un algorithme NP complet, est-il raisonnable d'envisager un temps NP d'exécution constant lorsque le problème NP complet traité croît en difficulté ? Merci.

Je vous ai fait quelques remarques ici
Évitez je vous prie les répétions qui me forcent à me répéter.

[fredegaire]

Bonjour,
Dans l'hypothèse d'un algorithme NP complet, est-il raisonnable d'envisager un temps NP d'exécution constant lorsque le problème NP complet traité croît en difficulté ? Merci.

Bonjour.

Je crois que tu devrais d'abord lire des choses (il doit sûrement y avoir des articles dans Wikipedia) pour comprendre un peu le sens des mots. Parce que tout ce que tu écris n'a aucun sens :
- C'est un problème qui peut être NP-complet, un algorithme NP-complet ça ne veut rien dire
- NP ne désigne pas un temps d'exécution, mais une classe de complexité
- Un problème NP-complet ne "croît pas en difficulté", c'est le temps de résolution qui croît en fonction de la taille de la variable

Bref, si tu veux discuter de cette question, il va falloir commencer par travailler de ton côté. Mais c'est intéressant, bon courage.

[Noress]

Bonjour,

Considérons le problème du sudoku généralisé.
Soit S, l'ensemble des familles (s_i) de solutions. Chaque s_i compte 362 880 solutions.
Soit Q l'ensemble des questions admettant chacune une et une seule solution dans S.

Propriétés de S :
s_n, s_ms_n, alors s_ns_m=.
s_n, s_m, si s_ns_m, alors s_n=s_m.

Soit q₁ Q, l'ensemble des questions dont la solution est dans s₁.
s₁ reconnaît q₁ dans la solution qu'il présente.
q_iq₁, s₁ présente une non solution absolue.

s₁ a une taille de 17 118 octets.
Son temps de résolution en fonction de la difficulté de q₁ (sudoku facile, moyen, difficile, diabolique...) ne peut être que constant.

J'espère être compréhensible.
Cordialement, Merci.

[Schrodies-cat]

Le problème du Sudoku généralisé:
Le Sudoku sa joue habituellement sur une grille 9*9, on peut le jouer sur une grille m*m ou m est un carré .
On peut donc considérer la complexité du problème en fonction de la taille de la grille (et donc des données).
Vous avez l'air de confondre taille des données et complexité de l'algorithme ou du problème qui parle du temps (en fait le nombre d'opérations élémentaires) qu'il faut pour résoudre le problème.

[Schrodies-cat]

Vous avez déja posé la même question ici :
http://forums.futura-sciences.com/ma...-temps-np.html
Ce genre de procédé est des plus irritants pour ceux qui s'efforcent de vous répondre.

[Schrodies-cat]

Ou alors vous avez posté dans le mauvais fil ?
Cela arrive.
Car ici c'est plutôt hors-sujet.

[Noress]

Bonsoir,
C'est assez incompréhensible, je ne suis resté que sur cette invitation et je vois que cela se duplique sur : En bref : un nouvel algorithme déjoue les systèmes de cryptographie. C'est assez gênant. Et même les votre son dupliqués. ????

[Noress]

Vous avez déja posé la même question ici :
http://forums.futura-sciences.com/ma...-temps-np.html
Ce genre de procédé est des plus irritants pour ceux qui s'efforcent de vous répondre.

Je ne vois rien sur Temps NP vous confondez avec les commentaires au bas de l'article http://www.futura-sciences.com/magaz...graphie-53698/
Ce serait bien d'effacer tout ça si vous le pouvez merci.

[Noress]

Et ça continue à se dupliquer....

[Noress]

Le problème du Sudoku généralisé:
Le Sudoku sa joue habituellement sur une grille 9*9, on peut le jouer sur une grille m*m ou m est un carré .
On peut donc considérer la complexité du problème en fonction de la taille de la grille (et donc des données).
Vous avez l'air de confondre taille des données et complexité de l'algorithme ou du problème qui parle du temps (en fait le nombre d'opérations élémentaires) qu'il faut pour résoudre le problème.

Justement, l'algorithme s1 ne comporte strictement aucune opération élémentaire (c'est toute sa particularité) pour m=9 et il en sera de même pour m=16, m=25 etc... ce qui signifie que le temps de la vérification de la solution du problème sera toujours plus longs que celui de sa résolution.
Merci.

[vgondr98]

Justement, l'algorithme s1 ne comporte strictement aucune opération élémentaire (c'est toute sa particularité) pour m=9 et il en sera de même pour m=16, m=25 etc... ce qui signifie que le temps de la vérification de la solution du problème sera toujours plus longs que celui de sa résolution.
Merci.

Peux-tu expliquer plus clairement ?

Déjà, j'ai du mal avec cette phrase

Son temps de résolution en fonction de la difficulté de q1 (sudoku facile, moyen, difficile, diabolique...) ne peut être que constant.

En effet, dans ma logique, un sudoku "ultra facile" (80 cases remplies et 1 case vide) est beaucoup plus rapide à résoudre qu'un sudoku "diabolique" (le nombre de cases remplies minimums et admettant une solution unique).

[Noress]

Peux-tu expliquer plus clairement ?

Déjà, j'ai du mal avec cette phrase

En effet, dans ma logique, un sudoku "ultra facile" (80 cases remplies et 1 case vide) est beaucoup plus rapide à résoudre qu'un sudoku "diabolique" (le nombre de cases remplies minimums et admettant une solution unique).

Oui, dans la logique je suis entièrement d'accord avec toi un sudoku facile se résout plus rapidement qu' un sudoku difficile (64 case vides). Cependant je ne passe pas par l'utilisation des opérations élémentaires. Mon approche repose sur la connaissance dans la définition d'un ensemble de solution incomplète qui m'a permis de développer cet d'algorithme (s1) qui contourne les opérations élémentaires. Et donc le seul indicateur reste la taille de ce même algorithme. Le plus troublant est que à vide cet algorithme à une taille de 17 118 octets, et que donc pour un sudoku de 64 cases vide sa taille sera plus petite que pour un sudoku facile.

[Noress]

Peux-tu expliquer plus clairement ?

Mais tout est dit : s1 ne fonctionne pas à l'aide d'opérations élémentaire. Et comme la vérification de la solution passe par l'utilisation d'opérations élémentaires, le temps de résolution sera toujours plus court que celui de la vérification.

[Noress]

Je sent que ça va être rude là !!!

[JPL]

Le sudoku n'a rien à faire dans cette discussion.

[Noress]

Le sudoku n'a rien à faire dans cette discussion.

Désolé je suis pourtant dans la bonne discussion

[JPL]

Il y a quelque chose que je ne comprends pas : les messages se dupliqueraient dans deux discussions différentes ?

[Noress]

Il y a quelque chose que je ne comprends pas : les messages se dupliqueraient dans deux discussions différentes ?

Il semble que oui. Pour ma part je ne suis qu'ici.

[JPL]

Du coup, comme je n'ai pas suivi cette discussion de façon très attentive j'ai parfois du mal à savoir de quoi parlent certains messages (ceux qui sont hors sujet ou non).

[Noress]

q_iq₁, s₁ présente une non solution absolue.

Je vous prie de m'excuser mais j'ai un doute sur ce passage que j'ai dois peut-être clarifier.

[Deedee81]

Salut,

Il y a quelque chose que je ne comprends pas : les messages se dupliqueraient dans deux discussions différentes ?

Non. Si je suis les liens indiqués ci-dessus c'est la même discussion, mais en accédant soit par Futura Forum soit via les actualités.
Une confusion bien compréhensible.

P.S. je ne juge pas sur le sudoku qui serait HS ou pas, je n'ai pas lu assez en détail l'actu et les messages.

[Noress]

Salut,



Non. Si je suis les liens indiqués ci-dessus c'est la même discussion, mais en accédant soit par Futura Forum soit via les actualités.
Une confusion bien compréhensible.

P.S. je ne juge pas sur le sudoku qui serait HS ou pas, je n'ai pas lu assez en détail l'actu et les messages.

Bonjour
En effet, toute la discussion se duplique sur la lien suivant : http://www.futura-sciences.com/magaz...graphie-53698/
Dans la zone "Commentaire".

[Deedee81]

En effet, toute la discussion se duplique sur la lien suivant :

Non, non, j'insiste. Ce n'est pas une duplication. C'est LA discussion. Mais vue par deux interfaces différentes.

C'est comme voir un fichier dans l'explorateur windows ou bien avec un DIR dans une boite Dos. C'est le même fichier, pas une duplication.

[Noress]

q_iq₁, s₁ présente une non solution absolue.

Il n'y a pas doute, l'expression est maintenue.

[Schrodies-cat]

Du coup, comme je n'ai pas suivi cette discussion de façon très attentive j'ai parfois du mal à savoir de quoi parlent certains messages (ceux qui sont hors sujet ou non).

Vous avez vu des messages qui ne fussent pas hors sujet ?

Il y a la question : que signifie la "complexité d'un problème", mais le sujet est sur une question particulière de cryptographie.

[Noress]

s₁ a une taille de 17 118 octets.
Son temps de résolution en fonction de la difficulté de q₁ (sudoku facile, moyen, difficile, diabolique...) ne peut être que constant.

Ce passage est complètement faux.
En effet, c'est le fichier (F) qui contient s₁ qui a une taille de 17 118 octets. Toutes les valeurs ci dessous sont en Octet.

M=9.............................. ................à vide.............................. ........72 cases vides (a)........................... .........................1 case vide
F.............................. ....................17 118........................... .....................17 149........................... .............................. ......19 648
F-s₁ (b)........................... .............14 351........................... .....................14 929........................... .............................. .......17 584
s₁.............................. ...................2 767........................... ........................2 220........................... .............................. ..........2 064

(a) Un sudoku de ce type (9 cases remplies par 1, 2, 3, 4, 5, 6, 7, 8, et 9) admet certes plusieurs solutions mais c'est juste pour la mesure de s₁.
(b) (F-s₁) correspond à la solution de l'algorithme sans ce dernier (copier coller valeur).
Si cette mesure s'avère recevable, alors la logique de vgondr98 est vrai (et donc toutes mes excuses).
Cela dit, pour être éclairé sur la délicate question de la complexité nous faut-il des mesures analogues pour m=4 et m=16 et assiter par là-même à la non explosion de la taille de s₁ (ce que je ne promet pas) ?