librairie grands nombres ^

Question

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...

leprov · Answer

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?

leprov · Answer

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

BruNews · Answer

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++

coucou747 · Answer

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...)

BruNews · Answer

Fais une boucle avec grands nombres, tu verras si c'est viable.

ciao...
BruNews, Admin CS, MVP Visual C++

coucou747 · Answer

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...

cosmobob · Answer

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+ ;)

coucou747 · Answer

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 ;

Stepharcher · Answer

Si tu veux l'une des bibliothèques les plus performante du moment... recherche "GMP" sur google.

 >:)  Stéph  >:)

coucou747 · Answer

nonon, ça c'est pas interessant, je veux la créer moi même pour ma satisfaction personelle...

Stepharcher · Answer

ok désolé... Mais ça peut te servir de référence, tu regardes l'efficacitées de tes fonctions par rapport à celle de GMP...

 >:)  Stéph  >:)

cs_AsOr · Answer

Salut steph, moi ca minteresse ta librairy ou je peut la trouver, merci

cs_AsOr · Answer

j'ai trouver la library, mais elle est sous linux, est ce qu'il ets possible de lutiliser sous windows ( borland c++ builder 6 )

Librairie grands nombres ^

13 réponses

Votre réponse

Discussions similaires