Java Code erklären

[Tiny9014]

Hallo, bin absoluter Anfänger im Programmieren mit Java. Kann mir jemand helfen und folgenden Code schrittweise erklären. Es geht um eine Moduloberechnung. Gerne auch an einem Besipiel, wie 15

public class Pow {
    public static void main(String[] args){
        int x = Integer.parseInt(args[0]);
        int k = Integer.parseInt(args[1]);
        int n = Integer.parseInt(args[2]);
        
        System.out.print(x+"pow"+k+" mod "+n+" = "+ pow(x, k, n));
     }

       
            static int pow( int x, int k, int n) {
                int ergebnis=1;
                while (k !=0) {
                    if (k%2 !=0) ergebnis = (ergebnis*x)%n;
                x =(x*x)% n; k = k/2;
                }
                return ergebnis;
            }
}

^23mod13.

 

[Xyz1]

^23mod13

??

Power ist doch schonmal ein Indiz dafür dass es sich um Potenzierungen handeln könnte....

 

[Tiny9014]

Meine Frage ist eher, was genau in diesen beiden Zeilen passiert. Gerne anhand eines Beispiels erklärt. Ich weiß leider nicht was das k= k/2 bezweckt

if (k%2 !=0) ergebnis = (ergebnis*x)%n;
x =(x*x)% n; k = k/2;

 

[Xyz1]

Falls es Dich tröstet, ich auch nich

 

[Tiny9014]

Allerdings kann ich es auch nicht weglassen, da ich dann keine zeitnahe Ausgabe habe. Kannst du mir möglicherweise weiterhelfen wie der Code auszusehen hat?

 

[Robat]

Der Code beschreibt mEn genau dieses Problem: schnelle modulare Exponentialrechnung
Wenn man sich die einzelnen Werte pro Iteration mal ausgeben lässt und sich die Beschreibung in dem Link durchliest erkennt man eigentlich recht schnell, warum was gemacht werden muss.
Beispiel für basis = x = 7, exponent = k = 256 und mod = n = 13

Iteration | Basis | Exponent | Ergebnis
        1 |    10 |      128 |        1
        2 |     9 |       64 |        1
        3 |     3 |       32 |        1
        4 |     9 |       16 |        1
        5 |     3 |        8 |        1
        6 |     9 |        4 |        1
        7 |     3 |        2 |        1
        8 |     9 |        1 |        1
        9 |     3 |        0 |        9

 

[Tiny9014]

x =(x*x)% n;

Könntest du mir auch erklären, was hier genau passiert?

 

[Robat]

Naja was soll man dazu sagen.
Du hast einen Wert x und multiplizierst ihn mit sich selbst (errechnest das also Quadrat von x) und dieses Ergebnis rechnest du modulo n.
Modulo (%) bestimmt den Rest aus einer Division zweier ganzer Zahlen