Специализированные методы редукции для фиксированных триномов и пентаномов

Страницы работы

3 страницы (Word-файл)

Содержание работы

14 Специализированные методы редукции для фиксированных триномов и пентаномов

Алгоритм               Пословная редукция (метод Шроппеля) для

f  (x) = x163 + x7 + x6 + x3 + 1.

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

ВХОД:            , определяемое фиксированным триномом или пентаномом f (x) = (f m  1 … f 1 f 0 ) 2 = (f L … f 2 f 1 ) ,

                        s (x) = (s 2×m – 1 … s 1 s 0 ) 2 = (s n … s 2 s 1 ) (т.е. deg(s (x)) = 2×m > m ) ;

                        w ¾ размер слова (w = 32).

ВЫХОД:         s (x) = s (x) mod f (x), s (x) = (s m – 2 … s 1 s 0 ) 2

                        (deg(s (x)) = ‑ 1 = < m).

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

1.    for ( i = ni > L ; i - -) { // по словам s от старших к младшим

               1.1    T = s i ;

               1.2    s i - 6 ^ = T << 29;                                          // 6 - тое слово при i = 12 

               1.3    s i - 5 ^ = (T<<4)^(T<<3)^T^(T>>3);            // 7 - ое слово при i = 12 

               1.4    s i  4 ^ = (T>>28)^(T>>29);                         // 8 - ое слово при i = 12 

       }

2.    T = s 6 & 0xfffffff8 ; // Очистка бит 0, 1, 2 значения s 6 

3.    s 1 ^ = (T<<4)^(T<<3)^T^(T>>3);

4.    s 2 ^ = (T>>28)^(T>>29);

5.    s 6 & = 0x00000007;       // очистка верхних неиспользуемых бит значения s 6 ( ≥ 163)

                                               // 6 слово: 160 ÷ 191

6.    коррекция длины s (x); // if(s[0] > f[0]) s[0] = f[0];

 


M_LONG f= {6, 0xC9, 0, 0, 0, 0, 0x8};

12 сл. 352 ¸ 383 бита

  1. g(x)= x352Å  f(x)
  2. g(x) = x393 Å f(x)

g(x)= x m1 (m1³ m)

Приклад розрахованих попередніх таблиць для формування констант алгоритму пословної редукції (метод Шроппеля) для модулю f(x) = x 163 + x 7 + x 6 + x 3 + 1 (№ 1 із ДСТУ 4145  2002)

Похожие материалы

Информация о работе