Lösungsweg 257^271 mod 379

Neue Frage »

TheNoxxer Auf diesen Beitrag antworten »
Lösungsweg 257^271 mod 379
Meine Frage:
Schreibe bald ne Klausur in Linearer Algebra und habe keinen plan wie ich die Restklasse von 257^271 mod 379 ausrechnen soll...

Meine Ideen:
Ich glaube das man da mit den Potzengesetzten ran gehen kann um das ein bissel einfacher zu machen....
Elvis Auf diesen Beitrag antworten »

Wenn mir nichts besseres einfällt, fange ich an zu rechnen : , so kommt man schon mal zu
HAL 9000 Auf diesen Beitrag antworten »

Fermat bzw. Fermat-Euler mal ausgeklammert (beide helfen im vorliegenden Fall ja auch nicht) ist eine mögliche sture, aber noch leidlich schnelle Methode zur Berechnung solcher Potenzen mit großen Exponenten die folgende:


Man berechnet die Binärdarstellung des Exponenten, hier wäre das .

Dann berechnet man via Rekursion und soweit wie nötig, d.h. bis .

Am Ende dann werden die gemäß Binärdarstellung auftretenden dann miteinander multipliziert, d.h.

.

Zitat:
Original von TheNoxxer
Ich glaube das man da mit den Potzengesetzten ran gehen kann um das ein bissel einfacher zu machen....

Genau darauf fußt auch die vorgestellte Methode: Die Potenzgesetze liefern



sowohl direkt, also auch modulo 379. Augenzwinkern
TheNoxxer Auf diesen Beitrag antworten »

Hi Elvis mit deinem Lösungsweg kann ich mehr anfangen weil meine Mathe Prof exotische Lösungen nicht gerne in Klausuren hat. Wenn ich deinen Weg jetzt weiter verfolge komme ich auf
5^15 konguent 124 mod 379 und damit auf 257^270 konguent 124 mod 379. Ist das soweit richtig und wie mache ich nun weiter ? Vielen Dank an dich und Hal9000 erstmal
TheNoxxer Auf diesen Beitrag antworten »

Ich meinte natürlich 5^15 konguent 119 mod 379
TheNoxxer Auf diesen Beitrag antworten »

Habe die Lösung selbst gefunden dennoch vielen Dank und eine Gute Nacht
 
 
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von TheNoxxer
weil meine Mathe Prof exotische Lösungen nicht gerne in Klausuren hat.

Einen geradlinigen und für derlei Potenzen universell anwendbaren Lösungsweg bezeichnest du als "exotisch"? Erstaunt1


Ein Verfahren, dass sich z.B. sehr kurz in Algorithmenform gießen lässt, hier in C:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
// Berechnet  a^n mod m
int ModulPotenz (int a, int n, int m)
{
    int p = 1;
    while (n > 0)
    {
        if (n & 1)
        {
            p = (p*a) % m;
        }
        a = (a*a) % m;
        n >>= 1;
    }
    return p;
}



P.S.: Der Lösungsweg von Elvis ist m.E. nur deshalb angenehm, weil mit der Potenz ein relativ niedriger Wert 5 erreicht wird, so dass man in einem Rutsch mit einem halbwegs leistungsfähigen TR ausrechnen kann. Elvis hat nun natürlich nur diesen Pfad hingeschrieben - ich weiß nicht, wieviel er probiert hat, bis er zu einem so angenehm niedrigen Potenzwert gekommen ist. Jedenfalls ist diese Probierzeit auch mit anzurechnen, wenn du sowas in der Klausur berechnen musst.
TheNoxxer Auf diesen Beitrag antworten »

Ich meinte mit exotisch eigentlich nur das wir es so nicht in der Uni gelernt haben und er meinte das er die volle Punktzahl gibt wenn wir ein Lösungsverfahren in der Vorlesung hatten.
HAL 9000 Auf diesen Beitrag antworten »

Welchen "nicht exotischen" Weg habt ihr denn kennengelernt? verwirrt

D.h., wie würdest du z.B. damit bestimmen (mal ohne externe Tipps zur geeigneten Exponentenzerlegung)?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »