Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 14-07-2008 16:43:59
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Fonctions à sens unique?
Bonjour,
Existe t-il des fonctions à sens unique autres que l'arithmétique modulaire? Je me suis déja rensseigner mais sans succés..
Merci.
++
« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »
Hors ligne
#2 14-07-2008 19:02:29
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 993
Re : Fonctions à sens unique?
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..
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#4 15-07-2008 04:29:10
- Barbichu
- Membre actif
- Inscription : 15-12-2007
- Messages : 405
Re : Fonctions à sens unique?
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.
++
Dernière modification par Barbichu (15-07-2008 04:30:33)
Barbichu
Hors ligne
#5 15-07-2008 16:04:46
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Re : Fonctions à sens unique?
Salut,
* 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)).
Mais tous sa repose bien sur l'arithmétique modulaire? non? (modX)
Dernière modification par Golgup (15-07-2008 16:06:20)
« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »
Hors ligne
#6 23-07-2008 11:28:00
- Barbichu
- Membre actif
- Inscription : 15-12-2007
- Messages : 405
Re : Fonctions à sens unique?
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 ?
++
Barbichu
Hors ligne
Pages : 1