В С Глухов - Вдосконалення алгоритму обчислення оберненого елемента gf(2t) в нормальому базисі - страница 2

Страницы:
1  2 

Аналізуючи табл. 6, можна зробити висновки:

кількість тактів однорозрядних зсувів не більша за 10 % від кількості тактів множення;зменшення кількості тактів зсуву зменшує загальну кількість тактів виконання алгоритму не більше ніж на 10 %;

серед основних полів з оптимальним нормальним базисом виділяються декілька з найменшою кількістю множень (10) - це поля зі степенями поліномів m = 173, 179, 281, 293;

якщо кращим вважати поле, в якому для обчислення обернених елементів треба витрачати меншу кількість тактів ніж хоча б в одному полі з меншим порядковим номером (з меншим за m), то найкращими є поля зі степенями поліномів m=281 та m=293 (7-е та 8-е поля, табл. 6 та рис. 4).

Множення Множення і зсуви

і і і і і і і і і і і і і і 1      3      5      7      9     11 13

Номер поля

Рис. 4. Кількість тактів множення і зсуву під час обчислення оберненого елемента у нормальному базисі (по осі X - номери полів з табл. 6)

Таблиця 6

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

m

(m-1)10

(m-1)2

k=

=[Iog(m-1)]

e=

=w(m-1)-1

n=k+e-1

Nm= n*m

Ns=m-e-1

%

1

173

172

10101100

7

4

10

1730

168

8,9

2

179

178

10110010

7

4

10

1790

174

8,9

3

191

190

10111110

7

6

12

2292

184

7,4

4

233

232

11101000

7

4

10

2330

228

8,9

5

239

238

11101110

7

6

12

2868

232

7,5

6

251

250

11111010

7

6

12

3012

244

7,5

7

281

280

100011000

8

3

10

2810

277

9

8

293

292

100100100

8

3

10

2930

289

9

9

359

358

101100110

8

5

12

4308

353

7,6

10

419

418

110100010

8

4

11

4609

414

8,2

11

431

430

110101110

8

6

13

5603

424

7

12

443

442

110111010

8

6

13

5759

436

7

13

491

490

111101010

8

6

13

6383

484

7

14

509

508

111111100

8

7

14

7126

501

6,6

Висновки. У роботі описане вдосконалення алгоритму Іто-Тічей-Цудзії (Itoh, Teechai, and Tsujii) знаходження оберненого елемента поля Галуа GF(2m) в оптимальному нормальному базисі. Вдосконалення полягає у зменшенні часу виконання послідовності операцій піднесення до квадрата

m

л

о

5

оиии

8000 4 7000 6000 5000 4 4000

3000

2000

1000

(послідовності операцій циклічного зсуву праворуч на один двійковий розряд). Використання вузлів циклічного зсуву на багато розрядів дає змогу скоротити час виконання послідовності зсувів приблизно на порядок, а час виконання алгоритму загалом приблизно на 7-9 %.

З метою зменшення тривалості обчислень рекомендується під час роботи відповідно до стандарту [1] у нормальному базисі використовувати поля зі степенями поліномів m=281 та m=293

1. Національний стандарт України ДСТУ 4145-2002. Інформаційні технології. Крипто­графічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевіряння. - К.: Державний комітет України з питань технічного регулювання та споживчої політики, 2003. 2. IEEE Std 1363-2000 IEEE Standard Specifications for Public-Key Cryptography Sponsor Microprocessor and Microcomputer Standards Committee of the IEEE Computer Society. Approved 30 January 2000. 3. Itoh T., Teechai O., Tsujii S. A Fast Algorithm for Computing Multiplicative Inverses in GF(2t) Using Normal Bases // J. Society for Electronic Communications. - Japan, 1986. - 44. -Р. 31-36. 4. Глухов В., Заіченко Н., Оліярник Б. Шифропроцесор для бортових інформаційно-керуючих систем //Наукові нотатки: Міжвуз. зб. (за напрямом "Інженерна механіка"). - 2007. -Вип. 19. Луцький державний технічний університет. - Луцьк, 2007. - С. 33-43. 5. Глухов В.С., Євтушенко К.С., Заіченко Н.В., Оліярник Б.О. Криптографічні засоби спеціалізованої бортової ЕОМ для бронетехніки // Вісн. Хмельницьк. анц. ун-ту. - 2007. - № 2. Технічні науки. -Хмельницький, 2007. - Т. 2. - С. 29-33. 6. Глухов В.С. Операційний пристрій для роботи з елементами поля Галуа, представленими у нормальній формі //Матеріали наук.-техн. конф. ІППТ при Нац. ун-ту "Львівська політехніка". - Львів, 2007. 7. Глухов В.С. Обчислювальний пристрій для операцій над еліптичними кривими //Вісн. Нац. ун-ту "Львівська політехніка". - 2006. - № 573. -С. 54-61. 8. Hlukhov V. Improvement of Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Bases. Матеріали конференції ACSN'2007. - Львів, 2007.

УДК 681.3, 621.3

В.А. Голембо, О.Ю. Бочкарьов, Х.Р. Попадюк

Національний університет "Львівська політехніка", кафедра електронних обчислювальних машин

ПРОБЛЕМА АЛГОРИТМІЧНОГО ЗАБЕЗПЕЧЕННЯ КОЛЕКТИВНОЇ ПОВЕДІНКИ АВТОНОМНИХ МОБІЛЬНИХ АГЕНТІВ В ЗАДАЧАХ ПРОСТОРОВОЇ САМООРГАНІЗАЦІЇ

© Голембо В.А., Бочкарьов О.Ю., ПопадюкХ.Р., 2007

Розглянуто підходи до розроблення алгоритмічного забезпечення колективної поведінки автономних мобільних агентів в задачах просторової самоорганізації на основі аналізу особливостей цих задач та різних варіантів комплектації робототехнічної платформи агента.

The approaches to the development of algorithms for collective behaviour of autonomous mobile agents in the tasks of spatial self-organization based on analysis of features of these tasks and various settings of agent's robotic platform are considered.

Вступ. Розглядається актуальна проблема розроблення алгоритмічного забезпечення багатоагентних систем (колективів агентів) в задачах просторової самоорганізації [1, 2]. Зокрема, обговорюється необхідність та можливість створення відповідного набору алгоритмів, який можна використовувати незалежно від типу мобільної робототехнічної платформи агента. Це, насамперед, зумовлено певною універсальністю задач просторової самоорганізації, вирішення яких потрібне для організації цілеспрямованої поведінки переважної більшості систем розподіленої робототехніки

Страницы:
1  2 


Похожие статьи

В С Глухов - Вдосконалення алгоритму обчислення оберненого елемента gf(2t) в нормальому базисі

В С Глухов - Система команд криптографічного процесора