Test RSA
dans Arithmétique
Test de vulnérabilité des nombres RSA
Il existe un très grand nombre de nombres RSA utilisés au quotidien et accessibles au public.
Notons un nombre RSA "RSA"
Le test est le suivant :
Entrons A = 2*RSA
Calculons :
A = k^2+r1 (k est le plus nombre élevé au carré < à A et r1 le reste)
A’= (k+1)^2-r2
Calculons :
d1=k-r1
d2=k+1+r2
Si d1 et/ou d2 sont de la forme s*(s+1) autrement dit le produit de 2 nombres consécutifs A et/ou A’ seraient factorisables sous la forme :
A = (x^2+x+r1)^2+r1
A’= (x^2+x-r2)^2-r2
Ma question est simple : sur un milliard de nombres RSA combien seraient de cette forme?
Une sorte d’estimation probabiliste si l’on veut.
Merci
Il existe un très grand nombre de nombres RSA utilisés au quotidien et accessibles au public.
Notons un nombre RSA "RSA"
Le test est le suivant :
Entrons A = 2*RSA
Calculons :
A = k^2+r1 (k est le plus nombre élevé au carré < à A et r1 le reste)
A’= (k+1)^2-r2
Calculons :
d1=k-r1
d2=k+1+r2
Si d1 et/ou d2 sont de la forme s*(s+1) autrement dit le produit de 2 nombres consécutifs A et/ou A’ seraient factorisables sous la forme :
A = (x^2+x+r1)^2+r1
A’= (x^2+x-r2)^2-r2
Ma question est simple : sur un milliard de nombres RSA combien seraient de cette forme?
Une sorte d’estimation probabiliste si l’on veut.
Merci
Cette discussion a été fermée.
Réponses
Ecrit de la sorte $(x^2+x+r1)^2+r1$, ce nombre n'est pas un produit de facteurs car j'imagine que tu ne sous-entends pas que le produit dont tu parles est: $1\times ((x^2+x+r1)^2+r1)$
est bel et bien un produit de 2 facteurs.
J’en ai découvert plusieurs.
Si la différence entre k et r1 est de la forme s(s+1) alors A = 2*n est facilement factorisable.
J’aimerais bien un jour les regrouper (je parle de ces tests rapides) et en trouver d’autres afin de voir combien de nombres sont vulnérables à la factorisation.
Là n’est pas la question du moment.
Il est possible de couvrir une large partie des semi-premiers impairs moyennant ces tests rapides.
On ne peut pas penser à tout lorsque l’on construit des nombres RSA. Infailliblement des trous surgissent.
Chercher des mouchoirs ou m`apporter des fleurs?
Facile de perdre sa langue! Nespa?
J’attends du sérieux cette fois.
Je parie que certains nombres RSA sont vulnérables à plusieurs de mes maudits tests.
Sachant qu'il est beaucoup plus facile de factoriser un polynôme à coefficients entiers je te propose une méthode "brute de décoffrage":
Soit $N=PQ$, $P,Q$ entiers positifs impairs.
1) On se choisit au hasard un nombre plus petit que $N$, $b>1$.
2) On décompose le nombre $N$ dans la base $b$ cela nous donne un polynôme à coefficients entiers ($<b$) P.
On a donc $N=P(b)$
3)On cherche le PGCD des coefficients de $P$. Si ce n'est pas $1$ on a trouvé l'un des facteurs de $N$.
4)Autrement on essaie de factoriser le polynôme $P$ sur $\mathbb{Z}[X]$.
Si on y parvient, on aura trouvé $P_1,P_2,...,P_n$ des polynômes (non nécessairement distincts) de $\mathbb{Z}[X]$ tels que $P=P_1\times P_2\times ...\times P_n$
S'il existe $1\leq i\leq n$ tel que $P_i(b)$ n'est ni égal à $1$, ni égal à $N$ alors on a trouvé un facteur de $N$, le nombre $|P_i(b)|$ .
Sinon on retourne à 1)
Il me semble qu'il n'y a aucune garantie que l'algorithme, même pour un $N$ pas trop grand, puisse servir à factoriser $N$. :-D
En espérant ne pas avoir écrit trop d'énormités. :-D
Tu ne t’excuses même pas pour avoir dit une énormité.
Je ne suis qu’un amateur bourré .... d’idées (whisky non! pas aujourd’hui du moins).
Laquelle? Je suis curieux de l'entendre.
Qu'attends-tu des autres? Qu'ils utilisent tes méthodes pour factoriser un nombre du type RSA-240?
Programme les et fais les tests toi-même sur les nombres de l'ex-challenge RSA non factorisés.
Si tu parviens à factoriser l'un de ces nombres tu montreras, dans une certaine mesure, leur utilité pratique.
PS:
Pour ta question initiale, c'est encore plus simple, tu peux mener une étude statistique empirique avec un programme.
PS2:
Si tu ne sais pas avec quoi programmer, tu peux utiliser GP PARI, logiciel libre et open source.