Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 32

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



  1. #1
    V5bot

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

    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

  2. Publicité
  3. #2
    Noress

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

    " 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.

  4. #3
    CM63

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

    Bonjour,

    Et c'est quoi le principe?

  5. #4
    Noress

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

    "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
    Dernière modification par JPL ; 02/05/2016 à 13h33. Motif: Activation du lien

  6. A voir en vidéo sur Futura
  7. #5
    Schrodies-cat

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

    Citation Envoyé par Noress Voir le message
    (...)
    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.
    Il n'est pire sot que qui ne veut pas comprendre .

  8. #6
    fredegaire

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

    Citation Envoyé par Noress Voir le message
    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.

  9. Publicité
  10. #7
    Noress

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

    Bonjour,

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

    Propriétés de S :
    sn, smsn, alors snsm=.
    sn, sm, si snsm, alors sn=sm.

    Soit q1 Q, l'ensemble des questions dont la solution est dans s1.
    s1 reconnaît q1 dans la solution qu'il présente.
    qiq1, s1 présente une non solution absolue.

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

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

  11. #8
    Schrodies-cat

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

    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.
    Il n'est pire sot que qui ne veut pas comprendre .

  12. #9
    Schrodies-cat

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

    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.
    Il n'est pire sot que qui ne veut pas comprendre .

  13. #10
    Schrodies-cat

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

    Ou alors vous avez posté dans le mauvais fil ?
    Cela arrive.
    Car ici c'est plutôt hors-sujet.
    Il n'est pire sot que qui ne veut pas comprendre .

  14. #11
    Noress

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

    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. ????
    Dernière modification par Noress ; 07/05/2016 à 23h14.

  15. #12
    Noress

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

    Citation Envoyé par Schrodies-cat Voir le message
    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.

  16. Publicité
  17. #13
    Noress

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

    Et ça continue à se dupliquer....

  18. #14
    Noress

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

    Citation Envoyé par Schrodies-cat Voir le message
    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.

  19. #15
    vgondr98

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

    Citation Envoyé par Noress Voir le message
    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
    Citation Envoyé par Noress Voir le message
    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).

  20. #16
    Noress

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

    Citation Envoyé par vgondr98 Voir le message
    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.

  21. #17
    Noress

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

    Citation Envoyé par vgondr98 Voir le message
    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.

  22. #18
    Noress

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

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

  23. Publicité
  24. #19
    JPL
    Responsable des forums

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

    Le sudoku n'a rien à faire dans cette discussion.
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  25. #20
    Noress

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

    Citation Envoyé par JPL Voir le message
    Le sudoku n'a rien à faire dans cette discussion.
    Désolé je suis pourtant dans la bonne discussion

  26. #21
    JPL
    Responsable des forums

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

    Il y a quelque chose que je ne comprends pas : les messages se dupliqueraient dans deux discussions différentes ?
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  27. #22
    Noress

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

    Citation Envoyé par JPL Voir le message
    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.

  28. #23
    JPL
    Responsable des forums

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

    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).
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  29. #24
    Noress

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

    Citation Envoyé par Noress Voir le message
    qiq1, s1 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.

  30. Publicité
  31. #25
    Deedee81
    Modérateur

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

    Salut,

    Citation Envoyé par JPL Voir le message
    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.
    Keep it simple stupid

  32. #26
    Noress

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

    Citation Envoyé par Deedee81 Voir le message
    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".
    Dernière modification par Noress ; 11/05/2016 à 12h02.

  33. #27
    Deedee81
    Modérateur

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

    Citation Envoyé par Noress Voir le message
    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.
    Keep it simple stupid

  34. #28
    Noress

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

    qiq1, s1 présente une non solution absolue.

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

  35. #29
    Schrodies-cat

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

    Citation Envoyé par JPL Voir le message
    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.
    Il n'est pire sot que qui ne veut pas comprendre .

  36. #30
    Noress

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

    Citation Envoyé par Noress Voir le message
    s1 a une taille de 17 118 octets.
    Son temps de résolution en fonction de la difficulté de q1 (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 s1 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-s1 (b)........................... .............14 351........................... .....................14 929........................... .............................. .......17 584
    s1.............................. ...................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 s1.
    (b) (F-s1) 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 s1 (ce que je ne promet pas) ?

Page 1 sur 2 1 DernièreDernière