Discussion :

[Artemus24]

Salut à tous.

Le but est de partir d'un nombre très très grand qui est le résultat d'une multiplication de deux nombres premiers (N = a * b).
Bien sûr, essayer de retrouver ces deux nombres premiers le plus rapidement.

Je me suis penché sur cette question, et la première idée consiste à décomposer ce nombre N sous la forme : x * ( x + y ).
Ce qui revient à dire que x est la racine carré du nombre N et ce x est en fait a.
Je dois retrouver b qui est en fait le reste de : N - x*x où x est initialisé à la racine carré de N puis varie par décrémentation.

Le mieux est de donner mon petit programme en 'C' :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**********************************************/
/*                                            */
/*     Décomposition de la multiplication     */
/*                                            */
/**********************************************/
 
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
 
/********************************/
/*                              */
/*     Procédure Principale     */
/*                              */
/********************************/
 
int main(void)
{
	unsigned long long int		a,b,i,n;
 
	/*==========================*/
	/*     Saisie du nombre     */
	/*==========================*/
 
	printf("Maximum : %llu\n", ULLONG_MAX);
	printf( "Veuillez saisir le nombre à décomposer : " );
	scanf( "%llu", &n );
 
	/*=====================*/
	/*     Préparation     */
	/*=====================*/
 
	a = (long long int)sqrt(n);
	b = n - a*a;
	i = 2 * a + 1;
 
	/*================*/
	/*     Calcul     */
	/*================*/
 
	while ((b%a) != 0)
	{
		b += (i -= 2);
		a--;
	}
 
	printf("\nA = %8.0llu   B = %8.0llu   Res = %llu\n", a, (a + (b/a)), (a*a + b));
}

Et voici quelques résultats :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Maximum : 18446744073709551615
Veuillez saisir le nombre à décomposer : 1234567890987654321
 
A = 1111011111   B = 1111211111   Res = 1234567890987654321
Appuyez sur une touche pour continuer...

Ou encore :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Maximum : 18446744073709551615
Veuillez saisir le nombre à décomposer : 987654313456789
 
A =   203423   B = 4855175243   Res = 987654313456789
Appuyez sur une touche pour continuer...

Le résultat est assez rapide quand la multiplication est proche de son carré.

Question : peut-on améliorer cet algorithme ?

@+

[Guesset]

Bonjour,

En cryptologie, un critère de choix des premiers qui vont participer à un grand nombre est la relation d'ordre de grandeur entre eux qui doit être importante. Les facteurs ne sont donc jamais proche de la racine carré. Cet algorithme apparaît donc assez vite hors course. Il y a quelques améliorations qui s'appuient sur la structure du N à décomposé mais elles n'en changent pas fondamentalement l'efficacité.

