Непредсказуемый подсчет числа

Question

Скажем, у меня 32-разрядное целое число. Первоначально я семя это черный ящик с чем-то случайным/секретным.

Каждый раз, когда я звоню, заранее, я получаю следующее число в последовательности, но следующее число в последовательности не обязательно является следующим наибольшим числом, например ++ это что-то непредсказуемое. Я сделал это, используя таблицу перестановок, но для этого требуется много места, и мне было интересно, знает ли кто-нибудь конкретную конструкцию, которая дала бы мне весь диапазон в каком-то детерминистском порядке, основанном на некотором начальном значении, а затем только дает значение ровно один раз за цикл.

Кто-нибудь знает о такой схеме?

Answer 1

Есть интересный ответ на вопрос о crypto.stackexchange.com Томасом Порнином, в котором говорится о том, как создать безопасный alternating step generator (ASG).

Это не самое быстрое решение моей проблемы, но я думаю, что это сработает.

Я написал этот код, чтобы проверить мою теорию

struct Lfsr 
{ 
    public readonly int State; 

    public Lfsr(int seed) 
    { 
     this.State = seed; 
    } 

    public Lfsr Advance() 
    { 
     var bit = ((State >> 30)^(State >> 27)) & 1; //^(State >> 1)^(State >> 0) 
     return new Lfsr(((State << 1) | bit) & 0x7fffffff); 
    } 
} 

static void Main(string[] args) 
{ 
    var n = 0; 

    var lfsr = new Lfsr(1); 

    do 
    { 
     lfsr = lfsr.Advance(); 

     ++n; 
    } 
    while (lfsr.State != 1); 

    Console.WriteLine(n); 
} 

На моей машине потребовалось около 7 секунд до перебрать с периодом 2147483647 подсчитывали число. Чтобы обеспечить безопасность, вам необходимо объединить их в ASG и использовать в три раза большие линейные сдвиговые регистры обратной связи (LFSR).

Для прочности вам также необходимо использовать полиномы обратной связи максимальной длины. статья Википедии ссылается на PDF, в которой перечислены полиномы обратной связи максимальной длины длиной до 168 бит.