librairie grands nombres ^

Je dévelope en ce moment une librairie qui me permetrais de gérer des nombres de 1024 bits..
Je ne fais que du C... Voici la sctructure qui contiendra le nombre :
typedef struct {
char valeur[256]; int unsigned long taille; }grandnombre;

Je ne fère pas les nombres négatifs, ni les nombres a virgules (totalement inutile en rsa, pour ces calculs, en général, on transforme la science en machine a fric.. ex : le calcul de pi ect....)

Voila, ça donne a peu près ça... dans taille, on a la taille du nombre, taille sert uniquement a gagner du temps, je pourais éviter de définir en dur le tableau comme me l'a dit kirua avec malloc et realloc, mais en fait, j'en ai pas vraiment envi car on perd du temps, ce qui est précieux dans les histoires de calculs...

J'ai eu quelques problèmes pour la division et le modulo (car on doit prendre b en entier) mais j'y suis arrivé, si qqn veut les sources complètes, il me mail, je lui répondrais...

Voici mon problème : pour les opérations : + - * pas de problèmes, pour / et % un peu plus dur, mais j'y suis arrivé, je bloque a ^ en effet si je fait a=b ^ c alors j'aurais un peu bcp de calculs si je fais
a=b
e=0;
while(e<c)
a=a*b

si je fais ça, j'aurais un peu bcp de calculs surtout que cette librairie devrait servir a des calculs genre rsa...

une idée spontanée mais pas forcément judicieuse (je sais pas, cest a reflechir, mais la chui pas assez enf forme pr y arriver) : calcul recursif selon la methode indienne (je crois ke ca sappelle comme ca). ca pourrait etre plus rapide, mais a vérifier.
sinon l'elever a la puissance de 2 la plus proche puiq finir comme tas fait ca peut pas le faire?

cest des idées pas forcement bonnes et en vrac, mais on sait jamais. cest les seules ke jai et chui trop fatigué pr reflechir plus lol

Recursivite a bannir ici, trop long en temps de calcul.
Va jeter un oeil sur codeproject ou sourceforge, me souviens plus exactement lequel (1er je crois), une classe grand nombre performante a ete publiee la semaine derniere.
PS: + de la moitie de la classe est implementee en asm, vitesse oblige dans les divisions.

ciao...
BruNews, Admin CS, MVP Visual C++

oulala l'asm c'est pas pour moi, mais les divisions, j'ai déja réussi... j'ai pas fais de test de vitesse, mais pour un petit nombre, on attend pas... (évidement, mes test ont été fait avec des nombres relativement petits pour la vitesse de vérification...)

Fais une boucle avec grands nombres, tu verras si c'est viable.

ciao...
BruNews, Admin CS, MVP Visual C++

boucle avec des grands nombres... des nombres de 1024 bits... je doute avoir le courage nécessaire a cette vitesse d'execution...

en fait, en rsa, on fait
b=a^d%n

et b a d et n sont énormes, le plus grand nombre ici, c'est n, mais je pe penses qas que cette vitesse soit satisfesante...

faire a^d c'est pas pareil que a^d modulo n.
(si a et d sont des grands nombres).
a^d va à coup sur etre immensément long (et en fait ca n'est jamais fait), alors que a^d mod n peut se faire en en temps en O(log(d)) (c'est une simple exponentiation modulaire).

voila...
a+ ;)

oulala je te suis plus moi, c'est aussi dur a faire sachant des les % et / sont rapides a effectuer, mais les calculs sont vraiment longs pour l'exposant...

b=a^d % n peut aussi se faire de cette façon la :

b = 1;
k=0;
while (k<d){
b=a*b;
b=b%n;
k++;
}

mais la, j'apelles 2*d fonctions et comme ces fonctions ont beau être rapides, ça prends quand même un peu de temps... De plus, je rapelles le principe de calcul des clefs :
p premier;
q premier;
n=p*q;
f=(p-1)*(q-1);
e premier avec f;
i=1;
while ( i%e!=0 )
{
i=i+f;
}

Donc, je sais que p et q doivent êtres énormes, e, je ne sais pas exactement quelle doit être sa taille, mais je supposes aussi que e ne doit pas être un petit nombre...


d= i / e ;

Si tu veux l'une des bibliothèques les plus performante du moment... recherche "GMP" sur google.

Stéph