Décomposition de nombres type RSA

[invitebd020be0]

Les nombres de type RSA sont le produits de deux nombres premiers. J'avais pensé à un algorithme (faisable à la main pour les petits nombres) qui extrait ces deux nombres. Le seul problème, c'est que je ne sais pas s'il marche vraiment, et si c'est le cas, je ne sais pas s'il est potable niveau temps de calcul. Cette idée m'est venue un peu par hasard, j'essayais de me souvenir de l'algorithme de Héron pour extraire la racine carrée d'un nombre. Mon idée était de prendre un nombre RSA (ça ne marche pas si le nombre est un produit de plus de deux nombres premiers) et de trouver quel était son carré le plus proche : par exemple 187 est le produit de deux nombres premiers, 14² = 196 est le carré le plus proche.

Ainsi, on part de

14*14 > 187

donc on considère

14* (14-1) = 14*13 = 182 < 187

Puis, comme le nombre devient trop petit, on considère :

(14+1) * 13 = 15*13 = 195 > 187

Puis :

15*12 = 180 < 187

Et :

16*12 = 192 > 187
...
16*11 = 176 < 187
...
17*11 = 187 ! 17 et 11 sont les facteurs recherchés !

A la main, ça prend du temps, mais je pense qu'un ordinateur est tout à fait capable d'effectuer ces calculs simples très rapidement. C'est une hypothèse. Comme ce genre d'algorithme a probablement dû être inventé bien avant ma naissance, je le poste pas pour savoir si j'ai tort, mais pour savoir où j'ai tort ! Vous pensez qu'un tel algorithme permettrait de déterminer rapidement les deux facteurs d'un RSA ? J'ai pas encore essayé de le programmer sous Maple, mais je vais tenter. Bien que cela me semble hors d'atteinte, vu mon niveau actuel.

Bonne année !
-----

[sadben2004]

Il faut avoir un algo performant pour trouver le carré le plus proche.
Pour la complexite il faut voir le pire cas qui est je pense 2*p avec p premier.
Il faudra aussi demontrer mathemtiquemnt que ca converge tout le temp

[invitebd020be0]

( Avant ton edit : Oui, mais dans ce genre de cas, je fais 5*5 = 25
Puis
4*6 = 24 < 25 (en fait, il faut à chaque fois comparer 4*5, 4*6 ou 5*4... regarder lequel est le plus proche)

4*7 = 28 > 25

3*7 = 21 < 25

3*8 = 24 < 25

3*9 = 27 > 25

2*9 = 18 < 25

2*10 = 20 < 25

2*11 = 22...

Il faut juste à chaque fois comparer quelle est l'opération qui donne le resultat le plus proche (pour la première opération à effectuer, en tout cas...) : si a² > RSA => Soit on fait (a-1)*a soit (a-1)*(a+1)...

Ensuite, je crois que l'algorithme reste le même... Merci en tout cas d'avoir partagé ton impression. )

Effectivement, il y a encore des choses à prouver. Trouver le carré le plus proche : E(sqrt(RSA)) avec E() la partie entière suffira (enfin, à discuter si c'est celui au dessus, ou au dessous). Ensuite, niveau complexité : 2*p cela me semble incroyablement plus rapide que les autres ! Enfin, je me trompe sans doute

[sadben2004]

Si j'ai bien saisi l'algo il ne converge pas dans ce cas :

22= 2*11

1- 5*5
2- 5*4
1- 6*4
2- 6*3
1- 7*3
2- 7*4
1- 6*4 ...
2-

[A voir en vidéo sur Futura]

[invitebd020be0]

Non car tu passes de 7*3 à 7*4 alors que le plus proche est 7*3 puis 8*3...

[sadben2004]

pardon, j'ai mal compris ton algo, j'ai cru que tu alternais le facteur à modifier à chaque pas.

[invitebd020be0]

Enfin, quoiqu'il en soit, j'aimerai étudier la vitesse de convergence, car je pense que fatalement la suite converge. Je l'espère en tout cas. Le programme est assez compliqué à rédiger (j'ai aps encore essayé) car il implique que je sois moi-même bien sûr de l'algo et de comment il fonctionne. Déjà, si sa vitesse de convergence n'est pas si élevée que ça, même au niveau théorique, ça représenterait pas quelque chose de très important. Enfin, c'est toujours ça... Bon réveillon !

