Informatik: Potenzen fürs Volk
Released by matroid on So. 04. Juli 2004 21:39:34 [Statistics]
Written by Gockel - 8636 x read [Outline] Printable version Printer-friendly version -  Choose language   
Informatik

\(\begingroup\) Hallo, Programmier-Freunde.


Gerade bei aufwändigen Algorithmen und/oder dem Rechnen mit großen Zahlen kann es passieren, dass ein Algorithmus, der zwar einwandfrei funktioniert und gut zu implementieren ist, einfach nicht schnell genug ein Ergebnis liefert.
Dann wird nach schnelleren, effizienteren Algorithmen gesucht.

Am Beispiel des Potenzierens möchte ich euch vorführen, wie man mit "Mathematischer Trickserei" schnellere Algorithmen entwickeln kann.



Definitionen



Für eine Halbgruppe, d.h. ein Paar, bestehend aus einer nichtleeren Menge \IM und einer assoziativen, binären Verknüpfung * : \IM\cross\IM->\IM, ist das Potenzieren wie folgt definiert:
\forall n \el \IN_(>0), a \el \IM: a^1=a, a^(n+1)=a*a^n
Wenn es außerdem noch ein neutrales Element 1 \el \IM gibt, dann kann man auch n=0 mit einschließen, indem man a^0=1 definiert.

Dabei sind nur minimale Anforderungen an die Halbgruppen-Operation gestellt: Sie muss nur Assoziativ sein.
Vorteilhaft ist es auch, wenn ein neutrales Element existiert, aber notwendig ist nicht mal das.
Man beachte: Es ist nicht einmal Kommutativität erforderlich, da man ja nur a mit sich selbst multipliziert, weshalb sich das Potenzieren auf eine Unmenge von Strukturen anwenden lässt.


Außerdem werde ich für die Analysen der Algorithmen einige einfache Definitionen verwenden, die der Verkürzung der Schreibarbeit und der Übersichtlichkeit dienen soll:
a soll immer die Basis der Potenz (d.h. \el \IM),
n immer der Exponent sein (d.h. \el \IN).
L soll im folgenden binäre Stellenanzahl des Exponenten sein, d.h. L=floor(log(2,n))+1



Algorithmus P1



Die Definition der Potenz führt uns direkt zum ersten Algorithmus:

\sourceon P1a (ohne neutrales Element)
Eingabe:
a aus M,
n aus N, n ungleich 0
Ausgabe:
a^n

(1) Setze r=a
(2) Solange n > 1 wiederhole
(2.1) Setze r=r*a
(2.2) Setze n=n-1
(3) Gib r aus.
\sourceoff

\sourceon P1b (mit neutralem Element)
Eingabe:
a aus M,
n aus N,
Ausgabe:
a^n

(1) Setze r=1
(2) Solange n > 0 wiederhole
(2.1) Setze r=r*a
(2.2) Setze n=n-1
(3) Gib r aus.
\sourceoff

Dieser Algorithmus ist natürlich sehr ineffizient. Seine Laufzeit ist exponentiell in L, da man genau n-1 bzw n Multiplikationen braucht.
Damit ist er besonders für große n ungeeignet.


Algorithmus P2



Aber die Mathematik hilft uns weiter:
In Halbgruppen gelten die üblich Potenzgesetze, darunter auch (a^x)^y=a^xy=a^yx=(a^y)^x mit x,y \el \IN.
Deshalb gilt insbesondere a^2x=(a^x)^2 bzw. a^(2x+1)=a*(a^x)^2=(a^x)^2*a.
Daraus lässt sich ein deutlich schnellerer Algorithmus ableiten:


\sourceon P2a (ohne neutrales Element)
Eingabe:
a aus M,
n aus N, (n ungleich 0)
Ausgabe:
a^n
(1) Wenn n=1 gib a aus
(2) Wenn n=2 gib a*a aus
(3) Wenn n gerade setze r=P2a(a,n/2) und gib r*r aus
(4) Wenn n ungerade setze r=P2a(a,(n-1)/2) und gib r*r*a aus
\sourceoff

\sourceon P2b (mit neutralem Element)
Eingabe:
a aus M,
n aus N,
Ausgabe:
a^n
(1) Wenn n=0 gib 1 aus
(2) Wenn n=1 gib a aus
(3) Wenn n gerade setze r=P2b(a,n/2) und gib r*r aus
(4) Wenn n ungerade setze r=P2b(a,(n-1)/2) und gib r*r*a aus
\sourceoff

