(7.306), еслиА>=0, П{к)--=Ц1

и В{к) = 0; (7.307), если АфО, Д(А;) = и В{к) = 1, Г 5 (А;) при выборе (7.306); \1-В{к) при выборе (7.307).

На этом эвристическое исследование алгоритма заканчивается. Подведем итог. Мы исходим из начальных условий (7.316) и оп-

(7.319) Выбрать <

(7.320)

) Напомним, что, согласно сноске на стр. 38, deg О = - оо.

ределяем А<), используя формулу (7.302), a+i*, используя (7.304), ©(+1), используя (7.305) ж D {к -\- 1), используя (7.314). Затем в соответствии с (7.315) и (7.319) определяем т(+> и •у(+" с помощью (7.306) или (7.307), а В {к + i) в соответствии с формулой (7.320). Как будет показано, многочлены, определенные этими рекурсивными правилами, удовлетворяют уравнениям (7.301), (7.302), (7.312), (7.313), (7.317) и (7.318).

Точная формулировка алгоритма имеет следуюший вид.

7.4. Алгоритм решения ключевого уравнения над произвольным полем

Первоначально полагаем аС) = 1, т) = 1, (о = 1, v" = = 0, D (0) =0, Б (0)- = 0. Далее проводим рекурсию следующим образом. Если S+i не известно, то рекурсия не проводится; в противном случае полагаем А> равными коэффициенту при z" в произведении (1 + S) а и

= Д№)2Т(),

(oC+i) =(о<)- AW zyC).

Если А) = О или если D (к) >{к-\-1)/2, или если А<)ф О, а D (к) = (к -\- i)/2 и В (к) = О, то полагаем

Dik-\-i) =D (к),

В{к + 1)=В (к),

T<+l> = ZT,

Y<+i> = zv.

Если А*") фО ж если D {к) <(к + 1)/2 или ПЦк) = (к + 1)/2 и В (к) = I, то полагаем

Dik + i) = k-\-i-D (к), В{к + 1) = i- B (к).

7.41. Теорема. Для любого к

7.411. оС") (0) = (0) = 1.

7.412. (1 -Ь S) а") = + Ai> z+i mod z+

7.413. (1 + S) tC) = Y" + z" mod г+Ч

7.414. deg of) D (k), и равенство достигается при В (к)

= 1.

Если AW ФО Ж D {к) = {к-\- 1)/2, то либо (7.306), либо (7.307) приведет к многочленам т") и у<+Ц, степень каждого из которых А; + 1 - Z) (А; + 1). В случае сомнения в выборе между (7.306) и (7.307) его следует отложить до проведения дальнейших рассуждений.

Начальные уравнения имеют вид

(1 Ч- S) от = (оС*) mod Z, (1 + S) т(«) = (Y()-bl)mod Z.

Эти уравнения могут быть решены при следующих очевидных начальных условиях:

(7.316) а(«) = т(») = (оС) = 1, v" =0, D (0) = 0.

Отметим, что deg оС) = deg тС = deg ©С) = О = D (0), а deg = -оо <D (0) ). Таким образом, на первом шаге мы получаем даже усиление неравенств:

deg (о() < Z) (А;), Aegyi") <k-D {к).

Мы требуем, чтобы по крайней мере в одном из этих соотношений было строгое неравенство. Введем для удобства булеву функцию В (к) с начальным условием В (0) = 0. [В общем случае В (к) = О или в (к) - 1.] Тогда наши условия примут вид

(7.317) deg (О") (к) - В (к),

(7.318) degv" k-D (к) - II - В (к)].

Если при D (к) = и А}) О мы сделали правильный выбор

между (7.306) и (7.307) и если В (к) хорошо определена, то можно гарантировать выполнение условий (7.317) и (7.318) для всех к. Из (7.310) и (7.311) следует, что правильный выбор состоит в следующем:

Согласно утверждениям 7.415 и 7.416, deg cot) + deg т) < к. В силу теорем 7.414 и 7.417 deg at) + deg yt) к. Следовательно, deg {Tt)cot) - at)v<>} < A; и

T:(k)(ii(h) aWy(>) = z.

Доказательство утверждений 5(A;) = 0, TO

degvtft)A;-i»(A;)-l, degat)<£»(A;)

7.414-7.417. Если

Таккак то .

deg{at)v()}<A;-l.

deg {cot)Tt) - aWyik)} = k,

deg{co()T()}= A;, degco/") =Z)(A;), uegjW = k-D{k).

Аналогично, если 5 (A;) = 1, то deg cof*) D (A;) - 1, deg xf*) k-D (k) и deg {co()Tt)} < A; - 1. Значит, deg {a)yi>)} = k,

deg at") = D (k) и deg yi") = k-D (k).

Замечание к т-еореме 7.43. Эта теорема дает обпее решение (произвольной степени) сравнения а (0) = 1, (1 + 5) а = = со mod z***. Для теорем 7.41 и 7.42 важна взаимная простота многочленов at) и т"). Следовательно, любой многочлен / может быть представлен в виде

