Potenz modulo irgendwas "schnell" ausrechnen?

Neue Frage »

cmenke Auf diesen Beitrag antworten »
Potenz modulo irgendwas "schnell" ausrechnen?
Hallo,

Wenn man

ausrechnen will, kann man das mit einem Trick ja ziemlich schnell machen. Ich soll

berechnen und habe nach etwas Tüftelei rausgefunden dass sich der Rest mit einer Periode von 4 wiederholt: 7, 4, 13, 1, 7, 4, 13, 1, ... habe dann festgestellt, dass 350 mod 4 = 2, also sollte es der zweite Rest sein (zufällig genau 4). Das passt auch. Für die ganze Angelegenheit habe ich aber eine Viertelstunde gebraucht und wenn mein Prof das in 2 Sekunden kann, will ich es in höchstens 20 schaffen! :-)

Kann mir jemand erklären, wie das "schnell" geht bzw. was dahinter steckt?

Danke und Gruß und guten Rutsch,

cmenke
AD Auf diesen Beitrag antworten »
RE: Potenz modulo irgendwas "schnell" ausrechnen?
Naja, 20 Sekunden ist für allgemeine x,y,m schon ziemlich ambitioniert...

Zumindest für teilerfremde x,m hilft der Satz von Fermat-Euler

weiter, wobei die Anzahl der zu m teilerfremden positiven ganzen Zahlen kleiner m ist.

Hier z.B. ist , also ist sofort klar.

Und für das kleinste positive d mit gilt auf jeden Fall , hier z.B. 4|8.


Sind x und m nicht teilerfremd, wird alles natürlich ein wenig komplizierter.


Vielleicht kann dich einer der Moderatoren ja mal mit einem passenden Link über Zahlentheorie versorgen...
PK Auf diesen Beitrag antworten »

siehe höhere Mathematik, den RSA- Fred, da hab ich den Square and multiply- Algorithmus vorgeschlagen.
Mathespezialschüler Auf diesen Beitrag antworten »

Wie wärs hiermit. Wobei das in dem Fall immer noch rechenaufwändig ist.
PK Auf diesen Beitrag antworten »

Kann man leider nicht anwenden, weil 350 kein Vielfaches von ist
AD Auf diesen Beitrag antworten »

@PK

Richtig, aber die Reduktion 350=43*8+6 hilft ja auch schon ein Stück weiter.

Du hast natürlich recht - so richtig hilft das nur bei y >> m, sonst hat man nur wenig gewonnen. Augenzwinkern
 
 
PK Auf diesen Beitrag antworten »

OK, da geb ich dir recht smile

Wäre ja dann:


also
cmenke Auf diesen Beitrag antworten »

OK, in diesem Fall sind x und m ja teilerfremd und ich gehe mal davon aus, dass dann nur solche Fälle von Interesse sind.
Aber wie ich mit dem Satz jetzt zur Lösung komme, leuchtet mir noch nicht ein.

Das habe ich verstanden, aber wie komme ich damit zu des Rätsels Lösung?
Vielleicht so: Ich weiß jetzt dass die Reste sich spätestens beim Exponenten 8 wiederholen, vielleicht auch schon früher (weil gilt, dass der kleinste Exponent mit Rest 1 Teiler von 8 ist) und kann den Exponenten modulo 8 nehmen?
Komme dann auf 6 und 7^6 muss ich im Kopf ausrechnen, modulo 15 nehmen und fertig?

Keine Ahnung ob das so richtig ist, ich... äh... stehe bei diesem Thema ein bisschen im Dunkeln... Augenzwinkern

Gruß,

cmenke
PK Auf diesen Beitrag antworten »

also, bei diesem Modulokram gibt's viele Freiheiten:

Beim satz von Euler-Fermat gilt: Für jede natürliche Zahl k gilt, wenn a und n teilerfremd sind:


so, das ist das mit dem 43*8, das ist dann weg und ab dann kannst du ja rechnen
cmenke Auf diesen Beitrag antworten »

OK, im Kopf geht das allerdings noch nicht. Aber ich kann dann ja durch ausrechnen der ersten 8 Reste schnell zeigen, dass die Periode 4 ist, 6 modulo 4 sind 2 und 7*7 schaffe selbst ich schnell im Kopf :-)
PK Auf diesen Beitrag antworten »

OK, da muss ich jetzt passen, das noch schneller zu machen. Vielleicht hat jemand anderes noch eine Idee, wie man das noch schneller rechnet.
Mathespezialschüler Auf diesen Beitrag antworten »

Zitat:
Original von cmenke
Komme dann auf 6 und 7^6 muss ich im Kopf ausrechnen, modulo 15 nehmen und fertig?

Das meinte ich oben mit rechenaufwändig.

Zitat:
Original von cmenke
OK, im Kopf geht das allerdings noch nicht. Aber ich kann dann ja durch ausrechnen der ersten 8 Reste schnell zeigen, dass die Periode 4 ist, 6 modulo 4 sind 2 und 7*7 schaffe selbst ich schnell im Kopf :-)

Wenn die Reste sich wirklich mit der Periode 4 wiederholen, dann geht das natürlich!
cmenke Auf diesen Beitrag antworten »

Zitat:
Original von Mathespezialschüler
Wenn die Reste sich wirklich mit der Periode 4 wiederholen, dann geht das natürlich!


Naja, ich weiß ja, dass die Periode höchstens 8 ist. Sie kann auch 2 oder 4 sein (= ein Teiler von 8 sein). Ich schaue mir also die ersten 8 Reste an und kann dann sagen "die ist 4!" wenn sie sich nach dem 4. schon wiederholt innerhalb der acht Reste, die ich betrachte.

EDIT: Natürlich brauche ich zum Ausrechnen der ersten acht Reste dann schon den Taschenrechner und rechne 7^6 dabei auch schon aus... Also ist die ganze Sache hinfällig.... aber.... ach schei.... Prost
AD Auf diesen Beitrag antworten »

Mir fällt grad noch was zu Fermat-Euler ein, was in den meisten Fällen zwar nicht viel bringt - hier aber schon:

Das oben angesprochenen minimale d mit ist genau dann gleich , falls x primitive Wurzel modulo m ist. Nun gibt es aber nur für (p ... ungerade Primzahl) primitive Wurzeln. Für alle anderen m gilt sogar , also .

Das kann man jetzt auch für m=15=3*5 anwenden, von daher ist auch klar, ohne dass man "rechnen" muss.
interessent Auf diesen Beitrag antworten »

oder ich mach das ordentlich und sage das ich nach euler-fermat nur 350 mod phi(15) als hochzahl von 7 brauche und der rest wegfällt (im modulo 1 ist).
also 350 mod 8 = 6 (wobei dieser teil im kopf noch eher schwierig ist)
-> 7^350 === 7^6 mod 15
und ab da sollts dann im kopf schon kein problem mehr sein, denn 7^2 *7^2 *7^2 mod 15
ist der modulo der teiler also 4*4*4 mod 15 und 16*4===1*4 mod 15 -->
7^350 mod 15 = 4
Mystic Auf diesen Beitrag antworten »

Ja, Arthur hat es ja schon angesprochen, trotzdem ist es für mich immer wieder verblüffend, dass die Leute geradezu "vernarrt" in den Satz von Euler-Fermat sind, obwohl doch der "richtige" (im Sinne von "optimale") Satz hier lautet



wobei die sog. Carmichalefunktion bezeichnet... Natürlich muss man dann auch hier wieder sehen, ob die echte Ordnung von a nicht noch kleiner ist, aber man startet halt von vornherein aus einer günstigeren Position... Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

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