Dieser Algorithmus läuft deutlich schneller: Die Funktion wird L-mal aufgerufen. Es werden insgesamt (1+O(1))L Multiplikationen durchgeführt.
Allerdings wird auch der Speicherverbrauch mit jedem Aufruf größer, da für jede Funktionsinstanz der Speicherplatz für 2 Elemente aus \IM reserviert werden muss.
Außerdem sind rekursive Algorithmen nicht gerade als Ressourcenschonend bekannt ;)


Algorithmus P3



Wir versuchen also aus diesem rekusiven einen iterativen Algorithmus zu machen.
Dazu stellen wir den Exponenten binär dar (d.h. im 2er System):
n=sum(b_i*2^i,i=0,k) mit b_i\el{0,1}
Wobei k die Bitlänge von n ist.
Außerdem gilt, wovon man sich leicht überzeugen kann, a^(x+y)=a^x*a^y=a^y*a^x mit x,y \el \IN

Wenn wir jetzt das in die Potenz einsetzen, erhalten wir:
a^n=produkt(x^(b_i*2^i),i=0,L-1)=produkt(x^2^i,array(i=0;b_i=1),L-1)

Wenn man jetzt noch weiß, dass a^2^(i+1)=(a^2^i)^2 ist, kommt man zu folgendem Algorithmus, der unter dem Namen Square-And-Multiply Algorithmus bekannt ist:


\sourceon P3a (ohne neutrales Element)
Eingabe:
a aus M,
n aus N (n ungleich 0)
Ausgabe:
a^n

(1) Setze r=f=a und n=n-1
(2) Solange n>0 wiederhole:
(2.1) Falls n ungerade, setze r=r*f
(2.2) Setze n=floor(n/2)
(2.3) Setze f=f*f
(3) gib r aus.
\sourceoff

\sourceon P3b (mit neutralem Element)
Eingabe:
a aus M,
n aus N
Ausgabe:
a^n

(1) Setze r=1 und f=a
(2) Solange n>0 wiederhole:
(2.1) Falls n ungerade, setze r=r*f
(2.2) Setze n=floor(n/2)
(2.3) Setze f=f*f
(3) gib r aus.
\sourceoff

Hier sollte man sich nocheinmal genau durch den Kopf gehen lassen, was hier gerade passiert ist.
Schritt \ref(2.1) Testet auf die Bedingung b_i=1. Die Schritte \ref(2.2) und \ref(2.3) sorgen dafür, dass von einem i zum nächsten gesprungen wird, indem es den "mitlaufenden Faktor" f quadriert und n um ein Bit kürzt.
Dieser Algorithmus sorgt praktisch dafür, dass der Exponent bitweise "zusammengesetzt" wird, indem f immer 2er Potenzen als Exponent hat und durch den Schritt \ref(2.1.1) diese 2er Potenzen an die richtige Stelle im Exponenten gesetzt werden.

Der Square-And-Multiply Algoritmus ist sehr effizient er benötigt (1+O(1))L, also maximal 2L, Multiplkationen und ist damit linear in der Länge von n. Im Gegensatz zum rekursiven Algorithmus ist hier allerdings der Speicherverbrauch konstant.

Außerdem lässt er sich auf alle Halbgruppen anwenden und ist deshalb für allgemeine Aufgaben bestens geeignet, denn mit ihm kann man so gut wie alles potenzieren: quadratische Matrizen, Restklassen, ganze, reelle, komplexe Zahlen usw. usf.
Dabei muss nur die Implementierung der Gruppenoperation * verändert werden. Der Algorithmus selbst ist in allen Halbgruppen gültig und, soweit ich weiß, der am weitesten verbreitete allgemeingültige Potenzierungsalgorithmus (für natürliche Exponenten).


Algorithmus P4



Der schnellste ist er aber dennoch nicht. Man das Ganze noch verfeinern, indem man vom 2er-System ins 4er, 8er, 16 oder ein anderes Zahlensystem mit einer 2er-Potenz als Basis umsteigt.
Ich führe das mal am Beispiel 16=2^4 vor. Dazu stellen wir n wieder in diesem System dar:
n=sum(z_i*16^i,i=0,k) mit z_i \el {0000_2 ... 1111_2}

