Les fabuleuses aventures des nombres premiers

Articles GZ
1

Un des plus vieux problèmes de complexité algorithmique vient de tomber. Des chercheurs indiens ont trouvé une procédure efficace pour déterminer à coup sûr si un nombre est premier ou pas. Toutes les méthodes connues jusqu’à présent étaient soit probabilistes (elles ne donnent le bon résultat qu’avec une certaine probabilité), soit pas efficaces du tout (c’est-à-dire qu’elles nécessitent un temps de calcul qui augmente exponentiellement avec la taille du nombre à tester). Le plus étonnant est que l’algorithme en lui-même tient en 13 lignes, et fait appel à des notions pas trop compliquées (enfin pour des mathématiciens ;)).
Par contre, le problème de la factorisation est toujours ouvert. On ne sait pas à l’heure actuelle s’il existe une méthode efficace pour décomposer n’importe quel nombre en produit de nombres premiers. Enfin, sur un ordinateur classique, parce qu’en informatique quantique, il existe un tel algorithme, découvert en 1994, et implémenté récemment sur un petit nombre (voir <a href=http://www.cafzone.net/modules.php?op=modload&name=News&file=article&sid=590>cette news).

L’article original ici.

ndCaf : ça me rappelle que vraiment, j’adore la bouffe indienne (pas trop épicée, faut pas déconner non plus). Mais les maths, ça reste un autre problème…

2

J’ai eu peur, j’ai cru qu’on allait foutre RSA et consort au placard :slight_smile: bon on peux encore crypter tranquille :frowning: oui parce que bon meme en informatique quantique, factoriser un nombre de 256 bits, et meme 128, cé pas demain la veille :frowning:

3

je veux pas facher les matheux, mais à part pour la performance en elle-meme, ça sert à quelque chose de chercher les nombres premiers?

4

ouais ça sert à faire de la crypto par exemple RSA/PGP est basé sur des gros nombres premiers

(genre à 200 chiffres dans la vraie vie)

5

Bah et alors tu nous as pas mis le détail de l’algorithme expliqué ? Tsss :slight_smile:

6

Va voir l’article et d/l le pdf… attention c’est en anglais et faut etre un minimum matheux de feu (je suis en TS et j’ai bcp de mal a le comprendre)

7

ok merci pour l’info :slight_smile:

8

Tu pourras pas => il y a des notions de polynôme, par exemple, que tu n’as pas enore vu (non, les polynômes que tu vois au lycée, c’est pas des polynômes, c’est des fonctions polynomiales sur R, rien à voir (enfin si, mais c’est bq plus restreint)

9

Ca permet aussi de peaufiner les algos de multiplication de grands nombres, qui servent dans pas mal d’applis scientifiques (météo par exemple)

10

Hu, « vient de tomber » ?

Ca date un peu de l’été dernier ca :stuck_out_tongue:

11

L’arithmétique est actuellement la branche des mathématiques qui offre le plus d’applications concrètes, notamment dans l’informatique (calcul en base n, cryptage, algorithmique).

Et la décomposition d’un nombre en nombre premiers est effectivement à la base des cryptages actuels, comme le RSA. Si tu trouves un algorithme qui décompose n’importe quel nombre en peu de temps, tu es riche et célèbre du jour au lendemain (et accessoirement toutes les transmissions sur Internet seront à revoir :stuck_out_tongue: )

C’était la minute culturelle du jour…

12

Pfff, ces blasés, j’y crois pas… Dès que ça date pas de la veille c’est déjà vieux :stuck_out_tongue:

Et puis bon, pour les preuves mathématiques il y a toujours un temps de vérification qui va derrière, histoire de voir si les gars se sont pas plantés.

13

“Si tu trouves un algorithme qui décompose n’importe quel nombre en peu de temps, tu es …”

mort ! pourchassé par toutes les cia de la planète;

bon j’ai quand même un scénario pour se tirer d’affaire, restons positifs, donc s’il

y a qq’un qui trouve ici qu’il me contacte ;))