Moi et P=NP

Aller en bas

Moi et P=NP

Message par ☘fishcake☘ le Ven 6 Mai 2016 - 5:27

Avant de commencer mon blabla je tiens à vous dire que j'essaie de vous rendre mes explications les plus simple possible.

je tiens aussi à préciser que dans ce poste mes recherches ne sont pas affichées en intégralité pour éviter les vols.

commençant par répondre à la question qu'est-ce qu'un problème p = NP?

c'est un problème de mathématiques théorique très important tellement qu'on la classer dans les prix millénaire ce qui fait que ce problème est mise à prix à un million d'euros. Les conséquences de P = NP pourraient être considérables dans de nombreux domaines : cryptologie, informatique, mathématiques, ingénierie, économie. Pour faire simple la classe p sont les calculs qui son résorbable par un ordi. la classe NP son ce que l'ordi ne peut pas résoudre. il y a ainsi des problèmes de la classe NP célèbre comme le problème du voyageur du commerce ou le problème de la clid.

Je préfère m'attarder dans ce poste sur un problème rencontrer dans les années 90: sur les craquage code RSA Security.

RSA Security et est une entreprise qui a fermé maintenant travailler dans le chiffrement RSA. Des chiffrement RSA son des vieilles façon de crypter des données informatiques. cette méthode est encore utilisée dans certains sites même si elle devient rare.

il lance ainsi un concours dans les années 90 pour inciter les chercheurs à s'intéresser à la cryptographie. la règle est simple. RSS security ne donne un chiffre nous devons trouver la multiplication qui donne le même chiffre. plusieurs de ces problèmes sont mises à prix. Ainsi par exemple si on trouve la multiplication qui donne :
 
Code:
25195908475657893494027183240048398571429282126204032027777137836043662020
70759555626401852588078440691829064124951508218929855914917618450280848912
00728449926873928072877767359714183472702618963750149718246911650776133798
59095700097330459748808428401797429100642458691817195118746121515172654632
28221686998754918242243363725908514186546204357679842338718477444792073993
42365848238242811981638150106748104516603773060562016196762561338441436038
33904414952634432190114657544454178424020924616515723350778707749817125772
46796292638635637328991215483143816789988504044536402352738195137863656439
1212010397122822120720357
Ont gagner 200000 euro.

ce concours n'existe plus car RSA Security à fermer ses portes mais de nombreux problèmes que RSA Security a inventé ne sont pas résolus à ce jour.

passons maintenant à moi et mes recherche perso.

Ma méthode pour résoudre les problèmes des RSA Security qui sont classés NP au passage. je parle bien sûr de faire résoudre ça a un ordinateur vous avez compris je pense et je précise pour rien.

un petit schéma avant de commencer car tout mon explication va se baser sur ce petit  schéma.



chercher le résultat de 68559 x 95684 avec une méthode assez particulière. c'est une méthode inventé par les Indiens elle se présente pas vraiment comme ça elle ressemblerait plutôt à ceci: Image

Sur le schéma les traits qui partent du bas vers le haut c'est le premier nombre et ce qui part du haut vers le bas et le deuxième nombre. Le nombre numéroter sur les traits montant est le premier chiffre du premier nombre. vous remarquerez que chaque chiffre du premier nombre se croisent avec chaque chiffre du second nombre en un point. Et que ces points sont alignés les uns au-dessus des autres séparer dans des colonnes.

Nous allons prendre la dernière colonne nous allons multiplié les chiffres qui se trouve comme dans l'opération noter 1. puis nous prenons la deuxième colonne on se retrouve avec deux intersections nous faisons la même chose et nous additionnant les intersections. ainsi de suite. nous voyons bien arrivé à la cinquième colonne que chaque chiffre est multiplié par chaque chiffre. nous reviendrons après sur ce dernier.

après nous allons additionner le premier chiffre par le dernier chiffres du second résulta en prenant compte des retenues.

1.36
1. 6 , 2. 95
1. 6 , 2. 5 , 3. 124
1. 6 , 2. 5 , 3. 3
je m'arrête là parce que on se retrouve face à une difficulté que je ne veux pas dévoiler pour ne pas qu'on mon vol ce problème, et il y a bien sûr une technique pour résoudre le problème quand on se retrouve à 3 chiffres mais je ne vais pas le dire désolé.

