Potenz modulo irgendwas "schnell" ausrechnen? |
31.12.2004, 13:39 | cmenke | Auf diesen Beitrag antworten » | ||||
Potenz modulo irgendwas "schnell" ausrechnen? 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 |
||||||
31.12.2004, 14:18 | 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... |
||||||
31.12.2004, 14:18 | PK | Auf diesen Beitrag antworten » | ||||
siehe höhere Mathematik, den RSA- Fred, da hab ich den Square and multiply- Algorithmus vorgeschlagen. |
||||||
31.12.2004, 14:26 | Mathespezialschüler | Auf diesen Beitrag antworten » | ||||
Wie wärs hiermit. Wobei das in dem Fall immer noch rechenaufwändig ist. |
||||||
31.12.2004, 14:31 | PK | Auf diesen Beitrag antworten » | ||||
Kann man leider nicht anwenden, weil 350 kein Vielfaches von ist |
||||||
31.12.2004, 14:35 | 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. |
||||||
Anzeige | ||||||
|
||||||
31.12.2004, 14:35 | PK | Auf diesen Beitrag antworten » | ||||
OK, da geb ich dir recht Wäre ja dann: also |
||||||
31.12.2004, 16:07 | 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... Gruß, cmenke |
||||||
31.12.2004, 16:12 | 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 |
||||||
31.12.2004, 16:20 | 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 :-) |
||||||
31.12.2004, 16:23 | 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. |
||||||
31.12.2004, 20:57 | Mathespezialschüler | Auf diesen Beitrag antworten » | ||||
Das meinte ich oben mit rechenaufwändig.
Wenn die Reste sich wirklich mit der Periode 4 wiederholen, dann geht das natürlich! |
||||||
01.01.2005, 10:49 | cmenke | Auf diesen Beitrag antworten » | ||||
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.... |
||||||
01.01.2005, 13:12 | 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. |
||||||
10.05.2010, 18:44 | 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 |
||||||
10.05.2010, 20:31 | 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... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|