Como posso determinar os valores iniciais do gerador de números pseudo-aleatórios se a sequência é fornecida?

Suponha que eu soubesse que uma sequência numérica aleatória foi gerada por um gerador congruencial linear. Isso é,

$x_{n+1}=(aX_n+c) \bmod m$

Se eu sou dado o período inteiro (ou, pelo menos, uma grande subsequência contígua do mesmo), como pode reconstruir os parâmetros e que produziu esta sequência? Estou procurando um método geral que seja capaz de determinar os parâmetros iniciais se o gerador de números pseudo-aleatórios for conhecido. $a,c,m$ $x_0$

random-number-generation inverse-problem Paulo
fonte

O que exatamente é conhecido? Em uma subseqüência contígua, você não pode dizer onde a sequência começou , a menos que os itens sejam indexados em sequência. Se é conhecido, então e são facilmente descobertos.

x_{0}

$x_0$

m

$m$

a

$a$

c

$c$

hardmath

Respostas:

Veja o artigo Como quebrar um gerador linear de congratulações , Haldir ("Reverse Engineering Team", dezembro de 2004):

Neste artigo, apresentarei um método que resolverá todos os valores do LCG, incluindo o módulo com seis ou mais números consecutivos de saída PRNG.

O artigo inclui o código fonte da "prova de conceito", escrito em C, usando o NTL de Victor Shoup para aritmética de precisão estendida.

hardmath
fonte

Esse foi um ótimo artigo! :) Você conhece um método mais geral que pode ser aplicado a outros geradores de números aleatórios, não apenas congruentes lineares?

Paul

@Paul: É claro que é possível encontrar RNGs que são facilmente "resolvidos" para seus parâmetros a partir de dados de saída suficientes (problema inverso), mas parece que quanto melhor o RNG (mais aleatória a aparência da saída), mais difícil é o inverso problema seria. A solução do caso LCG está relacionada a certos efeitos dimensionais de agrupamento que são bem conhecidos, tornando pares de valores gerados distribuídos de maneira não uniforme. Para mais ver Seqüências Projeto de criptograficamente forte gerador, transformando linearmente gerados

hardmath