Quels algorithmes sont utilisés pour des C rand()?

Voir cet article: http://en.wikipedia.org/wiki/List_of_random_number_generators

C'est le code source de la glibc rand():

/* Reentrant random function from POSIX.1c.
   Copyright (C) 1996, 1999, 2009 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Contributed by Ulrich Drepper <[email protected]>, 1996.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

#include <stdlib.h>


/* This algorithm is mentioned in the ISO C standard, here extended
   for 32 bits.  */
int
rand_r (unsigned int *seed)
{
  unsigned int next = *seed;
  int result;

  next *= 1103515245;
  next += 12345;
  result = (unsigned int) (next / 65536) % 2048;

  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;

  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;

  *seed = next;

  return result;
}

Source: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/rand_r.c;hb=la TÊTE

Comme vous pouvez le voir, il suffit de multiplier avec une addition et d'une maj. Les valeurs sont choisies avec soin pour vous assurer que vous n'obtenez pas de répétition de la sortie de RAND_MAX itérations.

Noter que c'est un vieux de la mise en œuvre qui a été remplacé par un algorithme plus complexe: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/random_r.c;hb=la TÊTE

Si le lien en cas de bris, de Google pour "glibc rand_r"

Le domaine de la PRNGs (Générateurs de nombres Pseudo Aléatoires) est très vaste.

Tout d'abord, vous devez comprendre que sans avoir une entrée externe (généralement physiques), vous ne pouvez pas obtenir une véritable source de nombres aléatoires.. C'est pourquoi ces algorithmes sont appelés pseudo-aléatoire: généralement, ils utilisent une graine d'initialiser une position dans une séquence très longue qui semble aléatoire, mais ce n'est pas aléatoire du tout.

L'un des plus simple des algorithmes est le Générateur Linéaire à Congruence (LCG), qui a une certaine costraints pour garantir une longue séquence et il n'est pas sûr du tout.

Autre drôle de l'une (au moins pour le nom) est l'Blum Blum Shub Générateur ( BBS ), ce qui est inhabituel pour la normale PRNGs parce qu'il s'appuie sur l'exponentiation dans l'arithmétique modulo donner une sécurité comparable à d'autres algorithmes tels que RSA et El Gamal la rupture de la séquence (même si je ne suis pas sûr au sujet de la preuve)