Discussion :

[i.Polo]

Bonjour,

Je suis actuellement en 1ère année de classe préparatoire intégrée dans une école d'ingénieurs en nouvelles technologies. Notre professeur d'informatique, afin de comprendre l'aspect mémoire d'un système à microcontrôleur, nous a donné un projet lié à l'utilisation de pointeurs mémoire. Nous programmons en C++.

Ce projet a pour thème la cryptographie asymétrique et donc repose sur des calculs sur des nombres relativement longs (pouvant aller jusqu'à des milliers de bits sans problème). Pour pouvoir stocker sans trop de problèmes ces grands nombres (considérés comme positifs ou nuls et entiers), nous avons défini un type "lentier" (pour entier long) qui est en fait un pointeur vers une zone mémoire contenant des entiers non signés sur 32 bits. Chaque entier long sera constitué d'un tableau d'entiers sur 32 bits, et donc exprimé en base (2³²) (nombres pouvant aller de 0 à (2³²) - 1). La case d'indice 0 sera le poids faible (2³²)⁰ et la n-ième case sur laquelle est stocké l'entier long sera de poids (2³²)ⁿ.

Le "lentier" est défini de cette manière :

Code :

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

 typedef unsigned long * lentier;

Le travail est réparti en différents groupes d'étudiants et le mien est chargé de l'interfaçage, c'est-à-dire convertir un grand nombre en base 10 saisi par l'utilisateur avec une chaîne de caractères en un "lentier", c'est à dire un pointeur vers un nombre en base (2³²) . Nous sommes également chargés de l'opération inverse (convertir un "lentier" en un nombre sous forme d'une chaîne de caractères affichable en base 10).

Cette opération inverse décrite précédemment consiste en fait en des divisions successives par 10 afin de récupérer le reste et de convertir le "lentier" sur un tableau d'entiers de 32 bits en un nombre en base 10. Je rencontre un problème dans mon travail : je suis chargé de programmer une fonction intermédiaire à cette fonction, la division d'un "lentier" par 10, qui retourne à la fois le quotient et le reste (en ayant précisé sur combien de cases mémoire pointe ce "lentier"). J'ai suivi un algorithme de division euclidienne en base quelconque que j'ai adapté à notre cas, et le programme que j'ai conçu en C ne semble pas retourner les bons résultats pour un "lentier" de taille supérieure à 2.

Je vous joins mon code commenté ainsi que l'algorithme de division euclidienne en base quelconque. Dans l'algorithme, le souci se trouve dans mon cas (je pense) à l'étape b) du 3. puisque dans mon cas le diviseur B est de taille inférieure à 2, et dans l'algorithme ce n'est pas le cas.. Mon adaptation à une taille inférieure n'est probablement pas bonne. Je vous laisse en juger par vous mêmes.

En espérant que vous puissiez m'éclaircir à ce sujet, merci d'avance.

Bien cordialement

nb : Cet algorithme fait appel à des fonctions de base codées par d'autres personnes, qui effectuent la multiplication, l'addition et la soustraction de 2 lentier (paramètres : lentier a, lentier b, taille du lentier a, taille du lentier b) que vous voyez apparaître dans le code sous les noms "mult_classique", "add_classique" et "sub_classique".

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
res_div div_10(lentier a, unsigned int n)
{
	//======= LEXIQUE =======
	lentier q = (lentier)calloc(n, sizeof(int));
	unsigned long r;
	unsigned long long op1;
	unsigned long long op2;
	lentier qit = (lentier)calloc(1, sizeof(int));
	lentier brit = (lentier)calloc(n-1, sizeof(int));
	lentier op_c;
	lentier aux;
	res_div res;
 
 
	//======= ALGO ========
	//1 géré avec le calloc
	//2
	while (a[n - 1] >= 10)  //B*r^(n-t) correspond à 10*(2^32)^(n-1) soit un lentier de taille n avec des 0 partout sauf dans la case d'indice n-1 qui contient 10
	{
		q[n - 1]++;
		a[n - 1] -= 10;
	}
 
	//3
	for (unsigned int i = n - 1; i >= 1; i--)
	{
		//a
		if (a[i] == 10)
		{
			q[i - 1] = 0xFFFFFFFF; //2^32-1
		}
		else
		{
			q[i - 1] = (((unsigned long long)a[i]<<32) + a[i - 1]) / 10; //(a[i]r + a[i-1])/10
		}
 
		//b
		op1 = q[i - 1] * 10;							   //Q[i-t] * B[t-1]
		op2 =((unsigned long long)a[i]<<32) + a[i - 1]; //A[i]r + A[i-1]
		while (op1 > op2) //Comparaison des deux opérandes précédents de taille 2 (max)
		{
			q[i - 1]--;
			op1 = q[i - 1] * 10;
		}
 
		//c
		qit[0] = q[i - 1];
		brit[i - 1] = 10; //Pour la division par 10, B*r^[i-t] = 10*(2^32)^(i-1) soit un lentier  avec seulement 10 dans la case d'indice i-1 (sous le nom brit)
		op_c = mult_classique(qit, brit, 1, n-1);
 
		if (cmp_lentier(a, op_c, n) != -1) //Si A - Q[i-1]*Br^(i-1) > 0
		{
			aux = a; //pointeur auxiliaire vers a
			a = sub_classique(a, op_c, n, n); //On peut effectuer la soustraction
			if (i != n - 1) //Pas de libération pour la 1ère op sur A
			{
				delete[]aux;
			}
		}
 
		//d
		else  //Sinon, A - Q[i-1]*Br^(i-1) <= 0
		{
			aux = a; //pointeur auxiliaire vers a
			a = add_classique(a, brit, n, n-1);     //Donc on effectue d'abord l'addition 
			delete[]aux;
			aux = a;
			a = sub_classique(a, op_c, n, n); //Puis la soustraction (un unsigned long ne supporte pas de nombres négatifs )
			delete[]aux;
			q[i - 1]--;
		}
		brit[i - 1] = 0; //On libère la case mise à 10 pour la prochaine boucle
 
		delete[]op_c; //Libération du lentier pour la prochaine boucle
 
	}
	//libérations mémoire
	delete[]qit;
	delete[]brit;
 
	//4
	r = a[0];
 
	//5
	res.quotient = q;
	res.reste = r;
	return res;
 
}

[Flodelarab]

Bonjour

Appâter par la cryptographie asymétrique et finir sur un problème de division entière qu'on résoudrait par un simple '%' avec les integers est malin et très frustrant.

J'ai énormément de mal avec la première boucle. Si ton lentier est égal à 10 000, alors tu vas enlever 1000 fois 10 ??? Surtout qu'un lentier est fait pour être énorme. Il faut revoir l'algorithme.

[yahiko]

On est tout de même à la limite de problème d'implémentation plus que d'un problème d'algorithmique... M'enfin...

Tu devrais déjà nous montrer si tu parviens à convertir un nombre 32 bits normal en chaîne en base 10. Ce serait déjà une première étape.
Sachant qu'une fois cela réalisé, il "suffit" de généraliser l'algo à un vecteur de nombres en 32 bits.

[i.Polo]

Bonsoir,

En ce qui concerne la réponse de Flodelarab:

Je suis désolé si cela a été vu comme une manière "d'appâter" mais comme c'est l'intitulé du projet, je l'ai simplement remis dans le titre du topic. Il est vrai que ma partie ne traite pas tellement de l'aspect "cryptographie''.

Effectivement, niveau optimisation ce n'est pas le top ^^ Je reverrai ça. Après cette boucle fonctionnera dans tous les cas, j'aimerais surtout résoudre le problème de dysfonctionnement du programme en lui-même.

Pour yahiko :

Effectivement, le souci est que j'ai cherché dans les différents sujets et je ne voyais pas tellement d'endroit plus adapté pour un problème finalement lié en quelque sorte aux mathématiques. Il y avait sûrement mieux mais je ne l'ai pas vu car je n'ai pas trop l'habitude de poster sur le forum et je m'en excuse.
L'algorithme de conversion en base 10 a déjà été testé grâce à une fonction de division par 10 codée par notre prof, par la suite je ne vois pas ce que tu entends par "généraliser".

Merci à vous pour vos réponses

[i.Polo]

Bonjour,

J'ai rencontré mon prof et ma fonction marchait bien correctement, le problème ne vient pas de là et ma fonction a pu être énormément optimisée par rapport à la version de base présentée précédemment (quelques démos mathématiques rendant inutiles certaines boucles)

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
 
res_div div_10(lentier a, unsigned int n)
{
	//======= LEXIQUE =======
	lentier q = (lentier)calloc(n, sizeof(int));
	unsigned long r;
	res_div res;
 
 
	//======= ALGO ========
	//1 géré avec le calloc
	//2
	q[n - 1] = a[n - 1] / 10;
	a[n - 1] = a[n - 1] % 10;
 
	//3
	for (unsigned int i = n - 1; i >= 1; i--)
	{
		//a
 
		q[i - 1] = (((unsigned long long)a[i] << 32) + a[i - 1]) / 10; //(a[i]r + a[i-1])/10
 
		//b
		//La comparaison sera forcément non vérifiée pour un B de taille 1
 
		//c 
		a[i - 1] = (((unsigned long long)a[i] << 32) + a[i - 1]) % 10;
		a[i] = 0;
 
	}
 
	//4
	r = a[0];
 
	//5
	res.quotient = q;
	res.reste = r;
	return res;
 
}

Merci pour votre aide