Wir definieren Security-Begriffe - Diskussion des Algorithmus

8 Beiträge18.09.2006Archiviert
squeez18.09.2006 · Beitrag #9733
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag

Als Folge der Diskussion in [1] habe ich mir Gedanken ueber einen effizienteren Algorithmus gemacht.
Da es in dem verlinkten Thread zu sehr Offtopic waere, habe ich hier einen neuen Thread gestartet, wo nur ueber das Problem der Effizienz des eingesetzten Algorithmus diskutiert werden sollte, um Marc von Diskussionen ueber zu hohe CPU Belastung mit seinem Betreiber zu ersparen ;} .

Eigentlich ist das Problem ja recht trivial, und es stellt sich die Frage, weshalb squeez hierfuer einen eigenen Thread startet. Nun, die Bewertung eines Algorithmus ist ein eigenstaendiges Gebiet der Informatik. Und, diese Aufgabe ist ein perfektes Beispiel fuer diese Disziplin.

Hier die Originalimplementierung:

1. Ich bastle mir vier eindimensionale Arrays $aarray, $barray, $carray und $carray.

2. Diese werden mit Begriffen abgefuellt. $aarray = array("", "Passive", ...);

3. Zu jedem Array wird eine Zufallszahl durch $arnd = rand(0, count($aarray)-1); berechnet, die eine Referenzierung des entsprechenden Worts mit $aword = $aarray[$arnd]; zulassen soll.

4. Die Chancen werden berechnet $chances = (count($aarray)-1) * (count($barray)-1) * (count($carray)-1) * (count($darray)-1);

5. Und die Wortkette in der Form "$aword $bword $cword $dword" ausgegeben.



Ich habe hier ein paar Ideen im Hinterkopf, wie die CPU Belastung massiv reduziert werden kann.

Hier mein Vorschlag:
Das Problem betrifft die Berechnung der Zufallswerte, welche je nach Implementierung recht aufwaendig ausfallen kann.

Da der Inhalt eines jeden Arrays einmalig ist, und keiner der Werte mehrfach vorkommt, ist das Array bereits zufaellig sortiert. Es ist deshalb unsinnig, jedes mal noch einen zufaelligen (und damit rechenaufwaendigen) Index zu berechnen. Stattdessen kann einfach jedem Array ein inkremenierender Index zugeordnet werden, welcher jeweils inkrementierend bei jedem Zugriff hochgezaehlt wird. Der Umbruch erfolgt durch modulo Berechnung, so dass kein Ueberlauf entstehen kann.

Wichtig ist, dass die Auftrittswahrscheinlichkeiten nicht veraendert werden. Dies kann dadurch erzielt werden, in dem die Groesse eines jeden Arrays seiner naechsten Primzahl entspricht.

Nun beschraenkt sich die notwendige CPU Belastung auf das inkrementieren eines integers und der modulo "Umbrechung". Man drueckt dies in Form von O(1) aus. Die Berechnung einer Zufallszahl wuerde einem Polynom entsprechen, von welchem der Grad unbekannt ist. Also die Form O(x^m) annehmen kann, wobei m von der Implementierung abhaengt (und im besten Fall 0 entspricht, wohl aber >=1 sein wird).


So, ich bitte um eine Diskussion, wie man selbst dieses Verfahren noch beschleunigen koennte.

Marco

[1] http://www.computec.ch/forum_viewtopic.php?14.9715.10
[ Bearbeitet ]
sergey19.09.2006 · Beitrag #9735
Avatar
Mitglied seit: 22.03.2006
Forenbeiträge: 526
Besuche: 2692
Ich schreib das mal hier hinein:
@ Marc: danke das wollte ich eigentlich wissen.
@ squeez: Wieso alles so 'kompliziert'? Ich finde Marc's Lösung einfach und simpel, aber wenn du dir gedanken darüber machst, find ich auch gut.
Die Idee ist verdammt gut, auch wenn ich ab etwa der hälfte nicht mehr nachkomme ;)

Gruss

sergey
squeez19.09.2006 · Beitrag #9738
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag


Wieso alles so 'kompliziert'?

Ist nicht kompliziert. Ist effizient.


Die Idee ist verdammt gut, auch wenn ich ab etwa der hälfte nicht mehr nachkomme ;)

Wo steckst du fest? An welchem Punkt kommst du nicht mehr weiter?

Marco
flow19.09.2006 · Beitrag #9739
Avatar
Mitglied seit: 31.01.2005
Forenbeiträge: 154
Besuche: 3400
Ave

Auch sollte die Länge eines jeden Arrays unterschiedlich zur Länge jedes anderen Arrays sein, um die Vermischung der Wörter zu gewährleisten, denn wenn alle Arrays gleich lang sind, wiederholen sich die Kombination nach Anzahl Elemente im Array wieder.

Gruss Björn

P.S.: Falls bei jemandem die Generierung von Zufallszahlen auf der CPU zu stark ins Gewicht fällt, sollte man sich überlegen eine Quanten-Zufallszahl-PCI-Steckkarte[1] zu besorgen.

[1] http://www.idquantique.com/products/quantis.htm
squeez19.09.2006 · Beitrag #9740
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
hallo flow


Auch sollte die Länge eines jeden Arrays unterschiedlich zur Länge jedes anderen Arrays sein, um die Vermischung der Wörter zu gewährleisten, denn wenn alle Arrays gleich lang sind, wiederholen sich die Kombination nach Anzahl Elemente im Array wieder.


Zusammen mit der Aufrundung zur naechsten Primzahl der Groesse eines jeden Arrays wird eine maximale Annaeherung an den gegebenen Algorithmus ermoeglicht.


P.S.: Falls bei jemandem die Generierung von Zufallszahlen auf der CPU zu stark ins Gewicht fällt, sollte man sich überlegen eine Quanten-Zufallszahl-PCI-Steckkarte[1] zu besorgen.

Geile Idee ;}

Marco
sergey19.09.2006 · Beitrag #9741
Avatar
Mitglied seit: 22.03.2006
Forenbeiträge: 526
Besuche: 2692
Also die Modulo berechnung kapier ich noch, auch die Primzahlen, aber was dann folgt: TUUUUTTTT ;)

Hab's noch nicht ganz kapiert.

Gruss

sergey
squeez19.09.2006 · Beitrag #9746
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Also die Modulo berechnung kapier ich noch, auch die Primzahlen, aber was dann folgt: TUUUUTTTT ;)

Hab's noch nicht ganz kapiert.

Gruss

sergey


Ich glaube du meinst die Passagen mit der Begruendung der Effizienz.

Lies dir dazu mal folgenden Text durch.
http://www.linux-related.de/index.html?/coding/o-notation.htm

Wenn du Fragen dazu hast, einfach stellen...

hth

Marco
sergey20.09.2006 · Beitrag #9765
Avatar
Mitglied seit: 22.03.2006
Forenbeiträge: 526
Besuche: 2692
@ squeez:
Danke werd ich bei gelegenheit machen, hab momentan aber leider keine Zeit.

Gruss

sergey