Arithmethik auf endlichen Mengen: Grundlegende Fragen

[Phoenix]

Hi.

Zuerst: JA, das ist die falsche Sparte, weil es hier eigentlich gar nicht um Programmierung geht. In keiner Sprache. Aber das sind eigentlich Dinge, die einen Informatiker im Bereich Kryptologie interessieren müssten und es sind Dinge, die ich als Grundlagen für recht wichtig erachte und von denen ich nicht möchte, dass sie in K&T untergehen. Ein Forum für theoretische Informatik haben wir ja (noch? @Daniel) nicht. ;-)

Also Hintergrund: Ich büffel gerade für meine Datensicherheit-Klausur am Dienstag und im Gegensatz zu den sonstigen Klausueren sind bei DASI absolut keinerlei Hilfsmittel erlaubt. In so ziemlich jedem anderen Fach dürfen wir alles mitnehmen, hier halt nicht - noch nichtmal nen stinknormalen Taschenrechner.

Dennoch kamen in den Übungsaufgaben ab und zu so Dinge an wie "was ist 10^56 mod 13?" dran - und ich frag mich gerade ernsthaft, wie man sowas im Kopf bzw. auf dem Papier berechnen kann. Wobei das selbst meinen normaler Taschenrechner überfordert, mein großer sagt mir zwar recht flott, dass da 9 rauskommt, aber das hilft mir nicht sondelrich weiter.

Also erstmal hierzu: Gibt es irgendwelche Tipps & Tricks, wie man sowas relativ geschickt zu Fuss lösen kann?

[Robert Marquardt]

Also der Ansatz duerfte ueber die Primfaktoren laufen.
10^56 hat nur die Primfaktoren 2 und 5. Der Windows Taschenrechner gibt mir bei 100 mod 13 auch 9 heraus. Da muss der Hund begraben sein.
Den Rest muss man jetzt nur noch beweisen.

Die Mathematik auf endlichen Mengen (genauer Ringen) hat sehr viel mit Programmieren zu tun. Was ist den das Zweierkomplement fuer die Darstellung von Integern anderes?

[Jürgen Thomas]

Hallo Phoenix,

Ein Ansatz dafür:
10^56 = (10^2)^28
damit:
10^56 mod 13 = (10^2 mod 13)^28 mod 13
= 9^28 mod 13 usw.

Ein schnellerer Weg für dieses Vorhaben fällt mir erstmal nicht ein. (Mein Mathe-Studium ist schon ein paar Tage her...) Aber vielleicht bringt Dich das auf entsprechende Ideen. Jürgen

PS. Natürlich war ich nicht schnell genug.

PS2. Ach je, Ringe... Ich erinnere mich gerade mal daran, dass es so etwas gibt.

[brechi]

10^56 = 10^(7*2*2*2) = [(10000000 mod 13)^(2*2*2)] mod 13 = 10^(2*2*2) mod 13 = [(100 mod 13) ^(2*2)] mod 13 = 9^(2*2) mod 13 =
[(31 mod 13)^2] mod 13 = 3^2 mod 13 = 9 mod 13 = 9

[Phoenix]

Zitat:

Zitat von Robert Marquardt

Die Mathematik auf endlichen Mengen (genauer Ringen)

Im konkreten Fall sogar ein Körper ;-)

[JasonDX]

Die Loesung solcher Aufgaben geht eigentlich sehr einfach, wenn man sich 2 Saetze im Hinterkopf behaelt:

1. a^b = a^b1 * a^b2 fuer b = b1 + b2
2. (a * b) mod c = ((a mod c) * (b mod c)) mod c

vor allem durch #2 kann man die Aufgabe sehr vereinfachen: statt einer Multiplikation zweier grosser Zahlen erhaelt man die Multiplikation 2er Zahlen < c :)

greetz
Mike

PS: Keinen Taschenrechner in der Klausur? Willkommen im Club ;)

[Robert Marquardt]

Zitat:

Zitat von Phoenix

Zitat:

Zitat von Robert Marquardt

Die Mathematik auf endlichen Mengen (genauer Ringen)

Im konkreten Fall sogar ein Körper ;-)

Ich habe Informatik studiert (in den 80ern) und keine Mathematik. Es hilft mir nur ein gutes Gedaechtnis.
Wenigstens war da ein Schwung Mathematik dabei. Wie ist das heutzutage?

[JasonDX]

Zitat:

Zitat von Robert Marquardt

Ich habe Informatik studiert (in den 80ern) und keine Mathematik. Es hilft mir nur ein gutes Gedaechtnis.
Wenigstens war da ein Schwung Mathematik dabei. Wie ist das heutzutage?

Bei uns (TUM) is genug Mathe dabei: Von Diskreten Strukturen ueber Lineare Algebra und Analysis hin bis zu Stochastik haben wir jedes Semester irgendeine Vorlesung, die ich nicht bestehn werde :mrgreen:

greetz
Mike