Pseudo Randomizer

[JayTaph]

Stel, ik heb een challenge/response mechanisme geschreven, en daarvoor gebruik ik een pseudo-randomizer (die aan beide zijde dus dezelfde reeks random getallen uitspuugt bij dezelfde random seed).

Nou wil ik weten in wanneer deze reeks getallen zich weer gaan herhalen. Is zoiets wiskundig te berekenen vanuit de source (ik heb geen knuth-boeken bij de hand, dus ik weet niet of daar iets in staat) of zou dat gewoon brute-force geprobeerd moeten worden?

[gjkamstra]

Is afhankelijk van welke randomizer. Brute force werkt in ieder geval.

[Macros]

Ze gaan zichzelf volgens mij alleen in theorie herhalen. Ik denk niet dat iemand 1 van die geavanceerde pseudo randomizers ooit heeft zien 'loopen'
Zal wel heel ver in de toekomst liggen.

[Mithrandir]

Op woensdag 13 februari 2002 19:27 schreef Macros het volgende:
Ze gaan zichzelf volgens mij alleen in theorie herhalen. Ik denk niet dat iemand 1 van die geavanceerde pseudo randomizers ooit heeft zien 'loopen'
Zal wel heel ver in de toekomst liggen.

Ik denk dat je ze iig wél op tijd moet gaan seeden; dan krijg je zulke problemen niet zo snel...

[JayTaph]

>Ik denk dat je ze iig wél op tijd moet gaan seeden; dan krijg
>je zulke problemen niet zo snel...

Het is juist de bedoeling dat je dat NIET gaat doen. Elk random getal wordt naar de server gestuurd als "id". De server (die dezelfde random-routine heeft), kan daarmee dus bepalen of dat pakket gestuurd vanaf de client waar hij de challenge/response mee heeft afgesproken.

Natuurlijk kan je om de zoveel pakketten een nieuwe seed sturen, en die gebruiken voor de volgende reeks (bv 100) packets, maar daar gaat het me niet zo om.


Mijn vraag is meer: kan ik aantonen dat die randomizer expliciet zich pas na N keer gaat herhalen. En dat N 100, 100duizend of 100miljard is.

[RickN]

Op donderdag 14 februari 2002 09:25 schreef JayTaph het volgende:
[..]
Mijn vraag is meer: kan ik aantonen dat die randomizer expliciet zich pas na N keer gaat herhalen. En dat N 100, 100duizend of 100miljard is.

Ja, ik denk dat dat in het algemeen wel kan. Zelf ben in nu met Linear Feedback Shift Registers bezig, deze worden gebruikt om speudorandom sequences te genereren (meestal binair, maar dat hoeft niet) en daarvan kun je heel mooi zeggen wat de cycle lengte van de sequence is. Maar het hangt een beetje van je algoritme af denk ik hoe eenvoudig het is om die lengte te bepalen.

[JayTaph]

Ok, soms denk je veel te moeilijk en dan kan google je ook niet helpen.. Met verstand op nul hebik al flink wat meer gevonden

Ik maak gebruik van de Mersenne Twister, en deze routine heeft een cycle length van 2^19937 - 1..

[RickN]

Op donderdag 14 februari 2002 10:38 schreef JayTaph het volgende:
Ok, soms denk je veel te moeilijk en dan kan google je ook niet helpen.. Met verstand op nul hebik al flink wat meer gevonden

Ik maak gebruik van de Mersenne Twister, en deze routine heeft een cycle length van 2^19937 - 1..

Niet slecht Is ook niet toevallig denk ik, de LFSR's waar ik mee werk produceren ook sequences met een lengte van 2^n-1, zogenaamde m-sequences.

edit:

Lol, even een papertje over mersenne twister doorgebladerd en het blijkt ook gewoon een LFSR te zijn. Wel een hele lange, namelijk 19937 bits. Dit ding produceert dus een m-sequence zoals ik al zei, omdat het generator polynoom van dat ding primitief is. Waarschijnlijk hebben ze een heel slim polynoom gekozen waardoor ie toch efficient te genereren is.

JayTaph, de mersenne twister is een binaire LFSR, en als ze het dus hebben over een periode van 2^bla - 1, dan bedoelen ze de periode van de binaire sequence die eruit komt. Als jij er vervolgens integers mee gaat genereren, dan moet je de periode nog wel even door 32 (ofzo) delen, waardoor de periode nog maar( ) 2^19932 (ofzo) is.

[JayTaph]

2^19332 dus maar... damn.. da's NET te weinig

Verder snap ik geen hol van wiskunde, dus heb ik ook geen flauw idee wat voor formules erachter zitten of hoe dat allemaal werkt hoor..