Forum de mathématiques - Bibm@th.net

Salut Golgup,
Au final, au niveau de l'implementation, qui se fait sur des machines, dont les entiers sont codés sur 32 bits (ou 64) on finit toujours par faire de "l'arithmétique modulaire".
Mais les problèmes en eux-même n'y font pas forcement appel : Subset-sum n'y fait pas appel, et de nombreux problèmes NP-complets non plus.

Qu'est-ce qui t'embête tant ?
++

Salut Golgup,
invoqué par yoshi me voici ...
Par contre je ne comprend pas ce que tu voulais dire par "l'arithmétique modulaire" ?

La page wikipédia est plus complète en anglais (as usual) :
http://en.wikipedia.org/wiki/One-way_function
Mais pour bien comprendre la notion de fonction à sens unique, il est nécessaire d'avoir des notions de complexité (savoir ce que sont les classes de complexité P et NP au minimum) mais ce sont des notions relativement compliquées (enseignées en L2/L3 Math-Info ?). Et alors on se rend compte qu'il y a plein d'autres fonctions à sens unique, cf sections :
* Discrete Logarithms : là il faut des notions sur les groupes et les corps finis (largement hors-programme jusqu'au bac) et éventuellement les courbes elliptiques (ces dernières étant largement hors programme jusqu'à bac+2/3 au minimum)
* et Other Candidate : là il faut des notions de complexité

En attendant, pour essayer de te résumer/vulgariser la situation, tu peux lire l'article en te disant que P (ou FP) c'est ce qui est facile à faire et que NP-complet (ou FNP-complet) c'est présumé difficile (en tout cas, on ne sait pas à quel point c'est facile, et la personne qui le dira peut réclamer 1 000 000$ à l'institut Clay).
Voici une tentative d'explication des quelques fonctions à sens uniques listés
* la factorisation des nombres premiers (facile de calculer un produit, difficile de factoriser) (donne lieu à RSA)
* la racine carrée dans Z/nZ (facile de faire le carrée modulo n, difficile de prendre la racine carrée modulo n)
* log discret sur les Z/pZ avec p très grand (donne lieu à Diffie-Hellman)
on fixe a et on pose f(x) = a^x (mod p), la fonction f est à sens unique car il est facile de calculer f(x) par exponentiation rapide, mais très difficile étant donné b de trouver x tel que f(x) = b (mod p)).
NB : En fait, on peut le généraliser à des "groupes" bien choisis.
* Problème SUBSET-SUM : Étant donné un ensemble d'entier relatifs et k, existe t'il un sous-ensemble dont la somme des éléments est égale à k, si oui, lesquels doit on prendre ? (La fonction à sens unique sous jacente prend en argument un ensemble et nous donne le sous ensemble qui convient, s'il existe)
(cf http://en.wikipedia.org/wiki/Naccache-S … ptosystem)
* D'autres problèmes NP-Complets, sur lesquels tu peux toujours tenter de te documenter.

++

Bonsoir,

Peut-être quelques éléments de réponse :
http://www.cryptage.org/cle-publique.html
http://fr.wikipedia.org/wiki/Fonction_% … ens_unique
http://www.developpez.net/forums/archiv … 20046.html

Barbichu t'en dirait probablement plus et mieux..

@+