Stack-Overflow trotz long long int



  • Ich programmiere gerade eine Implementierung des RSA-Verschlüsselungsverfahrens. Dazu verwendet ich als Kern des Schlüssels Primzahlen kleiner als 1000, weshalb also das Modul kleiner als 106 ist.

    Ein möglicher Beispielschlüssel wäre z.B. n=136931 (Modul), e=533 (Verschlüsselungspotenz), d=82589 (Entschlüsselungspotenz).
    Als Beispielnachricht verwenden wir 5.

    Ich habe das ganze mal auf ein minimales Codebeispiel reduziert.

    #include <stdio.h>
    #include <stdlib.h>
    
    //berechnet basis^power modulo mod rekursiv
    int modulo(int basis, int power, int mod){
    	long long int lbasis = basis;
    	long long int lmod = mod;
    	long long int x;
    	if(power>0){
    		x = lbasis*modulo(basis,power-1,mod)%mod;
    		return x;
    	}
    	else{return 1;}
    }
    
    int main(int argc, char *argv[]){
    	int n = 136931;
    	int e = 533;
    	int d = 82589;
    	int message = modulo(5,e,n);
    	printf("%d\n",message);
    	printf("%d\n",modulo(message,d,n));
    }
    

    message wird dabei richtig als 93210 zurückgegeben (was mit dem Ergebnis eines CAS übereinstimmt und sich in diesem auch wieder zurückrechnen lässt), aber bei der Rückrechnung gibt mir Visual Studio 2008 einen Stack overflow in modulo() als Fehler aus.
    Dabei ist geht doch der Bereich für long long int bis 9223372036854775807<1012 und das größte Produkt was in meiner Berechnung bei modulo() vorkommen sollte ist kleiner als 106*106.

    Wie kann ich genug Speicher zur Verfügung stellen, damit sowas nicht passier?



  • Stack overflow bedeutet bei rekursiven Funktionen, dass:

    1. Die Funktion sich unendlich oft aufruft und somit der Stack überläuft.
    2. Die Funktion sich nicht unendlich aufruft, aber trotzdem lang genug um den Stack überlaufen zu lassen.



  • Danke für die Antwort - habe es jetzt iterativ implementiert und es funktioniert. 😃


Log in to reply