Il y a beaucoup de littérature (voir wikipedia pour commencer) sur ce problème difficile mais pas NP complet (il y a pire c'est rassurant ).

Salutations

[Sve@r]

Salut à tous.

Bonjour

Le but est de partir d'un nombre très très grand qui est le résultat d'une multiplication de deux nombres premiers (N = a * b).
Bien sûr, essayer de retrouver ces deux nombres premiers le plus rapidement.

Ah ? Parti pour casser RSA ? Bonne chance

Je me suis penché sur cette question, et la première idée consiste à décomposer ce nombre N sous la forme : x * ( x + y ).
Ce qui revient à dire que x est la racine carré du nombre N et ce x est en fait a.

Tu as conscience, j'espère, que ton algorithme n'est en réalité qu'un "brute force" inversé. Parce que entre partir de 2 et tester tous les nombres (2, 3, 4, 5, ...) jusqu'à (au pire) racine(N) ou bien partir de racine(N) et tester -1, -2, -3, ... jusqu'à (au pire) 2 c'est quelque part un peu la même chose. Avec toutefois une petite préférence pour le brute force classique car à moins d'être teubé et avoir choisi a=2, on peut présumer que a et b sont impairs donc partir de 3 et monter de 2 en 2.
Donc en fait, ta question c'est "peut-on optimiser le brute force". Voià quoi.

[Artemus24]

Salut à tous.

Les facteurs ne sont donc jamais proche de la racine carré.

C'est une autre approche, que l'approche triviale qui consiste à utiliser les nombres premiers inférieurs à la racine carré de la multiplication.
Je reste conscient que mon algorithme est juste une ébauche de la fonction inverse de la multiplication.

L'idée est la même que celle de l'algorithme de Shor.
Cette approche reste très simpliste, mais bien que meilleur que l'approche triviale.

Cet algorithme apparaît donc assez vite hors course.

Pourquoi est-ce si difficile de trouve cette fonction inverse ?

Il y a quelques améliorations qui s'appuient sur la structure du N à décomposé mais elles n'en changent pas fondamentalement l'efficacité.

Quelle amélioration peut-on apporter ?

Ah ? Parti pour casser RSA ? Bonne chance

Je ne cherche pas à casser le RSA. A moins de me tromper, la longueur conseillé par le RSA est de 2048, voire 4096 bits, non ?
Les 4096 bits représente un nombre de 1234 chiffres. Mon petit ordinateur ne pourrait pas supporter le choc.

Tu as conscience, j'espère, que ton algorithme n'est en réalité qu'un "brute force" inversé.

Oui, c'est bien cela. Peut-on l'améliorer ?

Donc en fait, ta question c'est "peut-on optimiser le brute force". Voilà quoi.

Ou mieux, expliquer pourquoi cette approche ne mène à rien.

J'ai vu le prix et les records.
Incroyable ! Le RSA-250 a été cassé le 28 février 2020, soit 829 bits.

@+

[Guesset]

Bonsoir,

Le problème de l'algorithme proposé est qu'il parcourt linéairement l'intervalle entre a et b. Or les 2 sont en général très distants l'un de l'autre. Prenons une exemple supposons que a soit de l'ordre de N^1/3 et donc b de l'ordre de N^2/3. La distance entre les deux est donc de l'ordre de N^1/3*(N^1/3-1) soit environ (N^1/3-1/2)². Avec 1024 bits cela représenterait de l'ordre de 2⁶⁸⁰ étapes soit au moins 10²⁰⁴. C'est beaucoup. Beaucoup trop.

On cherche des algorithmes dont la complexité soit un polynôme de log(N) et non une puissance (même fractionnaire) de N.

La structure à laquelle on peut s'intéresser est le début de N = n*2^p + r, r permet d'interdire a priori des valeurs de a et b et donc de diminuer le nombre de valeurs à tester mais cela ne change pas fondamentalement l'algorithme.

C'est désolant mais c'est ainsi.

Salutations

[Sve@r]

J'ai tenté un truc en partant de l'hypothèse d'Artemus24 disant N=x * ( x + y ). En développant, on obtient x²+xy-N=0. Equation du second degré. On calcule delta=y²+4N. Il existe donc deux solutions qui sont (-y+sqrt(delta))/2 et (-y-sqrt(delta))/2.
La seconde qui se factorisera en -(y+sqrt(delta))/2 et qui est donc clairement négative sera à oublier et on se concentre sur (sqrt(delta)-y)/2. Ne reste qu'à trouver"y" tel que y²+4N soit un carré parfait (sinon sqrt(delta) donne un nombre irrationnel qui ne convient pas).
Ca me paraissait une bonne idée sur le papier. Mais quand je l'ai appliquée, elle a foirée. Parce que pour par exemple 13*97, là où le brute force fera 6 tests (on ne teste que les impairs), il m'a fallu monter jusqu'à 84 pour trouver y²+4N carré parfait. Et 84 tests au lieu de 6...
C'est dommage car ça fonctionne. Quand y=84 on a bien delta=12100 et sqrt(delta)=110 ce qui donne au final x=13 (et x=-97 pour la seconde solution). Mais reste 84 tests au lieu de 6...

[Guesset]

Bonjour Sve

Ne reste qu'à trouver"y" tel que y²+4N soit un carré parfait...

En fait, c'est toujours la force brute sous une autre forme.

La valeur de y est paire sinon x+y serait pair puisque x est impair (on suppose que N est impair bien sûr). Écrivons y = 2a. Nous avons donc 4a² + 4N = B² ce qui implique B pair = 2b d'où a²+N=b² soit N = (b-a)(b+a) = x(x+y) = ((x+y/2)-y/2)((x+y/2)+y/2).

Ça tourne en rond

Salut

[Artemus24]

Salut à tous.

Merci de votre collaboration.

Or les 2 facteurs" sont en général très distants l'un de l'autre.

Pour éviter de cracker trop rapidement le RSA, l'astuce est de trouver ces deux facteurs dans un schéma non prédictible.
C'est pourquoi, comme tu le dis, ils sont très distants l'un de l'autre.
C'est un écueil difficile à résoudre car ce schéma est en dehors de toute logique basique.

C'est beaucoup, beaucoup trop.

Plus le nombre à décomposer est grand, plus cela va prendre du temps.
Donc impossible à cracker le RSA dans un temps raisonnable.
Sauf si ce nombre N a une particularité.

1) Pour revenir sur ma démarche, j'ai commencé par raisonner sur la multiplication elle-même.
J'ai cherché à décomposer la multiplication, de la même façon qu'on l'apprend dans les petites classes.
Nous avons alors un système d'équations avec comme contrainte, la propagation de la partie entière à l'unité supérieure.
A chaque étape, je suis obligé de calculer le modulo 10 ainsi que la division euclidienne de 10.
C'est complexe à mettre en œuvre puisqu'il y a des retours en arrière. Au final, c'est très très long.