/ = Ua() + Fxt").

Теорема 7.43 утверждает, что если а и со - решения уравнений а (0) = 1, (1 + 5) а = со mod z", то в формулах а = i/at) + + Fxt) и со = i/cot) + Fyt") участвуют одни и те же многочлены и и V. Более того, согласно теореме 7.43, степени многочленов U и V малы.

Доказательство теоремы 7.43. По предположению со = (1 + 5) а mod z+. Умножение на cot) с использованием утверждения 7.412 дает

(l + 5)atb)co = (l + 5)acot),

at")co = acot), atft)(o -acot") = -zV,

7.415. deg т) - D (к), и при В (к) == О достигается равенство.

7.416. deg cot") (к) - В (к), и при В (к) = О достигается равенство.

7.417. deg vt") к - D (к) - [1 - В (к)], и при В (к] = 1 достигается равенство.

7.42. Теорема. Для каждого к

7.43. Т е о р е м а. Если а и со - произвольные многочлены, удовлетворяющие условиям

а(0) = 1, (l+jocomodz+S а D = max {deg а, deg со}, то существуют такие многочлены U и V, что и (0) = 1, F (0) = О, degU -D (к), deg F < £» -- Ik-D (к)] и

co = f7coW + FvW.

7.44. Теорема. Если многочлены а и со взаимно просты, 0 (0) = 1 и (1 + 5) а= со mod z*+\ то

7.441. Либо Aega>D{k)-\-l - B(k)>D{k), либо degcu>£» (А;), либо оба неравенства выполняются одновременно.

7.442. Если deg а < (fc + 1)/2 и deg со А;/2, то о = оС) и со = cot).

Доказательство теоремы 7.41, за исключением утверждений 7.411-7.417. Эти утверждения доказаны при эвристическом рассмотрении алгоритма. Читатель может провести прямое доказательство, используя индукцию по к.

Доказательство теоремы 7.42. Согласно теореме 7.41,

(l + 5)aWsco№modz+i,

(1 + S) тС) = v(b) z mod z+K Перемножив эти сравнения, получим

(1 + S) tWcoW = (1 + 5) (уС) + z). Деление на 1 + 5 дает

Так как

fj(k)k - az = mod z+i,

t WcoW - yWak) = zk mod z+i.

Аналогично, из (7.45) и (7.46) получаем

((nWxC) -aWyW)(i)--z (C/(o()+Fy()). Используя теорему 7.42, приходим к равенству

co = Z7(oW + Fy<".

Доказательство теоремы 7.44. Утверждение 7.441 следует непосредственно из уравнения (7.46) и утверждений 7.415 и 7.417. Значит, если deg о < (А; + 1)/2 и deg со < А;/2, то D (к) < (к -\- 1)/2, и если В (к) = О, то достигается строгое неравенство. В силу теорем 7.414 и 7.416

.deg0W<y:l, degcoW<4-,

deg (oWco) < A; + у < A; + 1,

deg(aco())<A; + 4<A;+l,

deg(- zV) = deg(a")© - acu<))<A; + 1, degF< 1.

Так как F (0) = 0, то отсюда следует, что F = 0. При этом по теореме 7.43 а =Ua() и со = i/coC). Так как по предположению многочлены а и (О взаимно просты, то U = i. щ

51 1

52 Si

53 S2

Si 1

о о о о

St St-i........Sli

St+i St St-i t~2......Si

Это уравнение надо решить относительно 0, а2, . . ., Oj и ю, ©2, . . ., ©й если известны Si, S2, . . ., S2t. Сначала мы определим 01, 02, 03, . . ., Of из уравнения ,

i+i St . . . S2 Si t+l • • S3 S2

Szt S2t-i • St+i . которое эквивалентно уравнению

St ...s;

St+i S2

Эти уравнения можно решать о помощью описанной в разд. 2.5 стандартной редукции матриц. Такой метод требует значительно большего числа вычислений и большего объема памяти, чем метод производящих функций, и, как видно из разд. 7.1-7.4, эти матрицы, вообще говоря, вводить нецелесообразно.

Тем не менее мы покажем, в какой связи находятся матричные методы и алгоритм 7.4. Для предыдущей системы (А; X А;)-матрица

*7.5. Связь с матричными методами декодирования

Предыдущие методы вычисления величин о) по величинам Sj относятся к прямым методам решения системы линейных уравнений. Вместо ключевого уравнения (1 + 5) о = со mod 2+ можно записать эквивалентное ему матричное уравнение

где F (0) = О и deg V {к) D - к. Далее, умножив первоначальное сравнение на т) ввиду утверждения 7.413, получим, что

(1 + S) т№(0 = (1 + 5) а (y") + z"),

х(а = а (у(> + z) = oy) + z, (7.46) xW(o - ay():=Uz>,

где U{0) = 1 и degUd - D{k). Из (7.45) и (7.46) получаем

(t(ft)(oW - a()Y()) а = {UoW + FxW), что, в силу теоремы 7.42, приводит к равенству