Comment les ordinateurs peuvent-ils calculer des calculs exponentiels sans erreurs de débordement?

En étudiant certaines méthodes de cryptage / décryptage RSA, j'ai trouvé cet article: Un exemple de l'algorithme RSA

Il faut pour cela décrire ce message

Le résultat total de est si grand que, pour une machine 64 bits / 32 bits, je ne crois pas qu'elle puisse contenir une valeur aussi importante dans un seul registre. Comment l'ordinateur le fait-il sans débordement?

Cette question était une question de super utilisateur de la semaine .
Lisez l' entrée du blog pour plus de détails ou contribuez vous-même au blog

Parce que l'opération de module entier est un homomorphisme en anneau ( Wikipedia ) de -> / nℤ,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

Vous pouvez le vérifier vous-même avec un peu d'algèbre simple. (Notez que la finale modà droite apparaît en raison de la définition de la multiplication dans un anneau modulaire.)

Les ordinateurs utilisent cette astuce pour calculer des exponentielles dans des anneaux modulaires sans avoir à calculer un grand nombre de chiffres.

               / 1 I = 0,
               |
(X ^ I) mod N = <(X * (X ^ (I-1) mod N)) mod NI impair,
               |
               \ (X ^ (I / 2) mod N) ^ 2 mod NI même & I / = 0.

Sous forme algorithmique,

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

Vous pouvez l'utiliser pour calculer (855^2753) mod 3233avec des registres 16 bits uniquement, si vous le souhaitez.