vous aurez remarqué qu'en faisant ça le résultats de la multiplication principales se dévoile petit à petit.

Maintenant pour faire à l'envers il suffit d'avoir un petit peu de bon sens. nous savons que quoi qu'il arrive le dernier chiffre du calcul 1 sera 6. Comme l'avant-dernier chiffre de la multiplication est un 5 il suffit de mettre un nombre qui en s'additionnent en donnera 5. comme 3. et il suffit de trouver une multiplication qui vaut 36. Je veux juste que vous pigé le truc alors je vais m'arrêter là. De toute façon arriver au milieu du résultat de la multiplication principal nous avons tous des chiffres dévoilés.  Après il suffit de programmer un logiciel qui fasse ça car cette façon de résoudre le problème se classe en P.

Des méthodes similaires basés aussi sur la mathématique indienne marcherait pour d'autres problèmes de la classe NP.

bien sûr de ou trois trucs en été mis de côté dans cette explication c'est tout simplement que je ne veux pas qu'on me pique mon idée.

mais si des personnes veulent m'aider dans mes recherches j'en serai ravie.

je vous souhaite une bonne journée.
☘fishcake☘
☘fishcake☘

Messages : 178
Date d'inscription : 15/09/2012
Age : 28
Localisation : Pau

Revenir en haut Aller en bas

Re: Moi et P=NP

Message par tim9.5 le Ven 6 Mai 2016 - 11:08

Voici quelques idées qui me viennent à l'esprit.
Un problème NP-complet, c'est résoudre Candy Crush rapidement.
Le temps de résolution est essentiel à calculer, car pour être NP, il doit être exponentiel à la donnée initiale. C'est pourquoi il y a un grand investissement dans l'informatique quantique pour s'attaquer à ce type de problèmes. En effet, augmenter la mémoire et le processeur d'un ordi en mode binaire ne suffit pas pour les NP-problèmes.

Ce sont aussi des problèmes faciles à résoudre pour autant qu'on ait accès à une clef de départ. Dès que j'ai le premier nombre, je peux trouver aisément le second, par simple division.
La manière de formuler ton problème est importante : il y a toujours une solution ! Laquelle ?
réponse:
1 fois le résutat !
En général on demande de travailler avec des nombres premiers. Sinon il suffit de tester des critères de divisibilité (par 2, par 3, par 5, etc) et le craking devient plus facile.
Un mathématicien théorique n'essayera pas forcément de résoudre le problème, mais se posera les questions suivantes : est-ce soluble ? en combien de temps ? peut-on le généraliser ? peut-on le classer dans un groupe de problèmes similaires ?
Par exemple, tous les problèmes NP-complet peuvent se réduire à un seul. Si quelqu'un donne une solution dans un temps humainement acceptable, les autres sont alors aussi résolus.

La méthode indienne est une méthode parmi d'autres pour multiplier deux nombres. Une calculatrice en utilise une autre pour trouver le résultat.

Le problème est plutôt la marche arrière. Je m'explique.
Mettre du lait dans du café est simple. La méthode pour y arriver est simple. C'est la marche avant. La marche arrière constiste à prendre du café au lait, et à séparer les deux entièrement. Avec 2 molécules mélangées, c'est facile. Avec 3, 4 aussi avec un peu de méthode qu'on peut généraliser.
Si c'est un pb NP-complet, on peut imaginer que le temps de résolution est de 2.7 fois 2 = 5.4 secondes pour deux molécules, ou 2.7 fois 2.7 fois 2.7. pour 3 molécules, mais 27000000000000000000000000000000000000000000 secondes pour 100 molécules seulement. (=e^100) Comme les ordis calculent "à l'aide de P en un temps exponentiel", le bug est là.

Exploser une tasse contre un mur est très facile à faire. Rassembler des millions de fragment pour trouver la tasse initiale (et le mur initiale) sans les connaître, c'est la marche arrière.

