Pseudo-random Number Generators, ou simplesmente PRNGs, são algoritmos para geração de números com propriedades semelhantes à dos números aleatórios (random numbers). Os PRNGs produzem sequências de números aparentemente independentes, normalmente seguindo uma distribuição uniforme, com base numa expressão matemática. São normalmente definidos pelos seguintes aspetos: o seu output é determinístico, periódico e depende de um valor de inicialização, conhecido como seed. Este tipo de algoritmos (os PRNGs) são normalmente mais rápidos que a geração de números realmente aleatórios no /dev/random ou /dev/urandom (por exemplo, disponíveis numa distribuição Linux), uma vez que o SO usa o input de dados de interfaces de hardware, e.g., o rato, tráfego de rede da NIC (Network Interface Controller), etc.

Um outro exemplo de um true random number generator é o random.org, onde são usados dados de ruído atmosférico como input de aleatoriedade.

PRNGs

PRNGs representam peças cruciais dentro do contexto da simulação computacional, pois permitem criar situações aleatórias pelas quais um evento do mundo real é afetado. Assim, uma falha em termos da qualidade de randomness pode resultar numa reprodução deficiente do modelo de simulação, levando possivelmente a conclusões falsas ou deficientes.

Processamento é sinónimo de tempo, e os PRNGs produzem resultados num espaço temporal consideravelmente menor em relação a outro tipo de geradores de números e sequências aleatórias. Um exemplo desse facto é a geração de tráfego de rede, onde a distribuição dos resultados deve ser controlada e seguindo uma distribuição exponencial, e não deve ser morosa (i.e., o tempo de processamento não pode ser muito elevado).

PRNGs são também usados em máquinas de jogos online, jogos de vídeo e aplicações de segurança informática. No campo de segurança da informação, os PRNGs são muitas vezes a fonte de chaves de criptografia, nonces, hashs ou cifras. Nem todos os PRNGs podem ser usados em todas essas aplicações, uma vez que nem todos cumprem com exatidão algumas das regras que lhes permite serem a fonte para determinadas implementações criptográficas. Para criptografia são usados um tipo específico de PRNGs conhecidos por CSPRNGs (geradores de número pseudo-aleatório criptograficamente seguros), com propriedades que os tornam adequados para esse contexto.

Hoje em dia, existem muitos algoritmos para geração de números pseudo-aleatórios com distribuição uniforme, como por exemplo, LCG, ISAAC, Mersenne Twister, etc., todos definidos por características próprias:

• Período (comprimento do output);
• Independência (todos os números da sequência devem ser independentes uns dos outros);
• Distribuição uniforme (a probabilidade de sair o número 2 é igual à probabilidade de sair o número 7);
• Rapidez (na geração);
• Reprodutibilidade (capacidade de reproduzir a sequência novamente com determinados parâmetros iniciais).

De notar que as propriedades acima citadas são dificilmente conciliáveis, pelo que a seleção de um gerador conveniente para uma dada situação pode ser uma tarefa não muito trivial.

PRNGs são então funções matemáticas que debitam uma sequência finita de números, isto é, a dada altura a sequência de números começa a repetir-se. Ao tamanho dessa sequência é chamado período.

Linear Congruential Generator (LCG)

O LCG é o PRNG mais popular dentro deste contexto e usado largamente para geração de números pseudo-aleatórios com uma distribuição uniforme. Ele é de fácil implementação, tem alta performance computacional e simples de entender. É bastante usado a nível científico. O LCG é um PRNG que gera sequências de inteiros pseudo-aleatórias com base na expressão matemática

X_n = a X_n-1 + b mod M

em que a, b e M são números inteiros com determinadas características. Como se pode concluir da definição, cada número da sequência X_n é produzido a partir do seu antecessor X_n-r. Alguns destes geradores usam um número primo como M e b igual a 0. O número máximo que o período que estes geradores podem atingir é M e, para que isso aconteça, a e b devem preencher requisitos adicionais. Por exemplo, de uma maneira geral, a-1 deve ser divisível por todos os primos que factorizam M, e b deve ser co-primo com M. Se M for uma potência de 2 (muito comum em implementações práticas, já que operações módulo 2³² ou 2⁶⁴ são simples de implementar em máquinas de 32 ou 64 bits), então a-1 deve ser divisível por 4.

A escolha dos valores que parametrizam o gerador é crítica para manter uma qualidade mínima dos números gerados. Por exemplo, pode verificar-se a partir da seguinte inicialização que o gerador acima descrito (LCG) degenera num gerador fraco.

a=4   b=2   M=8

Considere começar com X₁ = 1. A sequência gerada é a seguinte:

