GÉNÉRATEUR DE GRANDS NOMBRES PREMIERS (BIS)

Commentaire de BlackGoddess le 04/11/2003 00:25:04

super, magnifique, je vais étudier de pres a classe BigInt, ca faisait longtemps que je cherchais une classe pareille :)

Commentaire de scelw le 27/02/2004 16:45:56

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 ?

Commentaire de ymca2003 le 27/02/2004 23:05:51

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

Commentaire de paranoman2002 le 01/03/2004 18:54:16

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

Commentaire de scelw le 06/01/2005 18:06:18

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?