Modulare Exponentiation in C

Question

Hilfe! Ich muss ein C-Programm implementieren (das nur die Bibliotheken string, stdlib und stdio verwendet), die eine modulare Exponentiation von wirklich großen Zahlen verwenden, einige von ihnen sind 260 Ziffern. Ich denke darüber nach, eine verkettete Liste zu verwenden, aber ich kann keine gute Referenz finden, wie man sie implementiert. Ich brauche das, weil ich RSA verwenden muss, um eine Nachricht zu verschlüsseln und zu entschlüsseln.

Auch habe ich genau das gleiche Problem beim Erhalten der GCD von zwei sehr großen Zahlen. Kann ich das irgendwie machen?

Answer 1

How to store large numbers? Sie diese Art ein hilft, Daten zu speichern Hexe verwenden, können Sie eine kleine Menge an Speicher zu verwenden und für den Betrieb als alles viel schneller sein wird anders, weil man sie directley auf Bits machen können und Sie ca die speziellen Formeln : Für Irecomand hinzufügen, um den Überlauf zu überprüfen;

multiplizieren (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 
}