Ich hab hier z_i mit Absicht binär notiert, da auch dieses Verfahren auf das Binär-System zurückgreift. Ähnlich wie beim vorhergehenden Algorithmus, wird der Exponent schrittweise "zusammengebaut". Nur hier nicht Bit für Bit, sondern in 4-Bit Schritten. Dazu unterteilen wir den Exponenten in 4 bit große Blöcke und untersuchen man die Bits in den Blöcken. Der Algorithmus fügt dann sozusagen die Bits in den Blöcken an den Exponenten an.
Wenn wir an den Exponenten eine 0_2 anfügen, ihn also mit 2 multiplizieren, wollen dann quadrieren wir einfach. Das kennen wir schon vom Square-And-Multiply Algorithmus. Wenn wir aber beispielsweise 11_2 anfügen wollen, quadrieren wir zuerst 2 mal, um Platz für 2 bits zu schaffen sozusagen, und multiplizieren dann mit a^3, um diese Bits zu füllen. Analog verfahren wir mit den anderen ungeraden Zahlen bis 16. Bei Geraden Zahlen müssen wir einfach nur den ungeraden Anteil betrachten und den geraden Faktor durch anfügen von "Leerbits", sprich durch Quadrieren, zur Verfügung stellen.
Wenn man die ungeraden Potenzen vorher schon berechnet und zwischenspeichert, erhält man dadurch einen sehr großen Geschwindigkeitsgewinn, da pro 4-Bit-Block 4-5 Multiplikationen erforderlich sind. Nämlich genau 4 Quadrierungen und gegebenfalls die Multiplikation mit der jeweiligen ungeraden Potenz von a.


\sourceon P4a (ohne neutrales Element)
Eingabe:
a aus M,
n aus N (ungleich 0)
Ausgabe:
a^n

(1) p(i)=a^i mit i=1,3,5...15
(2) Ermittle die Anzahl der 4-Bit-Blocks, setze dazu i=floor(ln(n)/ln(16))
(3) Ermittle den i-ten Block, setze dazu B=(n/16^i) mod 16
(4) Ermittle B=x*2^t mit x ungerade
(5) Setze r=p(x)
(6) Quadriere r t-mal
(7) setze i=i-1
(8) Solange i>=0 wiederhole
(8.1) Ermittle den k-ten Block, setze dazu B=(n/16^i) mod 16
(8.2) Wenn B ungleich 0 ist, tue folgendes:
(8.2.1) Ermittle B=x*2^t mit x ungerade
(8.2.2) Quadriere r genau (4-t)-mal
(8.2.3) Multipliziere r mit p(x)
(8.2.4) Quadriere r t-mal
(8.3) Ansonsten quadriere r 4-mal
(8.4) Setze i=i-1
(9) Gib a aus.
\sourceoff

\sourceon P4b (mit neutralem Element)
Eingabe:
a aus M,
n aus N
Ausgabe:
a^n

(1) Setze r=1 und p(i)=a^i mit i=1,3,5...15
(2) Ermittle die Anzahl der 4-Bit-Blocks, setze dazu i=floor(ln(n)/ln(16))
(3) Solange i>=0 wiederhole
(3.1) Ermittle den i-ten Block, setze dazu B=(n/16^i) mod 16
(3.2) Wenn B ungleich 0 ist, tue folgendes:
(3.2.1) Ermittle B=x*2^t mit x ungerade
(3.2.2) Quadriere r (4-t)-mal
(3.2.3) Multipliziere r mit p(x)
(3.2.4) Quadriere r t-mal
(3.3) Ansonsten quadriere r 4-mal
(3.4) Setze i=i-1
(4) Gib r aus.
\sourceoff

Ich kann das Prinzip ja einmal an einem konkreten Beispiel verdeutlichen:
Betrachten wir ein beliebiges a aus einem beliebigen Monoid, also einer Halbgruppe mit neutralem Element, und n=2987_10=1110101011_2.
Wir gehen den Algorithmus P4b also schrittweise durch:
(Alle Exponenten sind jetzt binär notiert)

(1) Zuerst setzen wir r=1=a^0 und berechnen wir nacheinander a^1, a^11, a^101, a^111, a^1001, a^1011 und a^1111
(2) i=2; Es sind, wie man leicht erkennt 3 Blöcke: B_0, B_1 und B_2.

