[mingw32]Décomposition inverse d'une multiplication !
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:
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:
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:
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 ?
@+
Les difficultés se multiplient
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 N1/3 et donc b de l'ordre de N2/3. La distance entre les deux est donc de l'ordre de N1/3*(N1/3-1) soit environ (N1/3-1/2)². Avec 1024 bits cela représenterait de l'ordre de 2680 étapes soit au moins 10204. 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*2p + 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
Produit comme différence de carrés
Bonjour Sve
Citation:
Envoyé par
Sve@r
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 :weird:
Salut
