Реализация LFSR

Aleator · Регистрация: 04.05.2011

Author24 — интернет-сервис помощи студентам

Вопрос касается реализации LFSR. В "Прикладной криптографии" Шнайера даётся пример реализации LFSR для многочлена: $https://www.cyberforum.ru/cgi-bin/latex.cgi?x^{32}+x^7+x^5+x^3+x^2+x+1$

C

AnsiString j="";
    static unsigned long ShiftRegister=1;
    for (int i=0;i<30;i++)   {
        ShiftRegister=((
        ((ShiftRegister >> 31)     // 32
        ^(ShiftRegister >> 6)      // 7
        ^(ShiftRegister >> 4)      // 5
        ^(ShiftRegister >> 2)      // 3
        ^(ShiftRegister >> 1)      // 2
        ^(ShiftRegister ))         // 1
        & 0x00000001)
        <<31)|(ShiftRegister >> 1);
         j=j+(ShiftRegister & 0x00000001);
        }
         Form1->Edit3->Text=j;

В j получаю M-последовательность для кодирования.
Пробывал написать для многочлена $https://www.cyberforum.ru/cgi-bin/latex.cgi?x^4+x+1$ (для проверки). Получаю нужную последовательность.
А как написать для $https://www.cyberforum.ru/cgi-bin/latex.cgi?x^{29}+x^2+1$ ?
Мой вариант выдаёт одни нули:

C

ShiftRegister=((
       ((ShiftRegister >> 28)     
        ^(ShiftRegister >> 1) )    
        & 0x00000001)
        <<28)|(ShiftRegister >> 1);

@grizlik78 · 11.04.2016, 18:49

Для кода из #10
0 0 0 1
складываются два правых, сумма записывается слева. правый символ извлекается из регистра сдвига и выдаётся как выход.
static позволяет сохранить переменную до следующего вызова функции.

@frank63 · 11.04.2016, 19:03

C++

1	static unsigned long S = 1;

А для многочлена x^7+x^5+x^3+1 в этом случае каково будет начальное состояние регистра?

@grizlik78 · 11.04.2016, 19:04

любое можно от 1 до 2⁷–1, т. е. от 1 до 127.

@frank63 · 11.04.2016, 19:09

если задать начальное состояние так:

C++

1	static unsigned long S = 1;

, то как будут заполнены 7 ячеек?

@grizlik78 · 11.04.2016, 19:10

Ну двоичное представление числа 1, то есть 0 0 0 0 0 0 1

@frank63 · 11.04.2016, 19:15

то есть правильно ли я понимаю, что при любом многочлене 7-ой степени, если

C++

1	static unsigned long S = 1;

, то первые 7 значений псевдослучайной последовательности: 1 0 0 0 0 0 0?

@grizlik78 · 11.04.2016, 19:17

Да.

@frank63 · 11.04.2016, 20:14

у меня только для одного многочлена из 3 получается такое начало последовательности при S=1. (для x^7+x+1). для x^7+x^5+x^3+1 первые 7 значений: 1001011; для x^7+x^6+x^5+x^2+1: 1101010.
с чем это может быть связано?

Добавлено через 1 минуту
и кстати для x^7+x+1 в обратной последовательности: 0000001

Добавлено через 1 минуту

C++

    for (int i = 0; i < w; i++){
        uL ^= (ShiftRegister >> ptr[i]);
    }
    uL &= 1;
    uL <<= N-1;
    uL |= (ShiftRegister >> 1);
    ShiftRegister = uL;
    return ShiftRegister & 1;  
}

Добавлено через 58 секунд
ptr[i]-массив значений на которые надо сдвинуть ячейки регистра

@grizlik78 · 11.04.2016, 20:43

uL перед циклом обнуляется?

@frank63 · 11.04.2016, 21:08

да.

@grizlik78 · 11.04.2016, 21:15

Ну что тут можно сказать по обрывку. Смотрите содержимое ShiftRegister в начале и в конце каждого вызова функции.

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.04.2016, 19:04	23
	любое можно от 1 до 2⁷–1, т. е. от 1 до 127. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.04.2016, 19:10	25
	Ну двоичное представление числа 1, то есть 0 0 0 0 0 0 1 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.04.2016, 18:49	21
	Для кода из #10 0 0 0 1 складываются два правых, сумма записывается слева. правый символ извлекается из регистра сдвига и выдаётся как выход. static позволяет сохранить переменную до следующего вызова функции. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.04.2016, 19:17	27
	Да. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.04.2016, 20:43	29
	uL перед циклом обнуляется? 0

@frank63 1 / 1 / 0 Регистрация: 05.11.2012 Сообщений: 33
	11.04.2016, 21:08	30
	да. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.04.2016, 21:15	31
	Ну что тут можно сказать по обрывку. Смотрите содержимое ShiftRegister в начале и в конце каждого вызова функции. 0