Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

461

Уап ЫиКекп С. Капк т й сЬате1ег оГ а §гарЬ. Ви11. зос. таА . Ве1§щт, В34, 1, 1982,

105-111.

^а1кир И.\У. Нош тапу шауз сап а регтШаЬоп Ье Гас1огес1т*о 1шо П — сус1ез. Безсге^е

таА., 28, 1979,315-319.

\Уап§ Е&п§. ТЬе сопАЬопз ап<1 теАоск аЬои! ехргеззт§ регтиЗДюпз аз а ргоёис! оГ1шо

сус1ез. Бэйцзин дасьюэ сюэбао, 5, 1986, 26-36.

^УетзбогТК. ТЬе опе-гоипб ЬтсЬопз оГАе ОЕ8 §епега!е Ае акетаЬп§ §гоир. Ргос. Еигосгур1-92, Ьес1. по!ез ш сотр. ЗС1., Уб58, 1993, 99 -1 12.

\УЛапсЬ Н. РтЬе регти!а1юп §гоирз. АсаА Ргезз, 1М.У., 1964.

^Лзоп К.М. СгарЬ риггкз, Ьото1ор1, апс! Ае акетаЬп^ §гоир. 1оита1 о!*сотЬ. Аеогу, , В16, 1974, 86-96.

Хи СЬеп§-Нао. ТЬе сотти 1а1огз о!*Ае аЬета1т § §гоир. 8с1епИа 8тн?а, 14, 3,1965,

339-342.

21езсЬап§ Т. СотЫпаЮпа1 ргорегбез оГЬаз1СепсгурЬоп орегаЬопз. А й\. т сгурю1о§у

Е1ЖОСКУРГ97. ЬесЬ по!ез ш сотр. зсь, У1233, 1997, 14-26.

Теоретические основы квантовой криптографии

С.Н. ВеппеП, (ЗиапШт спрЮ§гарЬу изт^ апу 1шо попог!о§опа1 з1а1ез, РЬуз1са1 Кеу1еу

ЬеПегз, V. 68, № 2}, р.3121, 1992.

С.Н. ВеппеИ, Р.ВеззеИе, С.ВгаззагЛ, Ь.8а1уаП,1.8то1т, Ехрептеп1а1 циапШт сгур!о§гарЬу, 1оита1 оГСгурю1о§у, у.5, №1, 1992, рр. 3-28.

КЛ. Ни§Ьез е1 а1., (ЗиапАт спрЮ^гарЬу оуег ип<1ег§гоип<1 орЬса1 ГЛегз, РгосееАп^з

СК1РТСГ96, р.329, 1996.

Р.Фейман, Р.Лейтон, М.Сэндс, Феймановские лекции по физике. Квантовая механика, т.8, М.: Мир, 1967.

К. Хелстром, Квантовая теория проверки гипотез и оценивания, М.: Мир, 1979.

462

ПРИЛОЖЕНИЕ 1 ' Классификация сигналов. Пояснения к выводу теоремы Котельникова

Классификация сигналов.

Физически сигнал реализуется в виде некоторого модулированного ко­ лебания. Если значения сигнала можно точно предсказать в любой момент времени, то он называется детерминированным. Примером непрерывных де­ терминированных сигналов являются импульсы или пачки импульсов, форма, амплитуда и положение во времени которых точно известны.

Все детерминированные процессы можно разделить на два класса: пе­ риодические и непериодические. Процесс 5(1) считается периодическим, если его значения точно повторяются через одинаковые отрезки времени Т, величи­

на которых называется периодом:

8Ц) = 8(1 + пТ); п = 1,2,3,..

Если такого отрезка времени нельзя указать, то процесс является непе­ риодическим. Периодические процессы делятся на гармонические и полигармонические. Класс непериодических процессов состоит из почти периодиче­ ских процессов и переходных процессов. Реально могут существовать любые комбинации этих процессов. Рассмотрим методы представления сигналов этих классов.

