Процессы управления и устойчивость

если x(R

1

·R

2

)·R

3

y, то xR

1

·(R

2

·R

3

)y. Аналогично показывается, что

из xR

1

· (R

2

· R

3

)y следует, что x(R

1

· R

2

) · R

3

y. Тем самым показано,

что (R

1

· R

2

) · R

3

= R

1

· (R

2

· R

3

).

Нетрудно видеть, что A(R

1

R

2

) = A(R

1

) ˙

+A(R

2

) и A(R

1

· R

2

) =

A(R

1

) ˙

×A(R

2

).

Определение 7 ([3], стр. 250).

n

k=1

R

k

называется транзитив-

ным замыканием бинарного отношения R, заданного на множестве

X, мощности n (т.е. |X| = n).

Матрицей транзитивного замыкания будет матрица ˜

A(R) =

˙

+

n

k=1

A

˙

×k

(R). Другими словами, ˜

A(R) равно булевской сумме бу-

левских степеней матрицы A(R).

Как видно из выше сказанного, для вычисления матрицы тран-

зитивного замыкания и нужны операции ˙

+ и ˙

×.

4. Моделирование операций ˙

+ и ˙

×. Поскольку в большин-

стве программных продуктов для компьютеров можно найти стан-

дартные программы умножения и сложения матриц, то целью этого

раздела является показать, как программно реализовать булевское

сложение и умножение матриц.

Определение 8 ([4], стр. 427). Индикаторной матрицей для

матрицы A = (a

ij

) называется матрица M (A) = (m

ij

), где

m

ij

=

0, если a

ij

= 0,

1, если a

ij

= 0.

Из определения 8 видно, что на выражение M (A) можно смот-

реть, как на операцию, сопоставляющую матрице A ее индикаторную

матрицу

Утверждение 1. A ˙

+B = M (A + B) и A ˙

×B = M (A · B).

Другими словами, в утверждении 1 говорится, что операцию бу-

левского сложения (0,1)-матриц всегда можно заменить двумя опера-

циями – операцией обычного сложения матриц и последующей опе-

рацией построения индикаторной матрицы полученной суммы мат-

риц. А операцию булевского умножения (0,1)-матриц заменить опе-

рациями обычного умножения матриц и последующего построения

индикаторной матрицы полученного произведения матриц.

Доказательство. Доказательство проведем только для булев-

ского умножения матриц, поскольку для булевского сложения оно

проводится аналогично.

362

Итак, пусть A ˙

×B = C, а M (A · B) = D, где A = (a

ij

), B = (b

ij

),

C = (c

ij

), D = (d

ij

). Нужно показать, что c

ij

= d

ij

.

Поскольку c

ij

, как и d

ij

, может равняться только нулю или едини-

це, то нужно показать, что c

ij

равняется нулю тогда и только тогда,

когда d

ij

равняется нулю, и c

ij

равняется единице тогда и только

тогда, когда d

ij

равняется единице.

Из определений булевского умножения матриц и построения ин-

дикаторной матрицы следует, что

c

ij

=

n

k=1

a

ik

b

kj

, d

ij

=

0, если

n

k=1

a

ik

b

kj

= 0,

1, если

n

k=1

a

ik

b

kj

> 0.

.

Рассмотрение формул для c

ij

и d

ij

показывает, что они могут рав-

няться нулю или единице только одновременно. Тем самым утвер-

ждение 1 доказано.

5. Применение булевского произведения (0,1)-матриц

для определения неразложимости матрицы.

Теорема 1. Квадратная матрица A размерности n тогда и

только тогда неразложима, когда (E +|A|)

n−1

> 0 или, что эквива-

лентно, когда (E + M (A))

n−1

> 0. Здесь E – единичная матрица, а

через |A| обозначена матрица, построенная из модулей элементов

матрицы A.

Показатель n − 1, фигурирующий в теореме, при практических

вычислениях всегда можно заменить относительно большим числом

2

k

, где k вычисляется из условия минимальности для выполнения

неравенства 2

