Quelle est la base idéale pour un algorithme de test de bibliothèque et de primalité bignum?

Question

Je dois programmer le test de primalité Solovay-Strassen présenté dans l'article original sur RSA.

De plus, je vais devoir écrire une petite bibliothèque bignum, et ainsi lors de la recherche d'une représentation pratique pour bignum je suis tombé sur cette specification:

struct { 
    int sign; 
    int size; 
    int *tab; 
} bignum; 

Je vais aussi écrire une routine de multiplication en utilisant la méthode Karatsuba .

Alors, ma question:

Quelle base serait pratique pour les données entières de magasin dans le struct bignum?

Remarque: Je ne suis pas autorisé à utiliser des implémentations tierces ou intégrées pour Bignum telles que GMP.

Merci.

Answer 1

La base que vous utilisez doit avoir une puissance de 2. Comme il semble que vous gardiez trace des signes séparément, vous pouvez utiliser les ints non signés pour stocker les nombres eux-mêmes. Vous aurez besoin de la capacité de multiplier 2 morceaux/chiffres/unités de ces nombres à la fois, donc la taille ne doit pas être plus de la moitié de la taille du mot que vous avez disponible. c'est-à-dire sur x86, un entier non signé est de 32 bits, de sorte que vous souhaitiez que vos chiffres ne soient pas supérieurs à 16 bits. Vous pouvez également utiliser "long long" pour les résultats intermédiaires des produits d'ints non signés. Alors vous regardez 2^32 pour votre base. Une dernière chose à considérer est que vous voudrez peut-être ajouter des sommes de produits, qui déborderont à moins que vous n'utilisiez moins de bits.

Si la performance n'est pas une préoccupation majeure, j'utiliserais simplement la base 256 et l'appelez un jour. Vous pouvez utiliser typedefs et les constantes définies afin de pouvoir modifier ces paramètres ultérieurement.

Answer 2

une puissance de 2.

Pour une implémentation simple, probablement la moitié de la taille d'un mot sur votre machine, de sorte que vous pouvez multiplier deux chiffres sans trop-plein. Donc 65536 ou 4294967296. Ou peut-être la moitié de la taille du plus grand type entier, pour la même raison, mais peut-être une meilleure performance sur tous.

Mais je n'ai jamais réellement implémenté une telle bibliothèque: si vous utilisez les algorithmes les plus connus, alors vous ne ferez pas de longue multiplication en style scolaire. La multiplication de Karatsuba (et toutes les autres astuces intelligentes que vous utiliserez) gagnerait à être faite dans un entier qui est plus de deux fois la taille des chiffres, je ne sais vraiment pas comment la performance fonctionne. Si c'est le cas, il vaut mieux utiliser l'arithmétique 256 et 32 ​​bits, ou l'arithmétique 65536 et 64 bits.

Dans tous les cas, si votre représentation est binaire, vous pouvez sélectionner et choisir des bases plus puissantes de deux bases pour chaque opération. Par exemple, vous pouvez traiter les données comme base 2^16 pour la multiplication, mais base 2^32 pour l'addition. C'est la même chose à condition de faire attention à l'endianité. Je commencerais probablement par la base 2^16 (puisque cela me force à commencer par l'endian-ness, alors que 2^8 ne le feraient pas), et je vois comment j'arrive - comme chaque opération est optimisée, une partie de l'optimisation consiste à identifier la meilleure base.

L'utilisation d'une taille qui n'est pas un multiple d'octets est une possibilité, mais vous devez utiliser la même base pour tout, car il y a des bits inutilisés dans le stockage à des endroits spécifiques en fonction de la base.

Answer 3

Les entiers du tableau d'onglets doivent être non signés. Ils devraient être la plus grande taille possible (base) que vous pouvez multiplier et représenter encore le produit.Si votre compilateur/processeur prend en charge 64 bits non signés longtemps, par exemple, vous pouvez utiliser uint32_t pour le tableau de "chiffres". Si votre compilateur/processeur ne peut produire que des produits 32 bits, vous devez utiliser uint16_t.

Lorsque vous additionnez deux tableaux, vous devez gérer le dépassement; dans l'assemblage c'est facile. En C, vous pouvez choisir d'utiliser un bit de moins (31 ou 15) pour faciliter la détection de débordement.

Pensez également à l'endianess, et à l'effet qu'aura l'algorithme et son comportement sur le cache.

Answer 4

Vous allez faire l'opération suivante beaucoup:

a b + c d ...; Choisissez 1/4 la plus grande taille de mot, ou 1/2 la plus grande taille de mot moins un peu ou deux. Ce serait soit 2^16 ou 2^30 pour les systèmes 64 bits et 2^8 ou 2^14 pour les systèmes 32 bits. Utilisez la plus grande taille prise en charge par le compilateur, pas le matériel.

Si vous choisissez 2^31 sur un système 64 bits, cela signifie que vous pouvez ajouter 4 produits sans débordement. Si vous choisissez 2^30, vous pouvez ajouter 16 produits sans débordement. Le plus vous pouvez ajouter sans débordement, les plus grands blocs provisoires que vous pouvez utiliser.

Si vous choisissez 1/4 de la taille du mot, vous aurez toujours un type natif, il sera donc plus facile de stocker les résultats. Vous pouvez à peu près ignorer le débordement aussi. Cela rendra l'écriture de code plus rapide et moins sujet aux erreurs, et est légèrement plus efficace en mémoire. Je recommanderais ceci à moins que vous aimez beaucoup de manipulations de bits avec vos maths.

Le choix d'une base plus large rendra les grands nombres d'O meilleurs. En pratique, alors qu'il serait probablement plus rapide d'avoir une base plus grande, ce ne sera pas la bosse de vitesse 4x que vous pourriez espérer.