Laufzeit des "kleinen Fermat" < Algorithmen < Schule < Informatik < Vorhilfe
|
Hallo Leute,
ich weiss nicht wie ich die Laufzeit einer Kongruenz bestimme bzw. der Potenz in der Kongruenz um die es eigentlich geht.
Es geht wie oben beschrieben um den kleinen Fermat.
[mm]a^{p-1} \equiv 1 \mod p[/mm]
^^das soll eig a^(p-1) heissen. Habs nicht hinbekommen, dass er alles in den Exponenten packt...
Wie soll ich da auf Logarithmisches Wachstum kommen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:40 Di 07.08.2007 | | Autor: | Gilga |
Schön, dass in der Schule der kleine Fermat dran kommt.
Leider versteh ich nicht ganz was du meinst. Meinst du die Komplexität der Berechnung von Potenzen in Restklassen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:55 Di 07.08.2007 | | Autor: | TheEraser |
Genau das meine ich.
Die O-Notation / Laufzeitkomplexität.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:00 Di 07.08.2007 | | Autor: | Gilga |
Macht man sowas im Mathe LK?
Wichtig bei solchen Aufgabe ist die Länge der Eingabe.
In diesem Fall also 2 Zahlen a und p. Die Länge ist immer Logarithmisch.
z.B. zur Basis 2 wenn man sie binär kodiert oder zur Basis wie in unserem Dezimalsystem log(100000)+1= 6 Stellen.( Man muss auch richtig runden ... ist aber egal wenn man asymptotische komplexität berechnet.
Betrachtet man jetzt allgemein die Multiplikation von 2 Zahlen a und b der Länge log(a)= n und log(b)=m und multipliziert wie in der Schule (eine Ziffer nach der anderen multi. dann alles addieren) kostet die Multiplikation von einer Ziffer von b mit a log(a)=n . Das muss man m mal machen. Zusammenadieren muss man dann m Zahlen der maximalen Länge n+m. Also n*m+(n+m)*m
Bei Restklassen mit p Elementen ist die Länge ja durch log(p) begrenzt.
Dann sollte insgesamt [mm] O(log(a)^2+log(a)*log(p)) [/mm] = [mm] O(log(p)^2) [/mm] rauskommen. Ich denk mal es gilt a<=p.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:09 Di 07.08.2007 | | Autor: | TheEraser |
Boah. Ich danke dir. Genau das wollte ich wissen.
Jo das kommt im LK dran. Aber ein Grossteil ist Eigeninteresse ;)
Danke dir!
|
|
|
| |
|
Tut mir leid, dass ich das Ganze hier nocheinmal aufwühle, aber ich steig doch nich so ganz dahinter...
Ich habs mal an dem Beispiel [mm]22^{996} mod [/mm] 997 probiert.
log(2)+1 = 1
log(11)+1 = 2 (stur für mein Beispiel gerundet ;) )
Aber ab hier komm ich da jetzt nicht mehr klar:
> kostet die Multiplikation von einer Ziffer von b mit a log(a)=n
Kann mir da nochmal bitte jmd. auf die Sprünge helfen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Mo 17.09.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