k

≥ (n − 1). Это позволяет заменить последовательное

умножение матриц, последовательным возведением в квадрат ([4],

стр. 614).

Поскольку (E + M (A))

2

k

> 0 эквивалентно тому, что матрица

M (E + M (A))

2

k

> 0 (слева булевская степень; тогда неравенство

означает, что слева – матрица из одних единиц), то одно вычисление

всегда можно заменить другим. Замечание об эквивалентности двух

неравенств означает, что они выполняются только одновременно.

Сказанное выше позволяет переформулировать теорему 1.

Теорема 2. Квадратная матрица A размерности n тогда и

только тогда неразложима, когда матрица M (E + M (A))

2

k

состо-

ит из одних единиц, где k вычисляется из условия минимальности

для выполнения неравенства 2

k

≥ (n − 1).

363

Проверка на разложимость матрицы A легко реализуется в среде

Matlab с помощью программы:

function razl

n=input(’размерность матрицы C -- ’);

C=rand(n,n);

B=triu(C)-diag(diag(triu(C)));

S=B+B’

i=1:n; j=1:n;

A(i,j)=round(S(i,j));

x=nextpow2(n-1);

V=(A+eye(n))^2;

for k=1:x F=V^k;

for i=1:n; for j=1:n; if F(i,j)>0; F(i,j)=1; else F(i,j)=0;

end end end

if F==1 input(’A неразложима’) else input(’A разложима’) end end

Литература

1. Шрейдер Ю. А. Равенство, сходство, порядок. М.: Наука, 1971.

256 с.

2. Макаров Ч.М., Виноградская Т.М., Рубчинский А.А., Соколов

В.Б. Теория выбора и принятия решения: учебное пособие.М.: На-

ука. Главная редакция физико-математической литературы, 1982.

328 c.

3. Оре О. Теория графов. М.: Наука, 1968. 352 с.

4. Хорн Р., Джонсон Ч. Матричный анализ: Пер. с англ. М.: Мир,

1989. 656 с.

364

Левина А.Б.

Санкт-Петербургский государственный университет

Устойчивость алгоритмов шифрования

при использовании параллельных систем

1

Рекомендовано к публикации профессором Демьяновичем Ю.К.

1. Постановка задачи. В настоящее время криптографические

алгоритмы находят широкое применение не только в задачах шифро-

вания данных, но и для аутентификации и проверки целостности [1].

На сегодняшний день существуют хорошо известные и апробирован-

ные криптоалгоритмы (как с симметричными, так и открытым клю-

чами), криптостойкость которых либо доказана математически, либо

основана на необходимости решения математически сложной задачи

(факторизации, дискретного логарифмирования и т.п.). К наиболее

известным из них относятся DES, RSA. Эти алгоритмы не могут

быть вскрыты без полного перебора или решения указанных задач.

Техника шифрования с открытым ключом, разработанная для реше-

ния проблем распределения ключей и аутентификации, имеет мно-

го преимуществ перед симметричным шифрованием. Одним из пре-

имуществ является то, что две стороны могут начать обмениваться

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

тельно об общем ключе. Криптосистемы с открытым ключом дают

возможность подписывать сообщения, электронные заказы, финан-

совые поручения. Криптосистемы с открытым ключом обеспечивают

существование технологий электронной торговли, поэтому обеспече-

ние и исследование их криптостойкости является актуальной пробле-

мой. В связи с широким использованием в настоящее время парал-

лельных компьютерных систем возникает вопрос криптостойкости

алгоритмов шифрования в условиях работы параллельных систем.

В данной работе рассмотрен наиболее известный алгоритм шифро-

вания с открытым ключом – алгоритм RSA. В результате станет

ясно, что устойчивость алгоритма в связи с его распараллеливанием

ослабится.

1

Работа выполнена при финансовой поддержке РФФИ (гранты № 04-01-00692

и 04-01-0026)

365

2. Описание алгоритма RSA. Алгоритм RSA – первый из ал-

