HÜ-A1

Benutzeravatar
timo.b
Mausschubser
Mausschubser
Beiträge: 79
Registriert: 28. Sep 2009 16:18

HÜ-A1

Beitrag von timo.b »

Hallo,
darf ich die Methode modPow(BigInteger exponent, BigInteger m) aus der Klasse BigInteger verwenden oder widerspricht das der Aufgabenstellung? Ich bin mir unsicher.

JavaDoc beschreibt die Methode wie folgt:
Returns a BigInteger whose value is (this^exponent mod m).
In der Aufgabenstellung steht:
Dies gilt jedoch nicht für den aus der Vorlesung bekannten effizienten Algorithmus zum Exponenzieren modulo n und den (erweiterten) Euklidischen Algorithmus!
Viele Grüße Timo

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: HÜ-A1

Beitrag von olg »

du hast dir deine Frage doch gerade selbst beantwortet... Du sollst für \(a^{exp} \text{ (mod n)}\) und \(ggt(a,b)\) nicht auf fertige Strukturen zurückgreifen. Das heißt, dass du modPow nicht verwenden darfst.
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

Benutzeravatar
timo.b
Mausschubser
Mausschubser
Beiträge: 79
Registriert: 28. Sep 2009 16:18

Re: HÜ-A1

Beitrag von timo.b »

Ja, ich fürchte, dass das dann doch sehr klar ist. Ich hatte Hoffnung... :P

Tribune
Erstie
Erstie
Beiträge: 16
Registriert: 23. Okt 2009 12:12

Re: HÜ-A1

Beitrag von Tribune »

Hallo zusammen,

in diesem Zusammenhang habe ich auch nochmal eine Frage:

meine Methode die den erweiterten Euklidischen Algorythmus benutzt will nicht so ganz funktionieren.
Kann von euch jemand mal folgende Beispieloperation ausführen:

Code: Alles auswählen

	BigInteger x = new BigInteger("2342345");
		BigInteger y = new BigInteger("768456345634645745674567");
			
		System.out.println(y.mod(x));
Das Ergebnis sollte 1797931 lauten, Java gibt bei mir aber 1799402 aus. Zu diesen Abweichungen kommt es bei mir nur bei großen Zahlen, ich bekomme es aber absolut nicht in den Griff.
Hat jemand eine Idee wie es dazu kommt??

nicolas
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 29. Jan 2010 12:56

Re: HÜ-A1

Beitrag von nicolas »

Keine Ahnung wie du auf 1797931 kommst. 1799402 ist das richtige Ergebnis.

Tribune
Erstie
Erstie
Beiträge: 16
Registriert: 23. Okt 2009 12:12

Re: HÜ-A1

Beitrag von Tribune »

Okay stimmt, vergessen wir mal den Windows Taschenrechner als Referenz! Die Zahl scheint er häufiger auszugeben.
Irgendwo hakt es scheinbar immernoch... Die großen Zahlen können einem ganz schöne Probleme bereiten.

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: HÜ-A1

Beitrag von Steven »

Wenn du etwas nachrechnen möchtest, empfehle ich dir PariGP. Das Programm ist kostenlos und kann so ziemlich alles, was man im Bereich Zahlentheorie normalerweise braucht. Der Windows-Taschenrechner ist für derart große Zahlen kein geeignetes Mittel, genauso wenig wie Rechenbretter, Abzählen an Reiskörnern etc.

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ-A1

Beitrag von Dennis Albrecht »

Im Allgemeinen kannst du den Rechenoperationen mit BigIntegern trauen (da die Zahlen ja in einem Array hinterlegt sind, sollte Java ja auch keine Ziffern vergessen können :D). Ich hatte mir eine Excel (bzw. OpenOffice :wink: )-Tabelle erstellt, um zu testen, ob meine Schlüsselpärchen stimmen (n=143). Dabei hat Excel behauptet, dass die meisten Nachrichten nicht korrekt en- und decodiert wurden. So hatte ich, obwohl ich unabhängig von Java mal meine Keys testen wollte, auf Java zurückgegriffen und alle Codierungen im gesamten Wortraum waren richtig. Solch lächerliche Zahlenspielchen mit einem derart winzigen n haben schon gezeigt, dass die meisten Standart-Rechenhilfen , die einmal das Studium gelegentlich erleichtern, hier schon zum erliegen kommen. (WolframAlpha wollte ich nicht bemühen, dort solltest du aber auch auf ordentliche Ergebnisse stoßen).

ez22
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 28. Mär 2011 14:52

Re: HÜ-A1

Beitrag von ez22 »

Ich habe eine Frage zu dem m (zu verschlüsselte Nachricht). diese Zahl wird als ganze Zahl betrachtet bei der Verschlüsselung oder muss man jede Zahl des Strings durchgehen und verschlüsseln?

großen Dank!

Dennis Albrecht
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 222
Registriert: 4. Okt 2010 18:15

Re: HÜ-A1

Beitrag von Dennis Albrecht »

m ist eine 41-stellige (wenn ich mich nicht verzählt habe) Dezimalzahl.

Gruß

Antworten

Zurück zu „Archiv“