Xl Туполевские чтения : всероссийская (с международным участием) молодежная научная конференция. Казань, 8-10 октября 2003 г., тезисы докладов. Т. 3

к задаче программной реализации полиномиальной модели конечного детерминированного автомата С.Ю. Соколов, Б.Ф. Эминов Научный руководитель: С.В. Шалагин, к.т.н., ассистеп г Казанский государственный технический университет им. Л.П. Гунолева В работе решена задача программной реализации конечного дегерми- нированного автомата в виде полиномиальной функции от двух перемен­ ных [1], вида / ( х , ? ) = Y^UjjX'q' , г = 2"-\, i.J=0 С помощью разработанного комплекса программ, решена задача ав­ томатизированного нахождения коэффициентов полиномиальной функции f(x,q) по матрице У , задающей функцию переходов конечного детерминированного автомата, а также обратная задача. В рамках данной работы решается задача программной реа]шза1ши умножения элементов поля, превышающих размерность ма1пин1юго cjtoBa. Проведен обзор известных подходов реализации алгоритмов умножения, деления и возведения в степень над конечными полями. Рассмотрены как классические алгоритмы, так и их модернизации [2]. Проведен их сравни­ тельный анализ по критерию оценки общего времени вьто;шения вычис­ лений. С целью максимального увеличения быстродействия вычислений, ал­ горитмы реализованы в виде набора ассемблерных процедур. BbHmjnienbi эксперименты и найдена максимальная размерность конечного hojhi, вы числения в котором обеспечивают приемлемое время получения результа та на компьютере Celeron 533, с оперативной памятью 192 МЬ (OIMM) и тактовой частотой 6 6 МГ ц. При наложении определенных офаничений на вход реализуемо!'» ко­ нечного детерминированного автомата, можно моделировачь конечные однородные цепи Маркова [1]. Созданная про1раммная система использу ­ ется для проведения лабораторных работ но дисциплине «MoдeJшpoвa ние». Литература: 1 Захаров В.М., Нурутдинов Ш.Р., Шалагин (;.В. Полиномиальное пред ставление цепей Маркова над полем Галуа // Вестник Казан, гос. гехн. ун-та им. А.Н. Туполева. 2001. № 3. С. 27-31. 2. Болотов А.А., Гашков С.Б., Фролов Л.Б., Часовских Л.Л. Ajnоригмиче- ские основы эллиптической криптографии. М.: МЭИ, 2000. 27