(3.1) B_2=0011_2 wird betrachtet
(3.2.1) x=11_2, t=0
(3.2.2) viermal quadrieren.. bringt aber noch nichts...
(3.2.3) jetzt aber: r*a^11=a^11
(3.2.4) nichts zu tun...
(3.4) okai... i=1 und noch mal das Ganze:

(3.1) B_1=1010_2
(3.2.1) x=101_2, t=1
(3.2.2) 3mal Quadrieren => r=a^11000
(3.2.3) mit a^101 multiplizieren => r=a^11101
(3.2.4) 1mal Quadrieren => r=a^111010
(3.4) okai... i=0 und das Ganze nochmal

(3.1) B_0=1011_2
(3.2.1) x=1011, t=0
(3.2.2) 4mal quadrieren => r=a^1110100000
(3.2.3) mit a^1011 multiplizieren => r=a^1110101011
(3.2.4) nichts zu tun...
(3.4) okai... i=-1 => Schleife bricht ab

(4) Wie wir sehen kommt das gewünschte Ergebnis bei raus...


Dieser Algorithmus lässt sich natürlich auch auf andere 2er Potenzen ausweiten. Wenn man k=2 setzt, erhält man eine leicht abgewandelte Variante des Square-And-Multiply Algorithmus' (diesmal eine ohne den "mitlaufenden" Faktor).
Um auf eine allgemeine Potenz 2^k zu verallgemeinern, muss man im Algorithmus natürlich 16 durch 2^k ersetzen. Außerdem muss man in Schritt \ref(1) nicht nur die ungeraden Zahlen bis 15 sondern bis incl. 2^k-1 berechnen und speichern.
Man untersucht natürlich auch keine 4-Bit-, sondern k-Bit-Blocks, und muss in Schritt \ref(3.2.2) bzw. \ref(8.2.2) (k-t)mal Quadrieren.
Auch die Laufzeit verändert sich mit der Wahl von k: Es werden (1+O(1/k))L, also maximal (k+1)/k\.L $ Multiplikationen in der Hauptschleife benötigt. Allerdings sollte man bedenken, dass mit wachsendem k auch der Schritt \ref(1) aufwändiger wird. Die Anzahl der Multiplikationen hängt in diesem Schritt linear von k ab. Diesen Schritt können wir auch durch die andern Potenzierungsalgorithmen nicht wesentlich verbessern, da wir viele dicht beianderliegende Potenz zu berechnen haben (2^(k-1) Potenzen um genau zu sein).
Man erkennt deshalb, dass hier ein Kompromiss gefunden werden muss zw. der Laufzeit von Schritt \ref(1) und der Hauptschleife. Außerdem muss man für höhere k auch höheren Speicherverbrauch einplanen, da alle 2^(k-1) Potenzen in p(i) ja im Speicher abgelegt werden müssen.
Weiterhin sollte bedacht werden, dass eine Erhöhung des k-Wertes irgendwann keine signifikanten Geschwindigkeitsvorteile mehr bringt.
In der Praxis werden k-Werte von 3-16 verwendet.


Gültigkeit des Algorithmus' in anderen Strukturen



Wie schon erwähnt sind die hier vorgestellten Algorithmen in allen Halbgruppen gültig. Weiter verallgemeinern lassen sich meines Wissens nicht, da für die Gültigkeit der Potenzgesetze, die wir hier verwendet haben, das Assoziativ-Gesetz zwingend erforderlich ist. Man kann die Anwendung allerdings für Spezialfälle noch ausdehnen. Wie ich schon vorgeführt habe, kann man in Monoiden (d.h. in Halbgruppen mit neutralem Element) den Fall n=0 mit einschließen, indem man a0=1 definiert. In echten Gruppen, in denen also jedes Element auch ein Inverses hat, kann man außerdem negative Exponenten definieren, indem man a-n=(an)-1=(a-1)n definiert.
Mit diesem Wissen kann man in wenigen Schritten den Algorithmus auch auf Monoide und Gruppen ausdehnen: Im Prinzip muss man nur die b-Varianten der Algorithmen benutzen, bzw. einen Schritt am Anfang hinzufügen, damit das Inverse potenziert wird, falls der Exponent negativ ist.

Eine Anwendung des Algorithmus'