2) Ma démarche suivante a été la classique division par la liste des nombres premiers.
Le problème de cette approche est de posséder la liste des nombres premiers.

3) Au lieu de débuter par les petits nombres premiers, j'ai pensé à commencer par la racine carré.
Mais cette approche est tout aussi longue.

On cherche des algorithmes dont la complexité soit un polynôme de log(N) et non une puissance (même fractionnaire) de N.

C'est un autre problème, celui de ma résolution NP = P

La structure à laquelle on peut s'intéresser est le début de N = n*2^p + r,

Au lieu d'avoir la base 10, ici la base est 2^p.
Il est vrai que trouver la partie entière n et le reste r est bien plus facile avec une représentation binaire.

r permet d'interdire a priori des valeurs de a et b et donc de diminuer le nombre de valeurs à tester mais cela ne change pas fondamentalement l'algorithme.

Je ne comprends pas trop cette affirmation.

J'ai tenté un truc en partant de l'hypothèse d'Artemus24 disant N=x * ( x + y ).

J'avais déjà tenté cette solution, sans succès.

Mais reste 84 tests au lieu de 6...

Tu arrives à la même solution que moi, à savoir trop de calcul pour arriver au résultat.

Je persiste à dire que si je sais calculer x_i qui est la racine carré entière de N, mon problème est de trouver la divisibilité euclidienne de y_i/x_i.
Par division euclidienne, j'entends l'obtention d'un reste nul.

Dans mon algorithme y_i augmente tandis que x_i diminue.
N'y-a-t-il pas un moyen de trouver la convergence où plusieurs i de y_i serait divisible par le x_i ?

Ce que je remarque, c'est que la variation y_i est toujours un nombre impair dont on décrémente de 2.
Par exemple 17, 15, 13, 11, 9, 7, 5, 3, 1. Si l'on fait la somme de cette variation, c'est toujours un carré.

Prenons un exemple. N=91 la racine carré est 9.

--> a₀ = 9.
--> b₀ = 91 - (a₀)² = 91 - 9² = 91 - 81 = 10.
--> i₀ = 2 * a₀ + 1 = 2 * 9 + 1 = 19.

test : 19 / 9 ? non

--> i₁ = i₀ - 2 = 19 - 2 = 17.
--> b₁ = b₀ + i₁ = 10 + 17 = 27
--> a₁ = a₀ - 1 = 9 - 1 = 8.

test : 27 / 8 ? non

--> i₂ = i₁ - 2 = 17 - 2 = 15.
--> b₂ = b₁ + i₁ = 27 + 15 = 42.
--> a₂ = a₁ - 1 = 8 - 1 = 7.

test : 42 / 7 ? oui = 6

Résultat :
--> a = a₂ = 7.
--> b = a₂ + b₂ / a₂ = 7 + 6 = 13.

Vérification : 7 * 13 = 91. Ok !

Pour l'indice 2, nous obtenons la solution.

b₂ = 42.
N vaut 91.
Donc 91 - 42 = 49 qui est un carré.
C'est aussi le carré de 7, qui est la valeur de a que nous trouvons pour l'indice 2.

Je ne sais pas trop si l'on peut exploiter quoi que ce soit avec cette constatation.
Cela revient à dire que : N - a² est divisible par a.

Ça tourne en rond

Qu'est-ce que tu sous-entends ? La récursivité ?

@+

[Guesset]

Bonjour,

Ça tourne en rond signifie juste que l'approche revient à son point de départ sans donner de piste exploitable.

Toutes les formes d'algorithmes en O(n^p) sont inexploitables pour les grand nombres c'est pourquoi on cherche des algorithmes en O(ln(N)^q) fussent ils heuristiques. La démonstration N=NP ou N!=NP n'a rien à voir car même s'il existe un algorithme déterministe pour la factorisation en O(ln(N)^q), il ne prouvera pas l'assertion N=NP car ce problème n'est pas NP complet.

Salutations