A mon avis, tu as intérêt à creuser la théorie NP-complet à fond, puis placer ton problème dans ce contexte dans les détails. Décrire entièrement la méthode (qui ne marche pas) avec une simple calculatrice pour bien comprendre les rouages.

Puis proposer le point de vue indien, et prouver que ça marche pour de petits exemples. Et finalement calculer le temps que ça prend pour l'exemple que tu as affiché, avec ta méthode. (Et arriver à un temps exponentiel, puisque c'est un problème NP-complet).

Heu, j'ai tout cassé, je crois (désolé  Crying or Very sad ) Mais c'est aussi la force des maths de décrire correctement des problèmes, sans être capable de les résoudre.
tim9.5
tim9.5

Messages : 305
Date d'inscription : 18/10/2014

Revenir en haut Aller en bas

Re: Moi et P=NP

Message par Invité le Ven 6 Mai 2016 - 11:39

Encore un génie incomprit qui en 3 lignes d'évidences va révolutionner des décennies de recherche de gens incomparablement plus compétent que lui...

Le coup du "c'est trop compliqué donc j'expliquerai pas", "je ne veux pas qu'on pique mon idée"... la base du troll scientifique...

Invité
Invité


Revenir en haut Aller en bas

Re: Moi et P=NP

Message par tim9.5 le Ven 6 Mai 2016 - 11:47

L'écouteur est jeune. Il réfléchit dans son coin et a des idées. Ca prend du temps de comprendre que nos réflexions scientifiques ne sont qu'une goutte dans un océean, non? Very Happy
tim9.5
tim9.5

Messages : 305
Date d'inscription : 18/10/2014

Revenir en haut Aller en bas

Re: Moi et P=NP

Message par Invité le Ven 6 Mai 2016 - 12:40

Si, mais un peu d'humilité c'est la base là dedans...

Invité
Invité


Revenir en haut Aller en bas

Re: Moi et P=NP

Message par ☘fishcake☘ le Ven 6 Mai 2016 - 12:56

tim9.5 > Pense qu'on a besoin de trouver une seule possibilité possible mais on peut aussi faire un champ de possibilités et les comparer suffirait largement.

hobb > bien sûr que je veux pas qu'on me pique mon idée. de toute façon j'ai donné un champ de possibilité pour pouvoir le résoudre je veux juste le faire avant ce qui me motive encore plus. et puis ça n'a rien de compliqué un mathématicien intermédiaires s'en sortirait avec ce type de résolution. Et le seul truc que j'ai pas dit c'est comment résoudre quand on a 3 chiffres. sérieux tu t'amuses à tourner le résultat dans tous les sens et tu arriveras au résultats toute façon. il suffit de prendre en compte des retenues comme tout calcul. je pense pas que c'est compliqué compliqué n'est pas là ce qui est compliqué c'est de le faire faire à un ordinateur. même quand je réfléchis un peu même si c'est la partie la plus compliqué je pense pas qu'elle ne sois pas résolvable. Je le répète il n'y a rien de compliqué. tu dois être plutôt littéraire parce que je vois pas ce que tu trouves de difficile là-dedans.
☘fishcake☘
☘fishcake☘

Messages : 178
Date d'inscription : 15/09/2012
Age : 28
Localisation : Pau

Revenir en haut Aller en bas

Re: Moi et P=NP

Message par tim9.5 le Ven 6 Mai 2016 - 20:05

Cher écouteur de silences,
Si j'ai bien compris, ton principal problème est de le faire faire à un ordinateur. Dans ce cas, tu peux utiliser le pascal http://www.programmation-pascal.com/.

Effectivement, Hobb a un côté littéraire car il écrit souvent sur ce forum. Tu peux lire le fil sur les oscillations. J'en profite de le remercier pour ses messages qui vont droit au but, et souvent très condensés. Il faut les lire plusieurs fois pour bien comprendre ce qui est dit. Comme en poésie.
tim9.5
tim9.5

Messages : 305
Date d'inscription : 18/10/2014

Revenir en haut Aller en bas

Re: Moi et P=NP

Message par Badak le Ven 6 Mai 2016 - 20:13