Die Fähigkeit schnell zu potenzieren ist äußerst vorteilhaft, vor allem, weil für die Umkehrung, das Diskrete Logarithmieren keine allgemeingültigen, schnellen Algorithmen bekannt sind. Diese Algorithmen sind weiterhin exponentiell.
Das ist das so genannte Diffie-Hellmann-Problem. Diese beiden Herren erkannten als erste die Bedeutungen dieser Asymmetrie und entwickelten ein Verfahren, das diese kryptographisch ausnutzt und nach ihnen benannt wurde.

Dabei geht es darum, wie zwei Gesprächspartner eine sichere, d.h. verschlüsselte Unterhaltung über eine öffentliche Verbindung führen können. Dazu muss ja über diese Leitung ein entsprechender Geheimschlüssel übertragen werden, sodas ihn nur die Teilnehmer der Unterhaltung ihn mitbekommen.
Den Schlüssel direkt zu senden ist offensichtlich so sicher wie eine Postkarte in sauberer Handschrift.
Das Diffie-Hellmann-Verfahren erlaubt über einen Umweg trotzdem, dass ein deutlich sicherer Austausch des Schlüssels stattfindet.

Dazu wählen die Partner A und B je eine natürliche Zahl, a und b aus \IN, sowie eine gemeinsame Basis h aus \IM (incl. der verwendeten Halbgruppe selbstverständlich), die sie veröffentlichen.
Dann berechnet jeder der beiden die Potenz von h und der gewählten Zahl aus:
A rechnet \alpha=h^a
B rechnet \beta=h^b.

Dann schicken sich beide ihr Ergebnis zu und potenzieren das Ergebnis des jeweils Anderen mit dem eigenen Exponenten.
A rechnet \beta^a=(h^b)^a=h^ab
B rechnet \alpha^b=(h^a)^b=h^ba

Wie man sieht, erhalten beide den selben Wert h^ab. Dies ist nun der gemeinsame Schlüssel.
Ein eventueller Lauscher hat nur die Zahlen h, \alpha und \beta mitbekommen. Daraus kann er, bei ausreichend großer Wahl von a und b, nicht in nutzbarer Zeit ermitteln, wie der Schlüssel lautet.

Dieses Verfahren ist ähnlich wie die RSA-Verschlüsselung, die ich in meinem letzten Artikel vorgestellt habe, darauf angewiesen, dass es zwei Verfahren gibt, von denen sich eines schnell und das andere nur langsam berechnen lässt.
Bei RSA sind das Multiplikation von Primzahlen und Primfaktorzerlegung, bei Diffie-Hellmann sind das Potenzieren und diskretes Logarithmieren.
Da die Rechenleistungen immer schneller werden, ist es wie auch bei RSA erforderlich, in regelmäßigen Abständen, die Schlüssel zu wechseln und längere zu benutzen.

Ich hoffe ich habe euch einen guten Überblick über allgemeingültige Potenzierungslagorithmen gegeben.

mfg^Gockel
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Interessierte Studenten :: Informatik :: Algorithmen :
Potenzen fürs Volk [von Gockel]  
Effiziente Algorithmen für die Berechnung von Potenzen a^n
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 8636
 
Aufrufstatistik des Artikels
Insgesamt 156 externe Seitenaufrufe zwischen 2012.01 und 2021.05 [Anzeigen]
DomainAnzahlProz
http://google.de13083.3%83.3 %
http://google.lu74.5%4.5 %
http://www.coding-board.de53.2%3.2 %
https://google.com31.9%1.9 %
https://duckduckgo.com10.6%0.6 %
http://www.fireball.de10.6%0.6 %
http://r.duckduckgo.com10.6%0.6 %
http://www.bing.com21.3%1.3 %
http://www1.delta-search.com10.6%0.6 %
https://www.bing.com10.6%0.6 %
https://www.ecosia.org10.6%0.6 %
http://google.fr10.6%0.6 %
http://google.com10.6%0.6 %
http://google.at10.6%0.6 %