Cependant, les valeurs de X et N dans RSA sont beaucoup plus grandes, trop grandes pour tenir dans un registre. Un module est généralement long de 1024 à 4096 bits! Ainsi, vous pouvez avoir un ordinateur qui fait la multiplication à la "longue" manière, de la même manière que nous effectuons la multiplication à la main. Au lieu d’utiliser les chiffres 0 à 9, l’ordinateur utilisera des "mots" 0-2 ¹⁶ -1 ou quelque chose du genre. (Utiliser seulement 16 bits signifie que nous pouvons multiplier deux nombres 16 bits et obtenir le résultat complet en 32 bits sans recourir au langage assembleur. En langage assembleur, il est généralement très facile d'obtenir le résultat complet en 64 bits, ou pour un ordinateur 64 bits. , le résultat complet sur 128 bits.)

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

Cela multipliera X par Y en une durée approximativement égale au nombre de mots de X multiplié par le nombre de mots de Y. On appelle cela le temps O (N ² ). Si vous regardez l'algorithme ci-dessus et le choisissez, c'est la même "multiplication longue" qu'ils enseignent à l'école. Vous n'avez pas de tables de temps mémorisées sur 10 chiffres, mais vous pouvez toujours multiplier 1 926 348 x 8 192 004 si vous vous assoyez et que vous vous en sortez.

Longue multiplication:

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

Il existe en fait des algorithmes plus rapides pour la multiplication ( Wikipedia ), tels que la méthode de Fourier rapide de Strassen, et des méthodes plus simples qui effectuent des additions et des soustractions supplémentaires, mais moins de multiplications, et aboutissent donc plus rapidement. Les bibliothèques numériques telles que GMP sont capables de sélectionner différents algorithmes en fonction de la taille des nombres: la transformation de Fourier n'est que la plus rapide pour les plus grands nombres, les plus petits nombres utilisent des algorithmes plus simples.

La réponse est simplement qu'ils ne peuvent pas, pas eux-mêmes. En effet, si vous prenez le concept de machine x-bit, alors il y a un nombre limité de nombres qui peuvent être représentés par un nombre limité de bits, tout comme il y a un nombre limité de nombres qui peuvent être représentés par 2 chiffres dans le système décimal.

Cela étant dit, la représentation informatique de très grands nombres est une composante importante du domaine de la cryptographie. Il existe de nombreuses façons de représenter un très grand nombre sur un ordinateur, aussi variées les unes que les autres.

Chacune de ces méthodes présente des avantages et des inconvénients, et bien que je ne puisse / ne puisse pas énumérer toutes les méthodes ici, je vais en présenter une très simplement.

Supposons qu'un entier ne puisse contenir que des valeurs de 0 à 99. Comment représenter le nombre 100? Cela peut sembler impossible au début, mais c'est parce que nous ne considérons qu'une seule variable. Si j'avais un entier appelé unitset on a appelé hundreds, je pourrais facilement représenter 100: hundreds = 1; units = 0;. Je pourrais facilement représenter un plus grand nombre, comme 9223: hundreds = 92; units = 23.

Même s’il s’agit d’une méthode facile, on peut affirmer qu’elle est très inefficace. Comme la plupart des algorithmes qui repoussent les limites de ce qu'un ordinateur peut faire, il s'agit généralement d'un bras de fer entre le pouvoir (représenter de grands nombres) et l'efficacité (récupération / stockage rapide). Comme je l'ai dit plus tôt, il existe de nombreuses façons de représenter un grand nombre dans les ordinateurs; il suffit de trouver une méthode et d'expérimenter avec elle!

J'espère que cela répond à votre question!

Lectures complémentaires:Cet article et celui- ci peuvent être utiles pour plus d'informations.

La façon dont cela peut être fait (il existe des moyens beaucoup plus rapides impliquant des quadratures répétées, etc.) consiste à se multiplier et, après chaque multiplication, prendre le module. Tant que le module carré est inférieur à 2 ^ 32 (ou 2 ^ 64), il n'y aura jamais de dépassement de capacité.

De la même manière que vous pouvez.

Je vais deviner que vous ne savez pas ce que 342 * 189 est. Mais vous connaissez les faits suivants:

9 * 2 = 18
9 * 4 = 36
9 * 3 = 27
8 * 2 = 16
8 * 4 = 32
8 * 3 = 24
1 * 2 = 2
1 * 4 = 4
1 * 3 = 3

18 + 360 + 2700 + 160 + 3200 + 24000 + 200 + 4000 + 30000 = 64638

En connaissant ces simples faits et en ayant appris une technique pour les manipuler, vous pouvez utiliser l'arithmétique comme vous ne le pouviez pas autrement.

De la même façon, un ordinateur qui ne peut gérer plus de 64 bits de mathématiques à la fois peut facilement diviser des problèmes plus importants en morceaux plus petits, créer ces morceaux plus petits et les rassembler pour former la réponse au problème plus vaste qui existait auparavant. problème sans réponse.

En ce qui concerne l'addition et la soustraction, de nombreuses CPU ont un "bit de report" qui est défini si l'opération arithmétique a débordé. Donc, si un résultat nécessite 8 octets à stocker et que la CPU a 32 bits (ce qui équivaut à 4 octets 8 bits), elle peut effectuer deux opérations d’addition, d’abord sur le "mot bas", puis sur le "mot haut". avec le peu de porter en prenant soin de la débordement. Nécessaire d'effacer le bit de retenue en premier. C'est l'une des raisons pour lesquelles les processeurs à bits plus élevés améliorent les performances, car cela ne doit pas être fait autant.

Bien sûr, cela provient de mon expérience d'assembleur limitée avec les processeurs 8 bits. Je ne sais pas comment le bit de retenue fonctionne avec les processeurs modernes avec des instructions multiplie et divde. Les processeurs RISC non-Intel peuvent également se comporter différemment.

Je ne connais pas grand chose aux maths en virgule flottante, mais au fond, les octets représentent un nombre fixe d’endroits, mais pas d’endroits spécifiques. C'est pourquoi on l'appelle "point flottant". Ainsi, par exemple, le nombre 34459234 consomme à peu près le même espace mémoire que 3.4459234, ou 3.4459234E + 20 (soit 3,4459234 x 10 ^ 20).