Exposé modulaire en C

Question

Aide! J'ai besoin d'implémenter un programme C (en utilisant uniquement les bibliothèques de chaînes, stdlib et stdio) qui utilisent l'exponentiation modulaire de très grands nombres, certains d'entre eux ont 260 chiffres. Je pense utiliser une liste liée mais je ne peux pas trouver une bonne référence sur la façon de l'implémenter. J'en ai besoin car j'ai besoin d'utiliser RSA pour crypter et décrypter un message.

En outre, j'ai exactement le même problème en obtenant le GCD de deux nombres très grands. Y a-t-il un moyen de le faire?

Answer 1

How to store large numbers? Vous pouvez utiliser ce type de stockage sorcière de données que vous aide à utiliser une petite quantité de mémoire et des opérations sera beaucoup plus rapide que toute autre chose parce que vous pouvez les faire directley sur les bits et ca vous utilisez les formules spéciales : Pour ajouter Irecomand vous de vérifier le débordement;

multiplier (x = x * y):

aux=x;x=0; 
while(y) 
{ 
    if(last_bit(y)==1) 
    x=x+aux; 
    shift_left(aux); 
    shift_right(y); 
} 

function modular_pow(base, exponent, modulus) 
{ 
if modulus = 1 then return 0 
Assert :: (modulus - 1) * (modulus - 1) does not overflow base 
result = 1 
base = base mod modulus 
while exponent > 0 
    if (last_bit(exponent)==1): 
     result = (result * base) mod modulus 
    exponent = exponent >> 1 
    base = (base * base) mod modulus 
return result 
}