горитмов шифрования с открытым ключом. Идея криптографии с

открытым ключом впервые появилась в 1976 году в работе Диффи

и Хелмана "Новые направления в криптографии", год спустя была

опубликована первая криптосистема с открытым ключом – RSA. Ос-

новой криптосистемы RSA является соответствующая задача RSA.

3. Задача RSA. Даны числа S и E, последнее из которых удо-

влетворяет соотношению:

НОД(E, (p − 1)(q − 1)) = 1.

Требуется найти такое число m, что

m

E

= C(mod N ).

Данная задача сводится к поиску простых делителей двух натураль-

ных чисел. Можно утверждать, что криптостойкость алгоритма RSA

базируется на сложности проблемы факторизации, хотя задачу RSA

можно решить и не решая задачу разложения на множители.

4. Алгоритм RSA. Для простоты введем двух пользователей,

обменивающихся информацией – Алиса и Боб. Алиса подбирает два

простых больших числа p и q и публикует их произведение, которое

называется модулем алгоритма,

N = pq.

Также Алиса генерирует шифрующую экспоненту E, удовлетворя-

ющую условию:

НОД(E, (p − 1)(q − 1)) = 1.

Доступная пара (N, E). Секретный ключ генерируется Алисой при

помощи расширенного алгоритма Евклида к паре чисел

(E, (p − 1)(q − 1)).

Расшифровывающая экспонента d удовлетворяет следующему соот-

ношению:

Ed = 1(mod (p − 1)(q − 1)).

366

Секретным ключом является тройка (d, p, q). Боб намерен зашиф-

ровать свое сообщение и переслать его Алисе. Для этого он берет

открытый ключ Алисы – пару (N, E) и получает шифротекст C из

своего сообщения m по следующему правилу:

C = m

E

(mod N ).

Алиса расшифровывает шифрограмму, возводя число C в степень d:

m = C

d

(mod N ).

5. Результат анализа устойчивости RSA в связи с воз-

можностью его распараллеливания. Криптостойкость алгорит-

ма RSA обеспечивается сложностью вычисления расшифровываю-

щей экспоненты по открытому ключу, т. е. по (N, E) . Задача RSA

не сложнее задачи факторизации, поэтому если разложить число N

на простые множители, т.е. на p и q, то можно вычислить d.

Существует несколько алгоритмов факторизации числа N . Наи-

более известные из них – это пробное деление, метод эллиптиче-

ской кривой, квадратичное решето, квадратичное решето в числовом

поле, методы, основанные на разности квадратов. Соответственно

возникает вопрос о возможности распараллеливания этих методов.

Удачное распараллеливание этих методов может дать существенный

выигрыш во времени при разложении чисел на множители, следова-

тельно, ослабить криптостойкость алгоритма RSA.

Литература

1. Смарт Н. Криптография М.: Техносфера, 2005. 192с.

367

Мирошниченко И.Д.

Санкт-Петербургский государственный университет

Методика формирования образовательного

процесса на основе параллельных технологий

В настоящее время образовательный процесс, как в вузе, так

и в общеобразовательной сфере все больше требует использования

в методах обучения применения дистанционных и параллельных

технологий. Здесь будет предпринята попытка обобщения с точки

зрения параллельных технологий опыта преподавания информаци-

онных дисциплин различным категориям слушателей: студентам –

информатикам-социологам (2–5 курсов), слушателям, повышающим

свою квалификацию по информатике и старшим школьникам раз-

личных школ одного из районов Санкт-Петербурга.

Рассмотрим следующие фрагменты образовательного процесса:

1. Технология Web-верстки.

2. Подготовка тестовой базы по изучаемой дисциплине силами

студентов и проведение тестирования для повышения среднего уров-

ня усвоения изучаемого материала.

3. Параллельное сравнительное изучение элементов языков про-

граммирования (С и JavaScript).

4. Сравнительное изучение пакетов прикладных программ смеж-

ных научных областей с целью возможного использования их в даль-

нейшей практической деятельности (MAPLE, MATHLAB, MathType

и др).