[invite82d14e21]

Enfin, quoiqu'il en soit, j'aimerai étudier la vitesse de convergence, car je pense que fatalement la suite converge. Je l'espère en tout cas. Le programme est assez compliqué à rédiger (j'ai aps encore essayé) car il implique que je sois moi-même bien sûr de l'algo et de comment il fonctionne. Déjà, si sa vitesse de convergence n'est pas si élevée que ça, même au niveau théorique, ça représenterait pas quelque chose de très important. Enfin, c'est toujours ça... Bon réveillon !

C'est une méthode connue, mais hélas à peine plus efficace que le test de la division.
Pour te donner une idée de la difficulté de rechercher la factorisation du produit de 2 nombres premiers de 100 chiffres, c'est à dire un nombre qui fait au moins 200 chiffres, il faut tester la division de 2 à racine carrée du produit. As tu une idée du nombre d'opérations que ça représente ? Bien plus que le nombre d'électrons dans l'univers!
De même, pour l'instant, on ne sait pas mémoriser les nombres premiers, il y en a bien trop. Les algorithmes ne s'en servent pas. Juste, on sait trouver des grands nombres premiers de la forme 2^n+1, par une méthode qui allège le nombre de tests.
RSA a encore beaucoup de marge avant de pouvoir être décryté.

[invitebd020be0]

D'accord, je comprends, même si je vois pas trop pourquoi l'algorithme est long, car si le nombre fait 100 chiffres, ça fait 100*10(nombres de chiffres de 0 à 9)*2(pour les deux nombres) = 2000 opérations, non ? Après c'est juste des tests !
Sinon, c'est hyper interessant, pour le reste de ce que tu disais... Merci encore

[invite82d14e21]

D'accord, je comprends, même si je vois pas trop pourquoi l'algorithme est long, car si le nombre fait 100 chiffres, ça fait 100*10(nombres de chiffres de 0 à 9)*2(pour les deux nombres) = 2000 opérations, non ? Après c'est juste des tests !
Sinon, c'est hyper interessant, pour le reste de ce que tu disais... Merci encore

Non, pas 2000 opérations. La racine carrée d'un nombre de 200 chiffres est un nombre d'environ 100 chiffres. Un nombre de 100 chiffres est indénombrable dans la nature!

[invitebe0cd90e]

Pour preciser la reponse de Nogdim : Ce qui fait marcher ton algo c'est l'idée suivante, assez evidente : Si un nombre est le produit de 2 facteur, exactement l'un d'entre eux est inferieur (ou egal) a la racine carré du nombre a factoriser.

Un algorithme hyper naif de factorisation d'un entier N est de tester tous les nombres inferieurs a N. La remarque ci dessus permet de se restreindre aux entiers inferieurs a racine de N, ce qui est mieux mais pas tellement.

Sauf erreur de ma part, ta methode revient donc a tester toutes ces possibilités en partant "de la fin" plutot que du debut, ce qui est naturel puisque dans un nombre RSA on imagine que les facteurs sont du meme ordre. Donc en pratique c'est sans doute a peine plus rapide, mais la complexité theorique reste la meme. Dans las algos sur les entiers, ce qui compte c'est le nombre de chiffre, pas le nombre lui meme. Si N a k chiffres dans son ecriture en binaire, la complexité de ton algo est donc a la louche ce qui est enorme. C'est une complexité exponentielle donc impraticable pour de grands nombres.

Les meilleurs algos connus sont de complexité sous-exponentielle, si je ne m'abuse, ce qui est bien mieux, mais loin d'etre suffisant.

[invitebe0cd90e]

Note que tu touches quand meme a une faiblesse de RSA : si les 2 facteurs sont "trop proches", ce qui peut arriver si on implemente cet algorithme de facon trop naive, alors il me semble qu'il existe une methode efficace pour factoriser le nombre, mais mes souvenirs sont flous. Ceci confirme qu'en crypto encore plus qu'ailleurs, le passage de l'algo theorique a une implementation effective est très delicate.