Algorithmus von Zufallszahlgeneratoren?

Hi,
ich studiere an der FH Elektrotechnik und muss in einer Vorlesung einen Vortrag über Pseudozufallszahlen halten. Dabei möchte ich evtl auch die Funktionsweise von Pseudozufallszahlgeneratoren, die von bestimmten Compilern mitgelifert werden (also zum Beispiel rand() unter C++), anschneiden. Ich hab bisher nur rausfinden können dass diese Funktion auf einem modularen Kongruenzgenerator basiert (also (a * x + c)mod n), allerdings meinte mein Prof, dass die Generatoren wahrscheinlich doch etwas komplexer seien.
Kann mir jemand etwas zu dem Thema sagen, oder besser Links oder andere Quellen verraten, wo ich so etwas rausfinden könnte?
Gruss,
teelow

http://burtleburtle.net/bob/rand/isaacafa.html

Jetzt wollt ich schon schreiben, dass es da nix gibt, aber dann hast du im Text ja doch noch Pseudozufallszahlgeneratoren geschrieben.

Talla

Ein recht bekannter Pseudozufallszahlenalgorithmus ist der Mersenne Twister.

Taurin

Lineare Kongruenzgeneratoren sind tatsächlich etwas komplizierter: x_neu = ax + b mod n hat drei Parameter a,b und n. Und wie die gewählt werden müssen, damit ein "guter" (was heißt hier überhaupt "gut" ) Generator rauskommt ist ein kompliziertes Stück Mathematik.

Super, das hilft mir schon mal weiter, danke@all!
Und kann mir vllt noch jemand sagen, auf welchen Algorithmus die normale, standardmässige rand()-Funktion in C++ basiert?
Gruss
teelow

ist afaik nicht im Standard definiert. Will heißen von Compiler zu Compiler anders. Sonst schau dir mal ne opensource libc an, wie glibc oder uclibc oder so.

okay, das hilft mir auch weiter. Nochmal thx@all!

nevermore

http://www.zdnet.de/security/news/0,39029460,39159132,00.htm

Vielleicht hilft dir das ja auch noch oder du kannst es in deinen Vortrag einbauen.

Hier ein Link zu einem aktuellen Thema. Stellt ganz gut dar, wie wichtig ein guter Zufallsalgorithmus für sicherheitsrelevante Zwecke ist. Finde ich erschreckend, wusste ich bis dahin auch noch nicht....

borg

die stdlib implementierung von GNU findest du hier: ftp://ftp.gnu.org/gnu/glibc/glibc-2.7.tar.gz

/* If we are using the trivial TYPE_0 R.N.G., just do the old linear
   congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
   same in all the other cases due to all the global variables that have been
   set up.  The basic operation is to add the number at the rear pointer into
   the one at the front pointer.  Then both pointers are advanced to the next
   location cyclically in the table.  The value returned is the sum generated,
   reduced to 31 bits by throwing away the "least random" low bit.
   Note: The code takes advantage of the fact that both the front and
   rear pointers can't wrap on the same call by not testing the rear
   pointer if the front one has wrapped.  Returns a 31-bit random number.  */

int
__random_r (buf, result)
     struct random_data *buf;
     int32_t *result;
{
  int32_t *state;

  if (buf == NULL || result == NULL)
    goto fail;

  state = buf->state;

  if (buf->rand_type == TYPE_0)
    {
      int32_t val = state[0];
      val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
      state[0] = val;
      *result = val;
    }
  else
    {
      int32_t *fptr = buf->fptr;
      int32_t *rptr = buf->rptr;
      int32_t *end_ptr = buf->end_ptr;
      int32_t val;

      val = *fptr += *rptr;
      /* Chucking least random bit.  */
      *result = (val >> 1) & 0x7fffffff;
      ++fptr;
      if (fptr >= end_ptr)
	{
	  fptr = state;
	  ++rptr;
	}
      else
	{
	  ++rptr;
	  if (rptr >= end_ptr)
	    rptr = state;
	}
      buf->fptr = fptr;
      buf->rptr = rptr;
    }
  return 0;

 fail:
  __set_errno (EINVAL);
  return -1;
}