= 4 × 1 + 2 mod 8 = 6;
= 4 × 6 + 2 mod 8 = 2;
= 4 × 2 + 2 mod 8 = 2;
…
= 2;

A sequência é dada por: (1, 6, 2, 2, 2, …). Começou a repetir o valor 2 logo a partir do terceiro valor. Para os parâmetros iniciais definidos anteriormente (incluindo o X₁), o período desta sequência é 3.

Na verdade, é difícil garantir excelente comportamento para sequências produzidas com um LCG, mas é pelo menos possível garantir que o período máximo (i.e., M) é atingido. Para garantir que o LCG tem um período M, podem ser definidas algumas regras à cabeça, nomeadamente: b e M têm de ser co-primos, e a-1 tem de ser divisível por todos os factores primos de M.

Ter um período completo significa que a sequência começa a repetir-se apenas após M, e antes que isso aconteça, a sequência é constituída por todos os valores possíveis módulo M. Para que isso aconteça é importante determinar a melhor parametrização.

Se forem considerados agora os seguintes parâmetros de inicialização:

a=4   b=3   M=16

as regras impostas acima são satisfeitas, i.e.: M é potência de 2 (16 = 2⁴), a-1=4 e divisível por 4, e 3 e 16 são números co-primos.

Neste caso, aplicando as regras definidas, consegue-se que o máximo período para os parâmetros de inicialização com módulo M=16 seja atingido. A sequência produzida, começando por X₁ = 10, seria:

(10, 5, 12, 15, 14, 9, 0, 3, 2, 13, 4, 7, 6, 1, 8, 11, 10, …)

Mas se um PRNG não é infinito, qual é o período máximo do LCG? Isto é, quantos números diferentes são possíveis gerar para uma sequência com este algoritmo?

É comum encontrarem-se geradores com o tamanho do período igual a ou múltiplo do tamanho máximo de um registo inteiro no CPU, (e.g., 2³², que numericamente é representado pelo valor 4294967296 – 32 bits de 1s). A título de exemplo, é possível obter um LCG com um período de 2³² com a seguinte parametrização:

rseed = (rseed * 1103515245 + 12345) & RANDMAX

O java.util.Random é um LCG que gera números aleatórios de 2⁴⁸ bits através do UNIX rand48, usando apenas os primeiros 32 bits como output útil.

#include "unif01.h"
#include "bbattery.h"

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include "ulcg.h"

#define norm 2.328306549295728e-10
unsigned int rseed = 5;

double lcg(){
   return (rseed=(rseed * 1103515245 + 12345) & RAND_MAX)*norm;
}

int main (void) {
  unif01_Gen *gen;
  gen = unif01_CreateExternGen01 ("MyLCG", lcg); /* My LCG */

  bbattery_SmallCrush (gen);
  unif01_DeleteExternGen01 (gen);

  return 0;
}

Teste Estatístico ao LCG

Existem baterias de teste preparadas para testar exaustivamente PRNGs, nomeadamente a TestU01. O código acima entregue já possui a implementação do LCG usado no java nesta biblioteca de teste de PRNGs. O resultado da qualidade do LCG é a seguinte para a bateria de testes mais modesta, conhecida por SmallCrush:

========= Summary results of SmallCrush =========
Version               TestU01  1.2.3
Generator:            MyLCG
Number of statistics: 15
Total CPU time:       00:00:03.56
The following tests gave p-values outside [0.001, 0.9990]:
(eps  means a value < 1.0e – 300):
(eps1 means a value < 1.0e – 15):
         Test     p-value
—————————————–
 1  BirthdaySpacings               eps
 2  Collision                  5.8e-14
 3  Gap                            eps
 4  SimpPoker                      eps
 6  MaxOft                         eps
 6  MaxOft AD                 1 – eps1
 9  HammingIndep               1.1e-11
10  RandomWalk1 H                  eps
10  RandomWalk1 M                  eps
10  RandomWalk1 J                  eps
10  RandomWalk1 R                  eps
10  RandomWalk1 C                  eps
—————————————–
All other tests were passed

De 15 testes efetuados, 12 falharam. Atingem-se resultados semelhantes para para outras baterias de testes, o que confirma a pouca qualidade para a geração de números aleatórios através deste PRNG.

Sim, o java.util.Random usa o LCG para a geração de números pseudo aleatórios, daí a previsibilidade nos valores gerados. Este gerador nunca pode ser usado em aplicações criptográficas, seja de que forma for. No entanto, é uma função rápida, excelente para pequenas experiências e geração de valores em aplicações de lazer (e.g., jogos).