Технология Web-верстки может рассматриваться с нескольких

позиций: a) как коллективная работа над общим проектом, которая

практически использует параллельные технологии ввиду того, что

выполняется либо в сетевом режиме в компьютерном классе, либо в

дистанционном режиме на удаленных компьютерах; b) как работа,

обучающая новым технологиям и закрепляющая полученные уме-

ния и навыки; c) результатом этой работы является современный

материал (книга), необходимый в изучении текущего или грядущего

курса, имеющий очень небольшой объем (550 стр.).

Организация коллективной работы над общим проектом в до-

вольно сжатые сроки по стандартным правилам с использованием

368

возможностей дистанционного доступа и Интернет-технологий соб-

ственно представляет один из аспектов распараллеливания учебного

процесса.

1. Индивидуальные работы по Web-верстке можно распределить

между студентами различных курсов, так как одни студенты могут

находиться в процессе обучения используемым в Web-верстке техно-

логиям, а другие – их закреплять, или же работы студентов старших

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

2. В каждой группе индивидуальные работы должны быть вы-

полнены по стандартной инструкции и прилагаемым шаблонам для

структуры и различных фрагментов документа.

3. Понятно, что современные возможности Интернет-технологий,

удаленного доступа и возможности работы в локальных сетях поз-

воляют выполнять индивидуальную работу по Web-верстке в самых

различных вариантах использования места и времени: в компьютер-

ном классе в локальной сети на практическом занятии одновремен-

но или в удобное время; выполняться одновременно или в заданные

сроки вне локальной сети с передачей результата каким-либо спосо-

бом по требуемому адресу (по почте, установкой на сайт или иным

способом). Такой способ выполнения задания очень важен для совре-

менных студентов или слушателей, так как подчас именно в данный

момент они по каким-либо причинам присутствовать на занятии не

могут, но для выполнения индивидуального задания дома или на

работе имеют условия технически совершеннее учебных.

Если рассматривать образовательный процесс как некую вычис-

лительную систему простых функциональных устройств (студен-

тов), тогда, применяя к множеству наших студентов (как к системе

простых функциональных устройств) первый закон Амдала, полу-

чим естественный вывод, что в общем случае производительность

верстки всего материала (образовательного процесса) определится

деловыми качествами и ответственностью самого нерадивого сту-

дента (самого непроизводительного функционального устройства).

На практике, чтобы не слишком зависеть от нерадивости, полезно

для таких студентов определить индивидуальные задания дальнего

плана или иметь в запасе небольшую дополнительную работу.

Согласно Амдалу, можно определить загруженность студента в

образовательном процессе на некоторый период T . Загруженность

369

студента можно рассматривать как отношение выполненной работы

за данный период времени (стоимость реально выполненной работы)

к работе, заданной преподавателем на этот период (стоимость макси-

мально возможной работы). Тогда, согласно Амдалу, максимальная

стоимость работы, которую можно выполнить за время T для про-

стых функциональных устройств равна T , а для конвейерных – nT .

Это означает (в идеале), что если все студенты за время T будут вы-

полнять работу параллельно, то окончательный результат получат

за время T . Если (в идеале) группа 3 курса выполняет свою работу

параллельно, как и группа 4 курса, но в различные непересекающи-

еся для этих групп часы, то окончательный результат получим за

время 2T .

Аналогично, можно ввести понятие реальной загруженности

группы студентов по Амбалу, если определить загруженность каж-

дого из студентов группы (pi) и его пиковую производительность

(?i). Пиковая производительность (?i) – это максимальное количе-

ство операций, которое может быть выполнено i-м студентом за еди-

ницу времени при отсутствии взаимодействий с другими студентами

из рассматриваемой группы (или множества студентов). Тогда ре-

альная производительность нашего образовательного процесса (си-

стемы) выражается суммой всех произведений загруженности каж-

дого из студентов группы (pi) на его пиковую производительность

(?i). Понятно, что, анализируя образовательный процесс и выделив