Häufige Aufrufer in früheren Monaten
Insgesamt 131 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2015 (67x)http://google.de/url?sa=t&rct=j&q=
201210-10 (10x)http://google.de/url?sa=t&rct=j&q=schnelles potenzieren algorithmus
201202-02 (7x)http://google.lu/url?sa=t&rct=j&q=algorithmus potenz
201212-12 (7x)http://google.de/url?sa=t&rct=j&q=schnelles potenzieren iterativ
201204-04 (7x)http://google.de/url?sa=t&source=web&cd=1&ved=0CCQQFjAA
201206-06 (6x)http://google.de/url?sa=t&rct=j&q=wir betrachten eine assoziative operation (...
201201-01 (5x)http://google.de/url?sa=t&rct=j&q=algorithmus potenz
201205-05 (5x)http://google.de/url?sa=t&rct=j&q=potenzen schneller ausrechnen
201203-05 (5x)http://www.coding-board.de/board/showthread.php
201304-04 (4x)http://google.de/url?sa=t&rct=j&q=iteratives potenzieren
201301-01 (4x)http://google.de/url?sa=t&rct=j&q=zeigen das potenzieren keine assoziative op...
201207-07 (4x)http://google.de/url?sa=t&rct=j&q=schnelles potenzieren mathe

[Top of page]

"Informatik: Potenzen fürs Volk" | 4 Comments
The authors of the comments are responsible for the content.

Re: Potenzen fürs Volk
von: FriedrichLaher am: Mo. 05. Juli 2004 17:41:50
\(\begingroup\)Ich nehme an, Du kennst die Methode, durch wiederholtes Quadrieren den Logarithmusdualis zu bestimmen: 1mal Quadrieren je Bit des ld . Ist das
wirklich "exponentiell"? \(\endgroup\)
 

Re: Potenzen fürs Volk
von: Gockel am: Mo. 05. Juli 2004 18:09:20
\(\begingroup\)Hi Friedrich.

Ich weiß im Moment gar nicht welchen Algoroithmus du meinst. Was quadriert man denn, wenn man log(2,n) bzw. floor(log(2,n))bestimmen will?
Ich kenne nur diesen Algorithmus:

\sourceon
Eingabe: x
Ausgabe: floor(lb(x))

(1) Wenn x=0, gib einen Fehler aus, weil lb(0) nicht definiert ist.
(2) Setze r=0
(3) Solange x>0, setze x=floor(x/2) und r=r+1
(4) gib r-1 aus.
\sourceoff

Wobei der erste Schritt weggelassen werden kann... dann wird die Bitlänge der Zahl 0 implizit auf 0 Bits festgelegt.

mfg Gockel.\(\endgroup\)
 

Re: Potenzen fürs Volk
von: FriedrichLaher am: Mo. 05. Juli 2004 18:43:42
\(\begingroup\)der Einfachheit halber sei 1 < x < 2,

(1) P=x, p=0, ld = 0
(2) P=P², p = p+1
(3) if(P > 2) {P = P/2, ld = ld + 1/2^p}
(4) wiederhole ab 3 bis zur gewünschten Genauigkeit
ld ist der Log.dualis(x)

[Knuth, Fundamental Algorithms, 2nd Ed., 1.2.2
]\(\endgroup\)
 

Re: Potenzen fürs Volk
von: Gockel am: Mo. 05. Juli 2004 19:43:27
\(\begingroup\)Hi Friedrich.

Ich glaube, ich weiß jetzt worauf du hinaus willst:
"Die Fähigkeit schnell zu potenzieren ist äußerst vorteilhaft, vor allem, weil für die Umkehrung, das Diskrete Logarithmieren keine allgemeingültigen, schnellen Algorithmen bekannt sind. Diese Algorithmen sind weiterhin exponentiell."

Dich hat gestört, dass da exponentiell steht, oder!?

Nun zum einen ist es ein bisschen ungenau (ich entschuldige mich dafür). Man muss natürlich sagen, dass die Algorithmen die aus a und ab den Exponenten b bestimmen wollen, exponentiell in der Bitlänge von b sind.
Sie sind also nicht wesentlich schneller als fortgesetztes Dividieren durch a bis 1 erreicht ist, denn das würde genau b Divisionen erfordern.
Zum Andern gehst du ja davon aus, dass der Logarithmus, den du angibst, das Problem schneller löst. Das muss ich aber ein wenig differenzieren. Es ist sicherlich eine Methode, die das Logarithmieren ermöglicht und außerdem recht effizient ist.
Was du hier vorgestellt hast, ist leider keine allgemeingültige Methode, denn darum geht es ja... in den Reellen Zahlen ist logarithmieren ziemlich einfach, aber wenn du dich z.B. in Z/nZ befindest, kannst du deine Methode nicht mehr anwenden.
Und beim Diffie-Hellmann-Verfahren werden i.d.R. auch nicht die reellen Zahlen benutzt, weil man es den Angreifern ja so schwer wie möglich machen will...

mfg Gockel.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]