A method for seed recovering in the linear generator over the finite field complicated by mask adding.pdf Рассматривается линейный генератор [1], который определяется как последова-тельность над полем P = (GF(q), +, ), q = ps, удовлетворяющая линейномусоотношениюun+i = + b, a, b G GF(q), a = 0, n = 0 , 1 , . . .Пусть a = ( a i , . . . , a s ) -фиксированный базис поля P, e 0 , . . . , - некоторые элемен-ты поля P, которые имеют представление в базисе a:.j = e ( i )ai + . . . + e( s )as, G GF(p), i = 0 , . . . , s, j = 1 , . . . , s.(j)Зафиксируем k G N, k < s. Будем считать, что ) = 0 для всех i = 0 , . . . , s, j == k + 1 , . . . ,s.Пусть задано некоторое натуральное число t, k +1 ^ t > 2, известны параметры a, bи элементы w0 , . . . , w t - i поля P видаwj = uj - ej , i = 0 , . . . , t - 1. (1)Пусть также известно, что a G F, где F - фиксированное подмножество P,|F| < 2p5t + ^ 2^P2 k - t + 2 , где & - наибольший из делителей s, которые меньше t.В [1] предложен метод, позволяющий при данных условиях восстанавливать значе-ние u0 с полиномиальной сложностью. В докладе предлагается метод, позволяющийвосстанавливать u0 при условии, когда параметр b неизвестен.Теорема 1. Пусть известны w0 , . . . , w t - i из соотношения (1), известен мульти-пликативный множитель a, a G F С P, F - фиксированное множество, |F| < ++ (t k 2^P2 f c - t + 2 ' k + 1 ^ t > 2, - наибольший из делителей s, которые меньше t, инеизвестна аддитивная константа b. Тогда существует алгоритм, который при опреде-лённых условиях с полиномиальной сложностью находит начальное значение u0.

Скачать электронную версию публикации