долю последовательных вычислений для процесса, к нему можно

примерить также 2 закон Амдала о максимально возможном уско-

рении процесса и 3 закон Амдала о верхней границе этого ускорения.

Отметим также, что самое слабое звено любой вычислительной

системы – передача информации (данных) от устройства к устрой-

ству или к памяти. Поэтому скорость выполнения запланирован-

ной работы резко возрастает при оптимальной организации про-

цесса передачи информации в образовательном процессе от студен-

та/преподавателя к студенту/преподавателю, т. е. с использованием

дистанционных и параллельных технологий передачи данных (элек-

тронная почта, рассылка, выкладка на сайт и т. д.)

Заметим, из-за того, что студенты вне компьютерного класса име-

ют условия технически более совершенные, чем учебные, и/или име-

ют возможность больше времени потратить на выполнение своего

370

индивидуального задания (чем запланировано учебным процессом

для работы), скорость и качество выполнения индивидуальных за-

даний студентами значительно увеличивается, а, значит, и общий

результат можно получить быстрее.

С точки зрения обучения новым технологиям и закрепления по-

лученных умений и навыков предложенная технология Web-верстки

весьма эффективна и обеспечивает достаточно устойчивые резуль-

таты, а именно:

• практическое знакомство с различными пакетами программ

просмотра и обработки информации (работа со сканером, редакто-

ром DJVU, пакетами FineReader, Photoshop или другими пакетами

обработки графической информации);

• закрепление навыков работы с языком HTML (сложные табли-

цы, перекрестные ссылки, ссылки внутри документа), элементами

каскадных таблиц стилей CSS;

• выполнение индивидуальных заданий больших объемов по

стандартным шаблонам для получения единообразного электронно-

го материала.

Результат коллективной работы – это электронный вариант мате-

риала, требуемый для изучения информационной дисциплины, изу-

чаемой непосредственно в текущем семестре или в недалеком буду-

щем. Исходный печатный материал, изначально имевший большой

объем (книга 400–550 стр.), представляет в результате папку доку-

ментов формата .html весьма и весьма небольшого объема, которыми

удобно пользоваться.

Для студентов же важно иметь такой материал небольшого объ-

ема, например, для пересылки домой по почте, так как по изуча-

емому предмету используется обычно достаточно много современ-

ной печатной литературы, которую, в таком случае, преподаватель

мог бы считать обязательной для изучения (минимальным или стан-

дартным набором). Такой вариант обработки материала не наруша-

ет прав автора, так как не используется в коммерческих целях, зато

электронный вариант современного учебника, доступно и глубоко из-

лагающего современные проблемы, наоборот, стимулирует к покупке

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

Процесс подготовки тестовой базы по изучаемой дисциплине си-

лами студентов и проведение тестирования для повышения среднего

371

уровня усвоения изучаемого материала также использует идеологию

распараллеливания.

Прежде всего, хотелось бы отметить, что содержание информа-

ционных дисциплин приходится модифицировать практически каж-

дый год, в отличие от классических математических дисциплин. Это

связано, как мы знаем, с появлением, как новых версий действу-

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

программных продуктов и технологий, предназначенных как специ-

алистам IT, так и ориентированных на решение проблем в самых

различных сферах.

В таких условиях наполнение конкретной дисциплины с каждым

годом необходимо обновлять, модифицировать в той или иной сте-

пени, вводить практические работы, связанные с появляющимися

технологиями, для ознакомления с ними студентов (информатиков

– социологов), хотя бы в общих чертах. Конечно, лекционный ма-

териал в виде электронных материалов студентам предоставляется

разными способами и на CD, и по электронной почте, и сбрасывается

на сервер.

Однако, для того, чтобы изучаемый материал был, по возможно-

сти, усвоен всеми студентами, с различной степенью подготовленно-

сти и скоростью усвоения, представляется полезным вводить не ме-

нее 1 раза в месяц семинарские занятия. За семестр таким образом

студенты должны подготовить не менее 6 докладов. Темы докладов

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: