ymca2003
Messages postés2070Date d'inscriptionmardi 22 avril 2003StatutMembreDernière intervention 3 juillet 20067 6 janv. 2005 à 18:12
Je ne peux pas trop te renseigner la dessus, je ne maitrise pas trop le sujet (moins calé en math/algo qu'en C/C++). A mon avis ça doit pas trop influencer mais normalement le calcul de a^r mod n doit être assez optimisé déjà.
scelw
Messages postés117Date d'inscriptionmercredi 3 septembre 2003StatutMembreDernière intervention17 février 2007 6 janv. 2005 à 18:06
Il s'agit d'une question à propos du test de Miller-Rabin.
(>> http://cryptosec.lautre.net/article.php3?id_article=12 ...[bà lire pour comprendre la suite!)
C'est l'un des tests les plus rapides qui existent au monde. Mais il possède un "goulot d'étranglement" qui limite malgré tout sa vitesse d'exécution dès lors que l'on veut tester des nombres de très grande taille (plus d'un million de chiffres) : le calcul de y = a^r mod n (voir lien donné ci-dessus).
Ma question est : pour diminuer sensiblement le temps d'exécution de ce test, serait-il possible de choisir a dans l'intervalle ]1 ; (n-1)/2[ , voire ]1 ; (n-1)/(10^1000)[ ??
Quelles répercussions sur le résultat ? La probabilité d'avoir un nombre premier est-elle fortement modifiée?
MetalDwarf
Messages postés241Date d'inscriptionmardi 29 octobre 2002StatutMembreDernière intervention23 janvier 2006 16 mars 2004 à 21:17
ces fonctions sont deja inluses dans NTL, dans la classe ZZ (celle des grands entiers).
l operateur % est defini si mes souvenirs sont exacts, / aussi.
et pour les puissances il y a power(), ou meme powermod si tu veux calculer a^n mod n...
Voila!!
paranoman2002
Messages postés1Date d'inscriptionlundi 1 mars 2004StatutMembreDernière intervention 1 mars 2004 1 mars 2004 à 18:54
Suis aussi trés intérréssé d'avoir une réponse à la question de "scelw" concernant GMP, moi j'utilise NTL (dérivé de GMP si j'ai bien compris) mais les temps de réponses sont incomparables, beaucoup plus rapide sous GMP, le hic, c'est que je suis incapable d'utilisé GMP sous Windows (GMP prévu pour tourné sous Linux...que je ne connais pas...pas encore...)
J'ai besoin des fonctions puissance (a^n, avec des a tres grand environ 50-100 Millions), division, et modulo
Merci pour un ptit conseil
scelw
Messages postés117Date d'inscriptionmercredi 3 septembre 2003StatutMembreDernière intervention17 février 2007 28 févr. 2004 à 09:23
si l'on manipule des nombres d'1 million de chiffres, qu'est-ce qui se passe ? ralentissement ? overflow ?
et connaissez-vous la librairie GMP ? c'est presque la même chose non ? y a-t-il une différence ?
ymca2003
Messages postés2070Date d'inscriptionmardi 22 avril 2003StatutMembreDernière intervention 3 juillet 20067 27 févr. 2004 à 23:05
On peut aller très loin mais 1 millions de chiffre ça fait beaucoup.
256 bits -> 77 chiffres
1025 bits -> 300 chiffres
(3*N/10 =) chiffres environs
la classe CBigInt permet de masquer à l'utilisateur la gestion internes (fonctions private), tout en exposant des fonctions d'accès et d'opération (public) facilitant l'utilisation.
De ce fait la classe CBigInt permet d'utiliser des nombres de la même façon que les types de base (int, long...)
CBgigInt a, b, c;
a = 32;
b = 65;
c = a+b;
...
scelw
Messages postés117Date d'inscriptionmercredi 3 septembre 2003StatutMembreDernière intervention17 février 2007 27 févr. 2004 à 16:46
Bonjour,
Je suis super nul en C/C++ mais cette source m'intéresse beaucoup !
Jusqu'où peut-on monter avec la classe BigInt ? Peut-on aller jusqu'à des nombres de 1 million de chiffres ?
Et qu'est-ce que c'est exactement la "classe BigInt" ? C'est pas une librairie plutôt ?
scelw
Messages postés117Date d'inscriptionmercredi 3 septembre 2003StatutMembreDernière intervention17 février 2007 27 févr. 2004 à 16:45
Bonjour,
Je suis super nul en C/C++ mais cette source m'intéresse beaucoup !
Jusqu'où peut-on monter avec la classe BigInt ? Peut-on aller jusqu'à des nombres de 1 million de chiffres ?
Et qu'est-ce que c'est exactement la "classe BigInt" ? C'est pas une librairie plutôt ?
garslouche
Messages postés583Date d'inscriptionmardi 26 novembre 2002StatutMembreDernière intervention29 mai 20151 19 nov. 2003 à 08:35
Très bonne idée de présenter ces algos!
Ton code est propre et bien commenté!
Par contre j'aurais quelques remarques à faire sur la POO :
- Tu devrais mettre tes variables de classes en Protected et non en Private. Ca permettrait de dériver plus facilement une classe de BigInt.
- Les fonctions comme IsPrime ou Miller devrait être des méthodes de la classe BigInt
- Tu devrais faire de Pgcd, jacobien, ... des opérateurs de BigInt.
En fait il faudrait que BigInt prenne en charge les opérations sur les BigInt!
Mais c'est déjà vachement bien....9/10
BlackGoddess
Messages postés338Date d'inscriptionjeudi 22 août 2002StatutMembreDernière intervention14 juin 2005 4 nov. 2003 à 00:25
super, magnifique, je vais étudier de pres a classe BigInt, ca faisait longtemps que je cherchais une classe pareille :)
6 janv. 2005 à 18:12
6 janv. 2005 à 18:06
(>> http://cryptosec.lautre.net/article.php3?id_article=12 ...[bà lire pour comprendre la suite!)
C'est l'un des tests les plus rapides qui existent au monde. Mais il possède un "goulot d'étranglement" qui limite malgré tout sa vitesse d'exécution dès lors que l'on veut tester des nombres de très grande taille (plus d'un million de chiffres) : le calcul de y = a^r mod n (voir lien donné ci-dessus).
Ma question est : pour diminuer sensiblement le temps d'exécution de ce test, serait-il possible de choisir a dans l'intervalle ]1 ; (n-1)/2[ , voire ]1 ; (n-1)/(10^1000)[ ??
Quelles répercussions sur le résultat ? La probabilité d'avoir un nombre premier est-elle fortement modifiée?
16 mars 2004 à 21:17
l operateur % est defini si mes souvenirs sont exacts, / aussi.
et pour les puissances il y a power(), ou meme powermod si tu veux calculer a^n mod n...
Voila!!
1 mars 2004 à 18:54
J'ai besoin des fonctions puissance (a^n, avec des a tres grand environ 50-100 Millions), division, et modulo
Merci pour un ptit conseil
28 févr. 2004 à 09:23
et connaissez-vous la librairie GMP ? c'est presque la même chose non ? y a-t-il une différence ?
27 févr. 2004 à 23:05
256 bits -> 77 chiffres
1025 bits -> 300 chiffres
(3*N/10 =) chiffres environs
la classe CBigInt permet de masquer à l'utilisateur la gestion internes (fonctions private), tout en exposant des fonctions d'accès et d'opération (public) facilitant l'utilisation.
De ce fait la classe CBigInt permet d'utiliser des nombres de la même façon que les types de base (int, long...)
CBgigInt a, b, c;
a = 32;
b = 65;
c = a+b;
...
27 févr. 2004 à 16:46
Je suis super nul en C/C++ mais cette source m'intéresse beaucoup !
Jusqu'où peut-on monter avec la classe BigInt ? Peut-on aller jusqu'à des nombres de 1 million de chiffres ?
Et qu'est-ce que c'est exactement la "classe BigInt" ? C'est pas une librairie plutôt ?
27 févr. 2004 à 16:45
Je suis super nul en C/C++ mais cette source m'intéresse beaucoup !
Jusqu'où peut-on monter avec la classe BigInt ? Peut-on aller jusqu'à des nombres de 1 million de chiffres ?
Et qu'est-ce que c'est exactement la "classe BigInt" ? C'est pas une librairie plutôt ?
19 nov. 2003 à 08:35
Ton code est propre et bien commenté!
Par contre j'aurais quelques remarques à faire sur la POO :
- Tu devrais mettre tes variables de classes en Protected et non en Private. Ca permettrait de dériver plus facilement une classe de BigInt.
- Les fonctions comme IsPrime ou Miller devrait être des méthodes de la classe BigInt
- Tu devrais faire de Pgcd, jacobien, ... des opérateurs de BigInt.
En fait il faudrait que BigInt prenne en charge les opérations sur les BigInt!
Mais c'est déjà vachement bien....9/10
4 nov. 2003 à 00:25