L'écouteur de silences a écrit:
hobb > bien sûr que je veux pas qu'on me pique mon idée. de toute façon j'ai donné un champ de possibilité pour pouvoir le résoudre je veux juste le faire avant ce qui me motive encore plus. et puis ça n'a rien de compliqué un mathématicien intermédiaires s'en sortirait avec ce type de résolution. Et le seul truc que j'ai pas dit c'est comment résoudre quand on a 3 chiffres. sérieux tu t'amuses à tourner le résultat dans tous les sens et tu arriveras au résultats toute façon. il suffit de prendre en compte des retenues comme tout calcul. je pense pas que c'est compliqué compliqué n'est pas là ce qui est compliqué c'est de le faire faire à un ordinateur. même quand je réfléchis un peu même si c'est la partie la plus compliqué je pense pas qu'elle ne sois pas résolvable. Je le répète il n'y a rien de compliqué. tu dois être plutôt littéraire parce que je vois pas ce que tu trouves de difficile là-dedans.

Désolé mais le problème de la factorisation, c'est compliqué. Puisque tu n'y trouves rien de compliqué, il se pourrait que tu te trompes.

En fait, juste prétendre que tu obtiens un algorithme en temps polynomial pour la factorisation, c'est douteux.
Je ne suis pas du tout spécialiste de la question, mais sur wiki, il est écrit que
L'ami wiki nous dit: a écrit: S’il peut être démontré qu'il est NP-Complet ou co-NP-Complet, cela impliquerait NP = co-NP. Ce serait un résultat très surprenant, par conséquent la factorisation entière est largement suspectée d'être en dehors de ces classes. Beaucoup de personnes ont essayé de trouver des algorithmes en temps polynomial pour cela et ont échoué ; par conséquent, ce problème est largement suspecté d'être également en dehors de P


Montrer que ton algortihme est dans P (si c'est le cas), ce n'est pas difficile en effet.
Tu peux prendre plusieurs ensembles de problèmes de taille croissante, et mesurer précisément la durée du calcul. Et ensuite faire le graphe de cette durée en fonction de la taille.
Mais il faut aussi faire attention à la quantité de mémoire: la mémoire doit aussi restée polynomiale. Si tu accélères les calcul en faisant exploser la mémoire nécessaire exponentiellement, ce n'est plus dans la classe P !!


Badak
Badak

Messages : 1138
Date d'inscription : 02/12/2011
Localisation : Montréal

Revenir en haut Aller en bas

Re: Moi et P=NP

Message par Invité le Ven 6 Mai 2016 - 20:49

L'écouteur de silences a écrit:tim9.5 > Pense qu'on a besoin de trouver une seule possibilité possible mais on peut aussi faire un champ de possibilités et les comparer suffirait largement.

hobb > bien sûr que je veux pas qu'on me pique mon idée. de toute façon j'ai donné un champ de possibilité pour pouvoir le résoudre je veux juste le faire avant ce qui me motive encore plus. et puis ça n'a rien de compliqué un mathématicien intermédiaires s'en sortirait avec ce type de résolution. Et le seul truc que j'ai pas dit c'est comment résoudre quand on a 3 chiffres. sérieux tu t'amuses à tourner le résultat dans tous les sens et tu arriveras au résultats toute façon. il suffit de prendre en compte des retenues comme tout calcul. je pense pas que c'est compliqué  compliqué n'est pas là ce qui est compliqué c'est de le faire faire à un ordinateur. même quand je réfléchis un peu même si c'est la partie la plus compliqué je pense pas qu'elle ne sois pas résolvable. Je le répète il n'y a rien de compliqué. tu dois être plutôt littéraire parce que je vois pas ce que tu trouves de difficile là-dedans.

Hé bien amuse toi avec les RSA720 qui tournent un peu partout sur le net alors... (PS : les gains obtenus en cas de factorisation ne sont plus acceptés depuis le PPMQ).

EDIT : la méthode qui est proposée ici, j'y ai déjà réfléchi, et en fait on reste en temps de calcul non polynomial (et mémoire non polynomiale non plus) : en gros, c'est pire que les méthodes existantes actuellement.

Invité
Invité


Revenir en haut Aller en bas

Revenir en haut


 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum