Maximalwert einer Funktion < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
Hallo,
ich brauche für die Anwendung des RSA Verschlüsselungsalgorithmus den maximalen Funktionswert folgender Funktion:
$ [mm] MOD(64^{2^{16} + 1}, [/mm] 18779) $
oder anders geschrieben:
$ [mm] 64^{2^{16} + 1} [/mm] mod 18779 $
Wie könnte man das Problem angehen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:12 Sa 08.03.2008 | | Autor: | abakus |
> Hallo,
>
> ich brauche für die Anwendung des RSA
> Verschlüsselungsalgorithmus den maximalen Funktionswert
> folgender Funktion:
>
> [mm]MOD(64^{2^{16} + 1}, 18779)[/mm]
>
> oder anders geschrieben:
>
> [mm]64^{2^{16} + 1} mod 18779[/mm]
>
> Wie könnte man das Problem angehen?
Hallo,
schade, dass 18779 keine Primzahl ist. Dort kämen nämlich von [mm] 64^1 [/mm] bis [mm] 64^{18778} [/mm] garantiert ALLE möglichen Reste (außer Null), also die Reste 1 bis 18778) einmal vor. So kommen nicht alle Reste vor
Es ist 18779=211*89.
Musst du es genau wissen, oder reicht eine Abschätzung? Sehr weit wird der größte Rest nicht vom maximal möglichen Rest 18778 entfernt sein. Die Potenzen von 64 lassen der Reihe nach verschiedene Reste, bis einmal der Rest "1" auftritt. Dann beginnen die Reste zyklisch von vorn.
Kannst du dir nicht ein Programm schreiben, das die Reste von [mm] 64^n [/mm] ermittelt und abbricht, wenn der Wert 1 erreicht ist (zwischendurch muss natürlich immer der bisherige Maximalrest registriert werden)?
Viele Grüße
Abakus
PS: Du brauchst kein Programm. Ich habe die Folge der Reste mal in einer Excel-Tabelle durchlaufen lassen. Bereits bei [mm] 64^{385} [/mm] tritt der Rest 1 auf, danach wiederholt sich alles. Der maximale Rest wird also innerhalb der ersten 384 Potenzen von 64 erreicht.
|
|
|
| |
|
Hallo,
schon einmal Danke für Deine Antwort.
Die allgemeine Formel, welche dem ganzen zu Grunde liegt heißt
$ [mm] k^{e} [/mm] mod N $
e und N sind Konstanten. k ist ein variabler Wert (die zur verschlüsselnde Zahl).
N kann keine Primzahl sein, da sie ein Produkt zweier solcher ist (p*q).
Eigentlich muss ich mich korrigieren, denn mich interessiert weniger der Maximale Wert, als die maximale Anzahl der Stellen des Wertes.
Denn ich habe folgendes Problem:
Ich möchte verschiedene Buchstaben (z.B. A,B,C) kodieren.
Nun entsprechen diese den ASCII Werten 65,66,67. Diese setze ich für k ein.
Nun variiert die Länge der Ergebnisse. Ich muss aber wissen, wie lang die Ergebnisse werden können (maximal). Und dieses Wissen muss ich aus e und N ziehen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:47 Sa 08.03.2008 | | Autor: | abakus |
> Hallo,
>
> schon einmal Danke für Deine Antwort.
>
> Die allgemeine Formel, welche dem ganzen zu Grunde liegt
> heißt
>
> [mm]k^{e} mod N[/mm]
>
> e und N sind Konstanten. k ist ein variabler Wert (die zur
> verschlüsselnde Zahl).
>
> N kann keine Primzahl sein, da sie ein Produkt zweier
> solcher ist (p*q).
>
>
>
> Eigentlich muss ich mich korrigieren, denn mich
> interessiert weniger der Maximale Wert, als die maximale
> Anzahl der Stellen des Wertes.
>
> Denn ich habe folgendes Problem:
>
> Ich möchte verschiedene Buchstaben (z.B. A,B,C) kodieren.
> Nun entsprechen diese den ASCII Werten 65,66,67. Diese
> setze ich für k ein.
>
> Nun variiert die Länge der Ergebnisse. Ich muss aber
> wissen, wie lang die Ergebnisse werden können (maximal).
> Und dieses Wissen muss ich aus e und N ziehen.
Wie schon gesagt,
der maximal mögliche Rest irgendeines Terms bei Teilung durck N ist N-1. Wenn N wiederum da Produkt anderer Zahlen ist, ergibt sich die Stellenzahl von N aus den Faktoren. Zur Ermittlung der Stellenzahl des Ergebnsses must du nur die Zehnerlogarithmen der Faktoren addieren (und 1 dazugeben, denn z.B. [mm] 10^3=1000 [/mm] hat nicht 3, sondern 4 Stellen).
Viele Grüße
Abakus
|
|
|
| |
|
Danke. Das hat mir sehr weitergeholfen :)
|
|
|
|
