Methode um "x^y mod n" zu berechnen funktioniert nicht...

[HiFish]

Hallo,
Ich habe probiert den RSA Algorithmus als Übung zum Einstieg in C zu programmieren . Jedoch liefert mir diese Methode:

unsigned int potenz(int exp,int bas,int n)
{
        unsigned int erg=0;
        int mo=exp%2;
        int x;
        if(mo!=0)
        {
                erg=bas%n * potenz(exp-1,bas,n)%n;
                return(erg%n);
        }else
        {
                erg=bas*bas;
                erg=erg%n;
                x= exp/2;
                while(x >0)
                {
                        erg=erg*erg;
                        x--;
                        printf("%d\n",erg);
                }
                return(erg%n);
        }

}

meistens 0 zurück sie soll x^y mod n berechnen aber irgendwas stimmt dadrin nicht. Ich komme nur leider nicht von selbst drauf. Würde mich über Hilfe freuen!
Gruß HiFish

[volkard]

kann deinem code nicht ganz folgen.
wenn exp ungerade ist, rufste potenz(exp-1)bas. ok, klingt logisch.
wenn exp aber gerade ist, dann
-halbierst du exp
-quadrierst erg
gehste in ne schleife.
und machst
erg=ergerg;//quadrierst erg
x--;//paßt nicht.
gemeint war wohl
erg=erg*bas;

aber unabhängig vom fehler, ist die sache auch zu lahm. wenn ich 2^65536 rechnen will, schmeißt er mich in ne schleife vin 32768.

mach lieber so:
potenz(bas,exp,n) ist
-wenn exp==1 dann bas%n
-wenn exp gerade, dann potenz(bas,exp/2,n)*potenz(bas,exp/2,n)%n
-wenn exp ungerade, dann potenz(bas,exp-1,n)*bas%n
das sorgt dafür, daß exp mindesten in jedem zweiten schritt halbiert wird, weil es ja immer, wenn halbieren nicht geht, weil exp ungerade ist, exp gerade macht und danach geht halbieren.

[derBaer]

ich denke mal das Dein Fehler hier zu suchen ist:
return(erg%n);

Als Rückgabewert machst Du immer eine Restwert-Division und das führt zwangsläufig dazu, dass du hier:
erg=bas%n * potenz(exp-1,bas,n)%n;

irgend wann mit 0 Multiplizierst. Und irgendwas mal 0 ist ? na was wohl ?

[volkard]

derBaer schrieb:

ich denke mal das Dein Fehler hier zu suchen ist:
return(erg%n);

Als Rückgabewert machst Du immer eine Restwert-Division und das führt zwangsläufig dazu, dass du hier:
erg=bas%n * potenz(exp-1,bas,n)%n;

irgend wann mit 0 Multiplizierst. Und irgendwas mal 0 ist ? na was wohl ?

nee. normalerweise fällt man in nen zyklus rein.
zum beispiel nehme ich mal die potenzen von 2.
2
4
8
16
32
64
128
256
...
wenn ich das endergebnis immer %10 hinschreibe, kommt
2
4
8
6
2
4
8
6
...
und ich kann innendrin so oft ich mag, %10 rechnen, das ändert nichts am ergebnis. im gegenzeil, es ist notwendig, um keinen fehler durch überlauf zu bekommen. richtig ist, daß die originalversion ein bißchen oft %n rechnete, das kostet aber nur rechenzeit, wenn man es zweimal zweimal macht, schadet aber nicht.

[HiFish]

erstmal danke für die Hilfestellungen.
Also mit deinem Ansatz Volkard kommt wieder ne 0 raus. habs grad mal mit:
exp 10
bas 2
n 3
ausprobiert gibt 0.

unsigned int potenz(int exp,int bas,int n)
{
        unsigned int erg=0;
        int mo=exp%2;

        if(exp==1)
        {
                erg=bas%n;
                return(erg);
        }
        if(mo!=0)
        {
                erg=bas%n * potenz(exp-1,bas,n)%n;
                return(erg);
        }else
        {
                erg=(potenz(exp/2,erg,n)*potenz(exp/2,erg,n))%n;
                return(erg);
        }
}

[volkard]

erg=(potenz(exp/2,erg,n)*potenz(exp/2,erg,n))%n;
=>
erg=(potenz(exp/2,bas,n)*potenz(exp/2,bas,n))%n;

übrigens ist die leerzeichensetzung bei
erg=bas%n * potenz(exp-1,bas,n)%n;
sehr verwirrend. vielleicht besser, das äquivalente
erg=(bas%n * potenz(exp-1,bas,n)) % n;
zu schreiben.

[HiFish]

ok vielen dank jetzt funktioniert es