Square and Multiply Algorithmus

Neue Frage »

GuitarExot90 Auf diesen Beitrag antworten »
Square and Multiply Algorithmus
Meine Frage:
Hallo Mathefreunde :-)

Ich möchte gern die letzten 3 Ziffern von und die letzten 2 Ziffern von ermitteln. Ich weiß, dass es einen Square and Multiply Algorithmus dafür gibt, jedoch bin ich noch nicht wirklich dahinter gestiegen :-(

Meine Ideen:
Bei kleinen Zahlen wie löse ich es mit:
also unter Anwendung der Potenzgesetze. Doch wie mache ich das bei großen Zahlen? :-( Gibt es dort soetwas wie eine Primfaktorzerlegung?
Ich hoffe ihr könnt es mir erklären.

Viele Grüße,
GuitarExot90
galoisseinbruder Auf diesen Beitrag antworten »

Die Aufgabe geht mittels eulerscher -Funktion noch einfacher.


Der Square-and-multiply Algorithmus funktioniert im wesentlichen:
Du stellst den Exponenten e als Binärzahl dar: (z.B. ) berechnest (n ist die Länge der Binärzahl) und damit den Ergebnis, (z.B ) indem du nur die multiplizierst mit
GuitarExot90 Auf diesen Beitrag antworten »

Danke für die schnelle Antwort galoisseinbruder :-)

Ok die binäre Darstellung von 10 ist 1010. Aber wie kommst du auf ? Also wenn ich jetzt nehme, dann ist die binäre Darstellung von 413=110011101 --> n=9 --> ???
Tut mir leid, wenn ich mich etwas dusselig anstelle, aber wie bereits erwähnt steige ich nicht hinter den Sinn und Zweck dieses Algorithmuses. Was ich noch vergessen habe: meine Idee war noch die 2 Ziffer durch mod 100 und die 3 Ziffern mit mod 1000 zu bestimmen.

Viele Grüße,
GuitarExot90
galoisseinbruder Auf diesen Beitrag antworten »

da hat sich bei mir doch der Fehlerteufel eingschlichen:
Es heißt nicht:
sondern natürlich:
und auch
sollte besser so heißen:, denn dann ist

und damit und die Faktoren mit fallen weg.

Und mit dem mod hast Du recht, ich ging aber bereits davon aus, dass Du das tust.
(Die zahlen wären sonst auch ein bisschen groß)
GuitarExot90 Auf diesen Beitrag antworten »

Ist Square and Multiply nicht aber dazu da um mod zu vereinfachen? Ich bekomme es nicht in mein Gehirn verwirrt

Viele Grüße,
GuitarExot90
galoisseinbruder Auf diesen Beitrag antworten »

Square-and- multiply can in jeder (multiplikativ geschriebenen) Gruppe verwendet werden. Und ja er vereinfacht die Berechnung, da man relativ wenige Berechnungen machen muss.
Wo ist das Problem?
Führe ih einfach mal aus.
 
 
GuitarExot90 Auf diesen Beitrag antworten »

Ich habe mir etwas schwer getan, deswegen habe ich mal weiter recherchiert. Die binäre Darstellung von 413 ist 110011101. Jede 0 wird durch ein Q und jede 1 mit einem QM ersetzt, also erhalte ich: QM QM Q Q QM QM QM Q QM. Das führende Paar kann ich wegstreichen, also erhalte ich: QM Q Q QM QM QM Q QM. Und daraus folgt: Habe ich Recht?
GuitarExot90 Auf diesen Beitrag antworten »

Ich habe eben nachgerechnet und das ist die Lösung für . Aber wieso sollte es mir das Rechnen erleichtern?
galoisseinbruder Auf diesen Beitrag antworten »

Wie würdest Du es denn sonst ausrechnen?
GuitarExot90 Auf diesen Beitrag antworten »

Der Vorteil ist also nun, dass ich in 8 Schritten anstatt in 413 Schritten lösen kann? Und wie kann ich jetzt mod 100 darauf anwenden?

Viele Grüße,
GuitarExot90
galoisseinbruder Auf diesen Beitrag antworten »

Das ist doch ein ziemlicher Vorteil, oder?
Und da Dein Ergebnis bzgl mod 1000 gesucht ist rechnest Du mod 1000. (bei der 7-er Potenz warens die letzten 3 Ziffern).
z.B. ist usw.
GuitarExot90 Auf diesen Beitrag antworten »

Mir ist alles klar bis auf die . Wo erhalte ich diese? Tut mir leid, ich sehe es nicht :-(
galoisseinbruder Auf diesen Beitrag antworten »

Ich verstehe die Frage nicht. Ich habe nie behauptet das in deinem Verfahren die vorkommt. Das war ein Beispiel (durch das z.b. davor angezeigt)um zu zeigen was die berechnung modulo 1000 bewirkt. (es ist die kleinste 7-er Potenz wo was halbwegs interessantes passiert.)
GuitarExot90 Auf diesen Beitrag antworten »

Oh Verzeihung, hatte mich verlesen Big Laugh
Die letzten drei Ziffern von sind "407" und ich dachte dabei an deine Lösung "401". Entschuldigung für die Verwechselung. Um mir Alles zu vereinfachen könnte ich doch wiefolgt bei meinem langem Term vorgehen:
, dann und immer so weiter? Weil dann hätte ich endlich den Sinn dahinter verstanden smile
Du hattest auch noch das Beispiel angebracht. Leitet sich das aus der eulerschen -Funktion ab?

Viele Grüße,
GuitarExot90
galoisseinbruder Auf diesen Beitrag antworten »

Ja Du kannst, und solltest sogar, so vorgehen wie Du es gemacht hast.


Zitat:
Du hattest auch noch das Beispiel angebracht. Leitet sich das aus der eulerschen -Funktion ab?

Nein, das war kein Beispiel und hat auch nichts mite der Eulerschen -Funktion zu tun. Wenn Du genau liest was ich geschrieben habe gehört die Berechnung zum vom mir vorgeschlagen Berechnungsweg. Dieser unterscheidet sich zwar von Deinem ist aber auch dein Square-and multiply Algoithmus.
GuitarExot90 Auf diesen Beitrag antworten »

Achso ok. Ich frage nur, weil du erwähnt hast, es ginge mit der eulerschen -Funktion eventuell einfacher?!
galoisseinbruder Auf diesen Beitrag antworten »

Es geht mit der -Funktion (und dem Satz von Euler) deutlich einfacher. Aber da Du sie offensichtlich nicht kennst, darfst Du sie ja dann auch nicht benutzen.
GuitarExot90 Auf diesen Beitrag antworten »

Die eulersche -Funktion ist mir bekannt Augenzwinkern Mit ihr errechnet man die Anzahl an teilerfremden Zahlen zu einer Zahl aus. Dafür benötigt man die kanonische Darstellung. Die Formel lautet:

Mir war nur nicht ganz klar, wie diese Formel mir weiterhelfen sollte.
galoisseinbruder Auf diesen Beitrag antworten »

Kennst Dun denn den Satz von Euler? Das wäre hier die eigentliche Anwendung.
GuitarExot90 Auf diesen Beitrag antworten »

Der Satz von Euler-Fermat lautet:
galoisseinbruder Auf diesen Beitrag antworten »

Dann bestimm doch mal .
Damit haben wir dann
GuitarExot90 Auf diesen Beitrag antworten »

Also die kanonische Darstellung von 1000 ist:

Daraus folgt:

also:
galoisseinbruder Auf diesen Beitrag antworten »

So weit, so richtig.
Und was fällt Dir im Hinblick auf auf?
GuitarExot90 Auf diesen Beitrag antworten »

413-400=13? Oder die letzten drei Ziffern von sind "001"? :p
galoisseinbruder Auf diesen Beitrag antworten »

Alles korrekt.
Wenn Du es auf anwenden willst ergibst sich jetzt:

und ist doch deutlich angenehmer zu berechnen.
GuitarExot90 Auf diesen Beitrag antworten »

Hey du hast Recht! Augenzwinkern Mir fehlt es leider noch ein wenig an Kombinationsfähigkeit, aber du hast mir definitiv weitergeholfen! Danke dir galoisseinbruder smile Habe es jetzt verstanden. Augenzwinkern

Viele Grüße,
GuitarExot90
smile
Neue Frage »
Antworten »



Verwandte Themen

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