В качестве носителя сигналов часто рассматривается гармоническое ко­ лебание, изменяющееся в соответствии с выражением 8(1) = 8 тсоз(аЯ + (р) ,

где: 8т- амплитуда; со - круговая частота; <х>= 2 я / ; / - частота в герцах; <р- на­ чальная фаза. Это колебание является периодической функцией с периодом Т=

/ " ’. Частным случаем гармонического сигнала (при частоте а>= 0) является по­

стоянный уровень. Гармонические колебания - это наиболее простой вид не­ прерывных периодических процессов. Сам по себе бесконечный во времени гармонический процесс не является сигналом и не несет информации. Носите­ лем информации он становится после модуляции одного или нёскольких его параметров другим процессом, связанным с сообщением.

Полигармонические сигналы образуются любыми периодическими процессами, отличными от гармонических. Если некоторый процесс 8(1) с пе­ риодом Т удовлетворяет условиям Даламбера, т. е. является непрерывным вез­

де, кроме, может быть, счетного множества точек разрыва 1 рода, и имеет ко­ нечное число экстремумов, то он может быть представлен на интервале перио­ да [0,7] совокупностью базисных функций в виде суммы

а д = 2 ] С А ( о , ( о

к=0

463

где: $%(/) - к-я базисная функция; Ск - весовые коэффициенты. При

этом предполагается, что

Т/2

Г <рк (/) а ф о ,

-Г/2

т. е. никакая из функций базисной системы не равна тождественно нулю на ин­ тервале периода [0,7]". Система функций {^(7)} называется ортогональной, ес­ ли для любой пары к и 1 , исключая А=/, выполняется равенство

Т/2

|^ * (0 ^ /(0 Л = о -		(2)
-77 2
Если, при /= к
77 2
1 ^	( 0 * = //* * о ,	(3)
-Г /2	___

то величина V/** называется нормой функции <^(/) и обозначается \срк||. Если

норма функций ортогональной системы равна 1 , то такая система функций на­ зывается ортонормированной. Для определения коэффициентов Ск в разложе­

нии функции 8(1) в ортогональном базисе рассмотрим выражение

Т/2

-Т/2

Представив в подынтегральном выражении 5(0 в виде его разложения (1) и учитывая (2) и (3), получим:

Т/2 оо

1( 2 С гЧ>г(1 ))ф к(1 )<И = С к[<рк||2 .

-Т /2 г=0

Из последнего выражения находим значение коэффициента Ск:

1	Т/2
Ск=7—1$Ь)<Рк{*)Ж-		(4)
Ы	-Т/2

Сумма ( 1) с коэффициентами, определяемыми по (4) называется обоб­

щенным рядом Фурье по данной системе базисных функций {^ (/)}. Обобщен­ ный ряд Фурье обладает важным свойством: при заданной системе базисных функций и фиксированном числе N его слагаемых он обеспечивает наилучшую

аппроксимацию (в смысле среднеквадратической ошибки) заданной функции

8(1). При заданной системе базисных функций {</%(/)} сигнал 8(1) полностью определяется набором весовых коэффициентов Ск. Этот набор называется дис­ кретным спектром сигнала.

464

Для любой ортогональной системы справедливо неравенство Бесселя

Е З Ы ^ И ' ! 2-

к—О

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

1 ^ | Ы М	№ Г .
*=0	|1
Величину	|В Д 2 = ()$ называют энергией сигнала. Для энергии
сигнала получаем

0* = Х с Л Ы Г

(5)

к=0

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

а = 2 < ? .

*=о

Пояснения к выводу теоремы Котельникова.

Как отмечалось выше в теории анализа сигналов и технике связи широ­ кое применение находит теорема Котельникова (теорема отсчетов), в соответ­ ствии с которой функция 5(0 полностью определяется последовательностью своих значений в моменты времени, взятые с интервалами не более продолжи­ тельными, чем У2/в, если наибольшая частота в спектре этой функции меньше / в. В этом случае функция 5(0 может быть представлена выражением

где А( = 1 / 2 / в- интервал времени между двумя соседними отсчетами

сигнала 5(0, а 5(кЛ() - отсчеты функции 5(0 в моменты времени I = кА( ,

5т а?8(?-АгА?)

сов( { - к А ( )

'Функции вида <рк(?) встречаются при исследовании спектра одиночно­

го прямоугольного импульса. Эти функции образуют систему ортогональных функций с интервалом ортогональности, равным бесконечности, и нормой

2 г8Ш2 е>.(?-А:Д?) ,	1	г з т Ч х ) ,	п . .
= -----------------------	= —	-------т -^ х	= — = А?.

-оо К ( '- ^ А')]

х

сов

465

Покажем, что разложение сигнала 8(1) в этом базисе дает спектр, дейст­ вительно состоящий из отсчетов сигнала 8(кЛ(). Предварительно условимся, что энергия сигнала конечна, т. е. 8(1) является квадратично-интегрируемой функцией. Кроме того, отметим, что <рк{к&() = <рк{0) = 1, (рк (пА{) = О при п^к.

Напомним, что понятие спектральной плотности сигнала 8(1) опреде-

СО
ляют с помощью преобразования Фурье 8(со)= |	, где
—00

е^|Ю-со5соМ51псо1. 8(ю) называют спектральной плотностью сигнала 8(1) (в

общем случае это				копплексное число). Спектральная плотность одиночного
								00	^2
импульса 8,(1) на частоте <в=ксо1 равна 81(03)= | 8|(|:)е~'(о1ё1 = |										8|( 1:)е- 1КС011<11:,
								—оо	1|
где	[Т1,г2]		-	интервал		существования			импульса.	Выражение
	1	00
8(1)=—		[ 8(оз)е_1(0Моэ называют обратным преобразованием Фурье.
	2п	•’
	-0 0
	Спектральная плотность функции <рк{() равна
				1 л -1кД(со		А.	-1кД1	при |со| < сов
				е	= ш е
	Ф к (й>)= 2{в
			О				при |со| > сов.
	Отсюда следует, что модуль спектральной плотности любой базисной
функции		<рк (()	в полосе частот |й>| < а>в					имеет постоянное значение, равное
М = 1 / 2 / в = п!(Ов.
(4):	Определим			значения коэффициентов разложения, примеряя формулу
			■ с , = 4 - / $ ( < Ы 0 * .							г а

- 0 0

Для вычисления интеграла в этом выражении воспользуемся известным соотношением, устанавливающим связь между произведением двух функций ДО и &(0И произведением их спектров плотностей Р(йз) и С(щ)

I/М е й * =^ I

.

466

где С*(<у) - функция комплексно-сопряженная к С(й>). В соответствии с этим

свойством

1	ч,	1	1	м"
|8(1)фк(1)с11=—	|з(со)Фк(со)1со = —		—	|з(со)е,кА1®с1со = А13(кА1),
- 0 0	-сов	В		_ 6)в

где пределы интегрирования берутся равными граничной частоте сов спектра сигнала и базисных функций. Подставляя полученное значение интеграла в (7), имеем окончательное выражение для коэффициента разложения

Ск = 8{кАг) = 8к,

т. е. коэффициентами ряда Котельникова являются отсчеты сигнала в моменты времени I = кА( , как это было определено в (6). Ряд (6) сходится к функции 5(0 при любых значениях времени (, т. к. вследствие ограниченности верхней частоты сигнала он является непрерывным. /

Если отсчеты сигнала 8(1) берутся с интервалами Д^ = 1 / 2 / в, то шири­

на спектра базисных функций <рк{() совпадает с шириной спектра сигнала и представление сигнала соответствует (6). Если взять интервал между отсчетами равным А* < А( , то ширина спектра соответствующих базисных функций бу­ дет превышать спектр сигнала 5(0, что повышает точность представления этого сигнала. При этом исключается возможность отбрасывания «хвостов» спектра

8(а>) вне граничных частот. Если интервал АI > А1, то спектр соответствую­ щей базисной функции становится уже спектра сигнала 5(0 и коэффициенты С* в выражении (7) становятся отсчетами не этого сигнала 5(0, а некоторого дру­

гого сигнала, спектр которого ограничен другой частотой / в < / в.

Решение реальных задач связано с сигналами, одновременно ограни­ ченными и по частоте и по времени. Теоретически эти условия являются несо­ вместимыми. Практически эти ограничения определяют таким образом, ,чтобы основная часть энергии сигнала была заключена в пределах выбранной дли­ тельности этого сигнала и ширины его спектра, а на долю «хвостов» приходи­ лась бы только незначительная ее часть. При таком подходе для сигнала дли­ тельностью Т и верхней частотой полосы пропускания / в число независимых отсчетов, необходимое для полного задания сигнала, равно

^ = 7 7 = 2 / . г .	*
А1
В этом случае ряд (6) может быть представлен следующим образом
,31ПЛ>? ((-кА()
8 {()= У 8 (к А 1 ) - ^ ~	~

и' сов{г-кА {)

467

Число N называют базой сигнала или числом степеней свободы сигнала. Учитывая (5), можно представить энергию и среднюю мощность сигнала через последовательность его отсчетов

к=0		к=0
1	1 Ы О	N к=О

Последнее выражение показывает, что средняя мощность непрерывного сигнала на интервале Т равна среднему квадрату отсчетов, умещающихся на этом интервале через промежутки \!2/в.

ПРИЛОЖЕНИЕ 2 Линейные рекуррентные последовательности над конечным полем

Излагаемый материал основан на книге /М.М. Глухов, В.П. Елизаров, А.А. Не­ чаев “Алгебра. Часть И”, Москва, 1991/. Далее: К - коммутативное кольцо с единицей е, N - множество натуральных чисел; N0=N^>>0, X - множество целых чисел; ОР(ф - поле из ^ элементов; (а, Ь) - наибольший общий делитель а, Ь; [а, Ь] - наименьшее об­ щее кратное а, Ь; а | Ь - а делит Ь; V - для любого.

Основные определения.

Определение 1. Последовательностью над К назовем любую функцию и : N0—» Я, при этом для каждого N0элемент и(1) назовем 1 -м членом после­

довательности и. Множество всех последовательностей над К обозначим К00. Для наглядности последовательность ие К00 можно записать в виде бес­

конечного вектора и=(и(0), и(1),...,и(1),...).

П о след о ва т ельн о ст ь (0, 0 ,...,0 ,...) будем назы ват ь н улево й , и обозна­

чат ь через (0).

Определение 2. Последовательность иеК00 называют линейной рекур­ рентной последовательностью (ЛРП) порядка ш>0 над К., если существуют константы Г0, ГЬ...,ГП1_|еК такие, что V 1е N0

и(1+ш)= Гт_|и(1+щ -1)+...+ Г|и(1+1)+ Г0и(1):

В этом случае это соотношение называют законом рекурсии ЛРП и, многочлен Р(х)=хшГт_1Хт~' Г,х - Г0 - характеристическим многочленом

ЛРП и, а вектор и(0,...ш-1)=(и(0),...,и(ш-1)) - ее начальным вектором. После­ довательность (0) считается по определению единственной ЛРП порядка 0 с характеристическим многочленом Р(х)=е.

468

Пример 1. (Последовательность Фибоначчи). Эта последовательность была придумана для решения следующей задачи, называемой задачей о разм­ ножении кроликов. Допустим, что каждая пара зрелых кроликов через месяц рождает новую пару кроликов, которая еще через месяц достигает зрелости.

Сколько всего пар кроликов можно получить от одной зрелой пары за 1 меся­ цев? Если обозначить искомую величину через и(1), то нетрудно увидеть, что и(0)=1, и(1)=1 и и(1+2)=и(1+1)+и(0 для 1е 1Ч. Таким образом, и - ЛРП над Ъ

(кольцом целых чисел) с характеристическим многочленом Р(х)= х2 -х -1 и на­ чальным вектором и(0,1)=(1,1).

Арифметическая последовательность. Для любых элементов а, б из кольца К. последовательность V с общим членом у(1)=а+сй, 1е {0,1,...} есть ЛРП

порядка 2 с характеристическим многочленом Р(х)=х2-2х+е=(х-е)2 и началь­ ным вектором (а,а+ё).

Геометрическая последовательность. Для любых элементов а, ц из кольца К последовательность а,щ,...,а^,... есть ЛРП порядка 1 с характерис­ тическим многочленом Р(х)=х-ч^ и начальным вектором а.

Конгруэнтная последовательность. Для любых элементов я, б из кольца К последовательность \у(0),\у( 1),... ,\у(0, ..., определяемая соотношени­ ями \у(0)=а, \у(1+1)=ц\у(1)+<1, 1еИ0 есть ЛРП порядка 1 с характеристическим

многочленом Р(х)=(х-е)(х-я) и начальным вектором \у(0,1)=(а,ая+с1). Арифме­ тическая прогрессия есть частный случай конгруэнтной последовательности при я=е.

Пример 2. Линейный регистр сдвига с характеристическим многочле­ ном Р(х)=хт - Гт^х1"-1 - ...- Г[Х - Го - это конечный автомат вида

+

А

& &

А А

< -

м-СО <г

М-С1+1) 4 -

Здесь ц(1) - ячейка памяти, содержащая элемент ц(8)еК.; Г5 - узел, осуществляющий умножение на ; знак + обозначает узел, осуществляющий сложение в К.. В начальный такт работы в ячейках памяти регистра записан на­ чальный вектор ц(0,..., т -1 ) = (ц(0),... ,ц(т-1)) ЛРП . Такой регистр схематически обычно изображается следующим образом.

469

<■	М-0	4 -
	Заметим, что заполнение ц(1,	, 1+пт-Т) регистра в 1-й такт работы вы­

ражается через его начальное заполнение р (0,..., ш-1) формулой ц(1,..., 1+т-1) = р (0,..., т -1 )- 5(Р)',

где
0	0	...	0	/о
е	0	...	0	/ .
0	е	...	0	А
0	0	..,.	е	/т-1

- сопровождающая матрица для унитарного многочлена Р(х).

Напомним, чтоунитарным многочленом называется многочлен со ста­ ршим коэффициентом равным единице. Зафиксируем унитарный многочлен Р(х)=хт - 1т-|Хт_| - ...- Г]Х - Го еП[х] степени т>0 и обозначим через Ьц(Е) се­ мейство всех ЛРП над К. с характеристическим многочленом Р(х). Тогда непос­ редственно из определения 2 вытекает

Утверждение 1. Любая ЛРП иеЬк(Р) однозначно задается своим нача­ льным вектором и(0,...,т-1). Если |К.| < со, то | ЬК(Р)| = |К|т.

При исследовании свойств ЛРП весьма плодотворным оказывается ал­ гебраический подход, связанный с введением на К00 различных операций.

Определение 3. Суммой последовательностей и,у е Г и произведени­ ем и на константу ге К. называют, соответственно, последовательности ш = и + V и г = г • и, определяемые соотношениями

\у(1) = 11(1) + у(1), 2(1) = г • иО), 16 N0.

Очевидно, что группоид (К.00, +) есть абелева группа с нулем (0) и для любых а, Ъ е К., и, V е К.00 справедливы соотношения

(аЬ) • и = а • (Ь и), (а+Ь) • и = а • и + Ь и, а(и+у)=аи+ау, е-и=и.

470

В частности, если Р - поле, то определенные выше операции задают на

Р°° структуру левого векторного пространства рР00, имеющего, очевидно, беско­ нечную размерность.

Из определений 2, 3 легко следует Утверждение 2. Для любого унитарного многочлена Р(х)еК.[х] подм­

ножество Ьк(Р)сК“ - есть подгруппа группы (К°°,+), выдерживающая умноже­ ние на элементы из К. Если Р - поле и Р(х)еР[х], то Ьк(Р) - подпространство пространства Р°°.

Таким образом, в случае, когда Р - поле, можно говорить о базисе про­ странства Ьр(Р). Мы, однако не будем рассматривать эту простейшую ситуа­ цию отдельно, а введем и изучим аналог понятия базиса пространства для про­ извольного семейства Ьк(Р).

Определение 4. Для унитарного многочлена Р(х)еК.[х] степени ш>0

систему последовательностей иь...,итеЕк(Р) назовем базисом семейства ЬК(Р), если для любой последовательности иеЬк(Р) существует единственный набор констант сь...,ст еК такой, что

. ц=с,и1+...+стит

Доказательство существования и описание базисов семейства Ьк(Р)

дает

Утверждение 3. В обозначениях определения 4 система последователь­

ностей иь...,итеЬк(Р) есть базис ЬК(Р) тогда и только тогда, когда составленная из начальных векторов этих последовательностей матрица

^ и х(0,т —1)^

*У = '

ит(

обратима над кольцом К..

ДОКАЗАТЕЛЬСТВО. Еслц II - обратимая матрица, то для любой по­ следовательности иеЬк(Р) единственный набор (С1,С2,...,ст)еК.т такой, что

и(0,1,... , т - 1)=(с,,с2,... ,ст)-11.

Рассмотрим последовательность у=С|и|+...+стцт. По утверждению 2

У€ЬК(Р). Кроме того, очевидно, что у(0,...,т-1)=(с1,С2,...,ст)-Ы=и(0,1,...,т-1).

Поэтому в силу утверждения 1 у=и, то есть сраведливо равенство и=С1 и1 +...+стит. Единственность представления последовательности и в этом

виде следует из того, что это равенство влечет: и(0,1,...,т-1)=(с1,С2,...,ст)-11. Таким образом, щ ,...,ит - базис ЬК(Р).

Наоборот, пусть и!,...,ит - базис Ьк(Р). Определим для каждого

к € {!,...,т} ЛРП е/еЬкСР) начальным вектором: екр(0,...,т-1) - к-ой строкой