Rechenregeln modulare Arithmetik |
08.04.2016, 13:11 | KlausiMausi12345 | Auf diesen Beitrag antworten » | ||||||
Rechenregeln modulare Arithmetik [1] a) 283328383 mod 23838 = x b) x mod 2883 = 292 c) 3837473 mod x = 2982 [2] a) 338383 x mod 2238 b) 3485734 2728 mod x [3] a) 3738937^x mod 2837 = 271 b) mod 398 = 281 [4] a) 3738937^x 3453 mod 2837 b) x mod 2837 Meine Ideen: Hallo! Es gibt bei der modularen Arithmetik ein paar Rechenaufgaben, bei denen ich nicht ganz sicher bin, wie man da am schnellsten zum Ergebnis kommt. Ich habe extra große Zahlen gewählt, weil man bei kleine Zahlen ja oft leicht im Kopf rechnen kann. [1] a) Wie findet man das am schnellsten? Euklidischer Algorithmus? b) Hier muss man ja rechnen x = k*2883 + 292, oder? Wie geht man da am besten vor? c) Hier lautet die Gleichung: 3837473 = k*x + 2982, richtig? Wie geht man denn hier vor? [2] a) Hier muss man ja rechnen: 338383 mod 2238 = x mod 2238, oder? links wieder der Euklid. Alg. und rechts so wie in Aufgabe [1] b). b) Hier muss man lösen: 3485734 mod x = 2728 mod x, also wie in Aufgabe [1] c. [3] a) Wie löst man sowas? Hab da gar keinen Ansatz b) Ebenso... keinen Plan. [4] a) Das ist ja der diskrete Logarithmus. Da weiß ich, wie man den schnell löst ;-) b) Das kann man umformen zu mod 2837 = x mod 2837, dann gilt für die rechte Seite wieder dasselbe wir in [1] b. Stimmen die Ansätze soweit? Mir geht es bei allen Ansätzen darum, wie man das bei großen Zahlen schnell macht. |
||||||||
08.04.2016, 18:21 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Division mit Rest, und letzterer ist hier ja gesucht.
Was willst du denn noch weiter "vorgehen"? k*2883 + 292 ist die Lösung, mit beliebigem ganzzahligen k.
Nun, die 2982 kannst du durch Subtrahieren rüber bringen. Dann steht da ein Produkt k*x, welches gleich einer festen, dir bekannten Zahl sein soll ... da kann es je nach Primfaktorzerlegung dieser Zahl eine ganze Menge Lösungen geben. Allerdings kommen davon nur Werte x>2982 in Frage, weil für kleinere ja nicht der Rest 2982 entstehen kann. |
||||||||
08.04.2016, 20:13 | KlausiMausi12345 | Auf diesen Beitrag antworten » | ||||||
Hallo HAL 9000 Klar, ich Depp, da geht ja jedes k Danke soweit mal! Wie wäre es bei 3 a) und b)? Da ist ja nicht die Kongruenz gesucht, sondern der Wert. Wie ist da der Ansatz? |
||||||||
09.04.2016, 10:48 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Zu 3a) 2837 ist Primzahl, und es ist . Nach kleinem Fermat ist mit jeder Lösung auch die gesamte Restklasse Lösung. Was die Bestimmung eines angeht (bzw. ob es überhaupt eines gibt): Ich hab nicht sonderlich viel Ahnung von Algorithmen zur Berechnung des diskreten Logarithmus, ich weiß nur, dass sie sämtlich nicht sonderlich schnell sind. Bei Primmodul 2837 kann man natürlich primitiverweise alle 2836 Exponenten durchprobieren, zumindest mit rechentechnischer Unterstützung. Zu 3b) Zunächst die Primfaktorzerlegung des Moduls: . Modulo 2 muss daher gelten, also . Modulo 199 haben wir via kleinem Fermat , wegen . Und wieder fällt mir da erstmal nix besseres ein, als per Brute-Force alle durchzuprobieren... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|