Несбалансированная сеть Фейстеля генерирует только полные перестановки с квадратными длинами - PullRequest
Новая
       16

Несбалансированная сеть Фейстеля генерирует только полные перестановки с квадратными длинами

0 голосов
/ 24 июня 2018

Я генерирую перестановки с обобщенной сетью Фейстеля , которая будет выводить целочисленные значения без знака в указанном диапазоне [0, period] псевдослучайно в соответствии со счетчиком, а затем цикл после достижения каждой из них все ровно один раз (без сохранения внутреннего состояния).

Вместо того, чтобы разбивать счетчик на два одинаковых по размеру битовых вектора L и R, я работаю с частным и остатком, который повторно собирается путем возврата частного * делитель + остаток. Это позволяет перестановки любого периода (не только те, которые имеют степени 2, , как LSFR ): 

uint16_t feistel(uint16_t counter, unsigned period)
{
    uint16_t d = sqrt(period);
    uint16_t s = period - d*d;
    uint16_t q = counter / d;
    uint16_t r = counter % s;

    for (int i = 0; i < 3; i++)
    {
        uint16_t nr = r;
        /* a simple insecure round function */
        uint16_t F = (i * r + q);
        r =  F % d;
        q = nr;
    }

    return q*d + r;
}

Этот код может правильно генерировать некоторые максимальные перестановки (т. Е. [feistel(N)...feistel(N+period)], содержащий каждое число между [0, period], в произвольном порядке).

Однако это происходит только для периодов, представляющих собой квадратные числа (где s = 0).

Можно ли это изменить, чтобы при любом выборе периода создавалась полная перестановка?

...