Сдвиг цикла LFSR за O (1) раз?

Question

Мне интересно, есть ли способ объединить две концепции: LFSR и баррель Shifters

Я ищу способ, чтобы за O (1) сместить цикл LFSR на заданное количество смен.

Я надеюсь найти простой процесс, в котором у меня есть текущее состояние LFSR и сколько раз я хочу перейти из этого состояния в качестве параметров к быстрому / простому процессу.

Сначала я просто подумал о том, чтобы посмотреть на все отводы, затем переместить отводы на 1 и посмотреть на них снова, каждый раз находя сдвиг в битах и ​​добавляя его в конец, но, конечно, это не O ( 1) и это усложняется, если я хочу сдвигаться так много раз, что касание «соскользнет» с исходного состояния LFSR.

Если нет времени O (1), есть ли более эффективный способ сделать несколько смен, чем каждое по отдельности?

Answer 1

В общем, я склонен сказать, что ответ - нет. Причина в том, что если бы существовал такой алгоритм, то мы могли бы за O (1) раз вычислить любой данный бит в последовательности, сгенерированной LFSR. В общем, вряд ли это выполнимо.

Однако вы можете сделать некоторые предварительные вычисления, чтобы немного ускорить процесс. Обратите внимание, что после любого фиксированного числа шагов состояние каждой ячейки в LFSR является линейной комбинацией битов из начального состояния. Итак, если вы предварительно вычислите коэффициенты в этой линейной комбинации для каждой ячейки за 1 шаг, 2 шага, 4 шага, 8 шагов и т. Д., То вы сможете прыгнуть вперед на много шагов за относительно короткое время. Конечно, это действительно даст вам полезное ускорение в случаях «соскальзывания», о которых вы упоминали ранее.

Answer 2

Что мне приходит в голову, если отводы занимают небольшую область регистра, что вы можете использовать поиск по таблице для выполнения одного или нескольких битов за раз.

Пример, если регистр8 битов пронумерованы слева направо от 7 до 0, а ответвления - это биты 0 и 2. Биты младшего разряда 3 могут извлечь новый бит 7 из таблицы 8 записей.

Аналогично, 4 бита младшего разрядаможет получить новые 7,6 бит из таблицы с 16 записями.Младшие 5 битов могут быть использованы для извлечения новых битов 7,6,5 из таблицы с 32 записями и т. Д.

Просто мысль.

Answer 3

Криптоанализ алгоритмов шифрования на основе LFSR делает это по существу, но в обратном порядке (т. Е. Они решают для условий на [current-N] итерациях (обычно в начальном состоянии), а не [current + N]. прежде всего) путем создания набора линейных уравнений, а затем решения. Я никогда не пытался переставить их так, чтобы они шли вперед, а не назад, но на первый взгляд кажется, что это должно быть вполне возможным (часть радости от того, что они линейны .. .)

Таким образом, чтение о некоторых известных атаках на алгоритмы шифрования на основе LFSR, вероятно, было бы полезно / полезно.

Answer 4

Если вы хотите увеличить последовательность LFSR на степень два, это возможно.Если вы возьмете последовательность LFSR максимальной длины и разбите ее на 2 ^ N частей по битам (чтобы в результате чередования этих частей вы получили исходную последовательность), каждая из этих отдельных последовательностей будет идентична оригиналу со сдвигомв фазе.

Таким образом, вы можете удвоить последовательность отводов обратной связи и запустить 2 ^ N LFSR параллельно (в регистре, который в 2 ^ N раз шире оригинала):

#include <iostream>
using namespace ::std;

void
galois1(const unsigned int taps, const unsigned int seed)
{
  unsigned lfsr = seed;
  do {
    cout << ((lfsr & 1) ? '1' : '0');
    lfsr =
      (lfsr >> 1)
      ^ (-(lfsr & 1) & taps);
  } while (lfsr != seed);

  cout << endl;
}

void
galois2(const unsigned int taps, const unsigned int seed)
{
  unsigned lfsr = seed;
  do {
    cout << ((lfsr & 1) ? '1' : '0') << ((lfsr & 2) ? '1' : '0');
    lfsr =
      (lfsr >> 2)
      ^ (-(lfsr & 1) & taps & 0x5555)
      ^ (-(lfsr & 2) & taps & 0xaaaa);
  } while (lfsr != seed);

  cout << endl;
}

int
main(void)
{
  // Original LFSR sequence, x^5 + x^3 + 1:
  //
  // Taps:  1 0 1 0 0
  // Seed:  1 0 0 0 0

  galois1(0x0014, 0x0010);

  // "Double stepped" sequence, interleaved bits:
  //
  // Taps (even):   1   0   1   0   0
  // Taps (odd):  1   0   1   0   0
  // Seed (even):   0   0   1   0   0
  // Seed (odd):  1   1   0   0   0

  galois2(0x330, 0x290);

  return 0;
}

Единственная сложная задача - выяснить новые начальные числа (и если вы найдете способ сделать это без генерации первых 2N битов последовательности, я хотел бы знать: -)