Конечные поля и их приложения

Эти субкубические сложности часто цитируются в индексном исчислении и методах линеаризации. Поскольку в матричном произведении имеется n2 записей, нижняя граница для ω равна 2, что не было достигнуто для общих матриц. Однако для разреженных матриц сложность исключения Гаусса может быть почти квадратичной.Если не указано иное, предполагается, что устранение Гаусса выполняется с наихудшей сложностью при ω = 3. Следует отметить, что большинство систем, с которыми мы имеем дело, являются большими и разреженными, и значение ω для решения этих систем может быть значительно лучше, чем в худшем случае.Пример 3.1. Пусть кольцо многочленов будет F2[x1, x2]. Ниже приведены решения для двумерной булевой полиномиальной системы по переменным x1, x2∈F2.x1x2 = 0 x1x2 + x1 = 0 x1 + x2 = 1. Мономы, присутствующие в этой системе,v = (x1, x2, x1x2)T.Они могут быть помечены как линейные переменныеw = (w1, w2, w3) T = (x1, x2, x1x2) T, Линейная система может быть сгенерирована следующим образом.w3 = 0 w1 + w3 = 0 w1 + w2 = 1 Соответствующее матричное уравнение тогдаИспользуя метод исключения Гаусса или аналогичные методы, решение вышеприведенного уравнения может быть вычислено какw = (0,1,0) T. Это означает, что решение исходной двумерной полиномиальной системых = (0,1) T.3.2. Методы решения над конечными полямиВ общем случае эффективные методы решения линейных систем над комплексным полем нельзя использовать в конечных полях. Тем не менее, более сложные методы были разработаны специально для повышения эффективности вычислительных решений для линейных систем над конечными полями. Метод структурированного исключения Гаусса можно использовать для преобразования большой разреженной линейной системы в эквивалентную малую плотную систему, которая может быть обработана с использованием меньшего объема памяти. Метод Ланцоша для решения линейных систем является итерационным методом, который первоначально использовался для вычисления собственных значений матрицы. С тех пор он был адаптирован для решения линейных систем над конечными полями. Метод сопряженных градиентов очень похож на метод Ланцоша. Метод Видермана пытается восстановить характеристический многочлен матрицы, представляющей линейную систему, используя эффективный алгоритм Берлекампа-Массидля линейных рекуррент. Экспериментально показано, что все эти методы осуществимы при решении больших линейных систем над конечными полями и используются в алгоритмах факторизации и исчисления индекса.3.2.1.Одномерные полиномыВ кольце многочленов Fq[x] получение корней Fq одномерного многочлена f ∈Fq [x] тесно связано с факторингом f, поскольку каждый линейный множитель (x − γ) функции f дает корень γ. Доступно несколько методов нахождения корней одномерных полиномиальных уравнений над конечными полями. Простейшим подходом является алгоритм исчерпывающего поиска по пространству решений Fq. Это известно в теории кодирования как поиск Чьена. На практике корни обычно получают из методов полиномиальной факторизации.3.2.2. Полиномиальная факторизация и поиск корнейПусть Fq [x] - одномерное кольцо многочленов от неопределенногоx над конечным полем Fq из q элементов, а f - многочлен от Fq [x] степени d. Многочлен f может быть разложен на множители какгде многочлены fr,1, fr,2, ..., fr, sr - это sr-множители степени r, имеющие кратности er,1, er,2, ..., er, sr соответственно. Количество факторов и их кратность должны удовлетворять условию3.2.3. Общие корни одномерных полиномовИз факторизации многочлена f ∈F2n [x] корни F2 функции f можно вывести из линейных множителей. Если существует m многочленов f1, f2, ..., fm∈F2 [x], для которых нужно искать общие корни в F2, с учетом каждого fiдля вычисления соответствующих корней, а затем извлечения общих корней достигнет этой цели. Тем не менее, это занимает много времени, чтобы фактор каждого полинома. Поскольку общие корни F2n r1, r2, ..., rs из f1, f2, ..., fm должны составлять общий факториз f1, f2, ..., fm, это означает, что имеемu | НОД (f1, f2, ..., fm). В частности, имеем uv= НОД (f1, f2, ..., fm),где u - произведение общих линейных множителей f1, f2, ..., fm, как определено выше, и v - произведение нелинейных общих множителей (f1, f2, ..., fm),, которые неприводимы в F2n [x] , чьи корни не в F2n. Тогда можно увидеть, что можно вычислитьuv = НОД (f1, f2, ..., fm, x2n - x), поскольку (x2n - x) является произведением ровно всех линейных полиномов в F2n[x]. Факторинг u дает общие линейные множители и, в свою очередь, общие корни из f1, f2, ..., fm.Наибольший общий делитель двух полиномов часто вычисляется с помощью евклидова алгоритма, который является одним из старейших алгоритмов, используемых сегодня для вычисления наибольших общих делителей в евклидовых областях. Поскольку F2n [x] - евклидова область, можноиспользовать евклидов алгоритм для вычисления общих факторов и, в свою очередь, общих корней многочленов. Временная сложность евклидова алгоритма на полиномах степени n составляет O(n) делений, что соответствует не более чем O (n2) операциям в F2n [x]. Кроме того, в характерных двух областях евклидов алгоритм может быть реализован более эффективно. Евклидов НОД алгоритм будет использоваться для вычисления общих полиномиальных корней в алгебраическом анализе потоковых шифров в поле расширения.3.3. Принцип Хассе для целочисленного решения уравненияВ математике локально-глобальный принцип Гельмута Хассе, также известный как принцип Хассе, заключается в том, что можно найти целочисленное решение уравнения, используя китайскую теорему об остатках, чтобы собрать воедино решения по степеням по модулю каждого различного простого числа. Это решается путем изучения уравнения в дополнениях к рациональным числам: действительным числам и p-адическим числам. Более формальная версия принципа Хассе гласит, что некоторые типы уравнений имеют рациональное решение тогда и только тогда, когда они имеют решение в действительных числах и в p-адических числах для каждого простого числа p.Если дано полиномиальное уравнение с рациональными коэффициентами, и если оно имеет рациональное решение, то оно также дает реальное решение и p-адическое решение, поскольку рациональные решения встраиваются в вещественные числа и p-адические: глобальное решение дает локальные решения в каждом простом числе. Принцип Хассе решает, когда можно сделать обратное: когда можно объединить локальные решения, чтобы сформировать глобальное решение?Можно задать это для других колец или полей: например, целых чисел или числовых полей. Для числовых полей вместо реальных и p-адических используются сложные вложения и для простых идеалов p.Квадратичные формыТеорема Хассе – Минковского утверждает, что локально-глобальный принцип имеет место для задачи представления 0 квадратичными формами над рациональными числами; и в более общем случае по любому числовому полю (как доказано Хассе), когда используются все необходимые локальные поля необходимые условия. Теорема Хассе о циклических расширениях утверждает, что локально-глобальный принцип применим к условию быть относительной нормой для циклического расширения числовых полей.Кубические формыКонтрпример Эрнста С. Сельмера показывает, что теорема Хассе – Минковского не может быть распространена на формы степени 3: кубическое уравнение 3x3 + 4y3 + 5z3 = 0 имеет решение в действительных числах и во всех p-адических полях, но оно не имеет нетривиального решения, в котором x, y и z являются рациональными числами. Поскольку любая кубическая форма над p-адическими числами, по крайней мере, с десятью переменными, представляет 0, локально-глобальный принцип тривиально выполняется для кубических форм над рациональными числами, по крайней мере, в 14 переменных.Формы высшей степениПримеры показывают, что теорема Хассе – Минковского не распространяется на формы степени 10n + 5, где n - неотрицательное целое число. С другой стороны, если d - любое нечетное натуральное число, то существует число N (d), такое, что любая форма степени d в более чем N (d) переменных представляет 0: принцип Хассе выполняется тривиально.Также устанавливается локально-глобальный принцип расщепления центральной простой алгебры A над полем алгебраических чисел K. Он утверждает, что если A расщепляется над каждым пополнением Kv, то он изоморфен алгебре матриц над K.Принцип Хассе для алгебраических групп гласит, что если G является односвязной алгебраической группой, определенной над глобальным полем k, то отображение изинъективно, где произведение находится над всеми местами sиз k.Принцип Хассе для ортогональных групп тесно связан с принципом Хассе для соответствующих квадратичных форм.Kneserи другие авторы проверили принцип Хассе с помощью доказательств для каждой группы. Последним случаем была группа E8, которая была завершена только Черноусовым спустя много лет после других случаев.3.4. Системы открытых ключей в полях расширенияЭффективность является одним из важнейших аспектов успеха криптографической системы с открытым ключом, и способность выполнять быструю арифметику лежит в основе эффективности вычислений в этих системах. Необходимо применить методы умножения полей расширений к системам открытых ключей, построенным на полях расширений. Алгебраический метод получения алгоритмов умножения достигает результатов, таких же или даже лучших, чем те, которые ранее сообщались в некоторых из этих систем открытых ключей. Также возможны эксперименты с различными основаниями, чтобы продемонстрировать гибкость алгебраического описания умножения поля расширения.С момента своего появления в 1976 году многие исследователи предложили множество систем открытых ключей, основанных на проблеме дискретного логарифма. До сегодняшнего дня наиболее влиятельными системами были обмен ключами Диффи-Хеллмана и схема шифрования Эль-Гамаля. Трудность решения проблемы дискретного логарифма имеет широкое признание, хотя недавние достижения в субэкспоненциальных алгоритмах, решающих проблему дискретного логарифма в конечных полях, подразумевают, что размер ключа, необходимый для защиты таких криптосистем, в настоящее время составляет около 1024 бит и скоро станет всё большим. Способ противодействия этой проблеме был введен в 1985 году с использованием эллиптических кривых, для которых не существует известных субэкспоненциальных алгоритмов для решения лежащей в основе задачи дискретного логарифма. С 1993 года также предлагались способы уменьшения размера ключа для систем над полями расширения при сохранении того же уровня безопасности. Их ассоциированные системы включают создание изоморфизмов между циклической подгруппой поля расширения и меньшим полем расширения, и это позволяет элементам в циклической подгруппе быть представленными с меньшим размером данных, сохраняя при этом безопасность системы. В 2004 году эти методы были модифицированы и обобщены в то, что сейчас известно как криптосистемы на основе тора [14].3.3.1 Криптография с открытым ключомДискретные логарифмы вместе с целочисленной факторизацией составляют две основные неразрешимые проблемы теории чисел, которые широко используются для проектирования в системах с открытым ключом. В отличие от целочисленной факторизации, которая определяется в целочисленном кольце ℤ, проблема дискретного логарифма может быть определена для любой циклической группы. Простейшая реализация систем с открытым ключом, основанная на задаче дискретного логарифма, - над циклическими группами в простых полях Fp, которые требуют только модульной арифметики. Затем могут быть выполнены такие протоколы, как обмен ключами Диффи-Хеллмана и шифрование Эль-Гамаля. Возможность реализации криптографии с открытым ключом в циклических подгруппах общих полей расширения на основе проблемы дискретного логарифма обсуждалась с момента публикации системы открытых ключей Эль-Гамаля. Он не получил широкого внимания, поскольку вычисления в простых полях и двоичных полях, как правило, гораздо проще реализовать, чем в полях расширения.Определение 3.1 (Проблема дискретного логарифма в полях расширения). Пусть G циклическая подгруппа мультипликативной группы F∗q поля расширения Fq, а g ∈ G - генератор группы G. Пусть h ∈ G. Для g, h задача дискретного логарифма в конечном поле является задачей вычисления наименьшего целого числа х, такого чтоgx = h. В системе с открытым ключом, основанной на проблеме дискретного логарифма, открытый ключ получается из g, а закрытый ключ из h. В этом случае безопасность системы заключается в трудности нахождения x со знанием g, h. Поскольку криптоаналитическая эффективность увеличивается, количество элементов циклической группы 〈g〉 должно увеличиваться, чтобы система открытого ключа оставалась защищенной. На момент написания рекомендуемый размер g составляет не менее 1024 бит для обеспечения безопасности в ближайшем будущем и не менее 2048 бит для обеспечения безопасности в течение более длительного периода. Предпринимались попытки уменьшить длину ключей при сохранении безопасности, чтобы обеспечить более сжатые реализации систем открытых ключей, особенно в устройствах с ограниченной памятью. С этой целью была введена криптография с эллиптической кривой. В текущем состоянии криптоаналитических методов и вычислительной мощности, размер ключа около 160 битов достаточен, чтобы противостоять атакам на дискретные логарифмы эллиптической кривой. Однако, поскольку арифметика на эллиптических кривых обычно громоздка, были предложены альтернативные системы открытых ключей, основанные на полях расширения, которые также достигают небольших размеров ключей. К ним относятся криптография на основе трассировки и криптография на основе тора [14], в которых используются специальные структуры для получения компактного представления групповых элементов.3.4 Трассировка криптографииДля компактного представления элементов поля расширения был введен ряд систем открытых ключей, начиная с системы открытых ключей LUC в 1993 году [13]. Сначала LUC предоставил возможность использования трасс в качестве средства для компактного представления. В 2000 году система открытых ключей XTR затем оказала влияние в области криптографии на основе трассировки как возможной альтернативы криптографии на эллиптических кривых. За этим последовало несколько вариантов и предположение о дальнейших основанных на трассировке системах открытых ключей, вплоть до появления торической криптографии [12].Определение 3.2. Пусть Fq - конечное поле с q элементами. Циклотомическая подгруппа Gq,n в Fqn является мультипликативной подгруппой в F*qnпорядка Φn(q), n-й циклотомический многочлен, оцененный в точке q.Определение 3.3. Пусть Fq - конечное поле с q элементами, а Fqn - поле расширения Fq степени n. Карта трассы Fqn относительно Fq определяется какЗначениеназывается следом x по отношению к Fq. Tr (x) обозначает след x в указанном выше контексте. Системы открытых ключей, основанные на трассировке, используют свойства трассировок элементов в циклотомических подгруппах для получения компактных представлений и эффективных вычислений. Здесь попутно следует сказать, что частный случай семейства систем открытых ключей GH, основанных на регистрах сдвига линейных обратных связей третьего порядка по Fp2, также дает систему открытых ключей XTR.3.3.1 LUCСистема открытого ключа LUC была введена в [13] и получила свое название от использования функций Lucas в системе. Это вариант систем с открытым ключом, основанный на дискретных логарифмах, построенный на циклотомической подгруппе Gp, 3 ⊂Fp2. В LUC элемент g ⊂Gp, 3 может быть однозначно представлен своим следом Tr(g) ∈Fp с точностью до его сопряженных. Пусть Vn = Tr (gn). Возведение в степень в LUC может тогда быть выполнено с представлением следа в Fp через рекуррентное отношениеVn + m = VnVm - Vn − m,который является частным случаем функций Лукаса. Это стоит одно умножение в Fp для каждой рекурсии. Затем система LUC может быть полностью реализована в Fp с использованием модульной арифметики. Затем было высказано предположение, что рекуррентное отношение громоздко использовать, например, в двойном возведении в степень. Реализация LUC в Fp2 с элементами, отображаемыми на их трассы в Fp только при необходимости передачи, может быть более гибкой. Однако стоимость реализации Fp2 значительно выше, чем реализация Fp. Для квадратичного расширения циклотомические поля Fp (ζ3) или Fp (ζ4) могут использоваться для эффективной арифметики с основаниями B3, i или B4, i соответственно. 3.2.2 XTRСистема открытых ключей XTR была введена в [5]. XTR обозначает Эффективное Компактное Представление Следа Подгруппы (ECSTR). Это вариант систем с открытым ключом, основанный на дискретных логарифмах, построенный на циклической подгруппе циклотомической подгруппы Gp, 6⊂Fp6. Основные результаты по XTR представлены ниже.Определение 3.4. Пусть Fp - простое поле из p элементов, Fp6 - расширение шестой степени Fp, а F*p2- его мультипликативная группа. Единственная мультипликативная подгруппа в Fp6 порядка Φ6 (p) называется супергруппой XTR. По существу, супергруппа XTR является просто циклотомической подгруппой Gp, 6.Лемма 3.5. Пусть Fp - простое поле из p элементов, а Fp2 - квадратичное расширение Fp. Элементы в супергруппе XTR могут быть однозначно представлены своими следами относительно Fp2 вплоть до их сопряженных.Элементы в подгруппе XTR могут быть представлены их следами, которые являются элементами в Fp2. Вычислительная эффективность в XTR достигается вследствие того, что вся арифметика может быть выполнена в Fp2.Пусть g - генератор циклической подгруппы 〈g〉super супергруппы XTR. Проблема дискретного логарифма в циклической подгруппе 〈g〉 образует основу безопасности системы открытых ключей XTR. Следовательно, порядок g определяет безопасность XTR от атак подгрупп, таких как методы Полларда [13]. Что касается субэкспоненциальных методов над полями, безопасность XTR основывается на том факте, что наименьшее поле, в которое может быть встроено 〈g〉, - это Fp6, поэтому безопасность XTR от этих методов такая же, как у систем на основе Fp6. Затем говорится, что XTR обеспечивает безопасность Fp6, используя только реализацию Fp2. Однако это утверждение было опровергнуто открытием эффективных методов исчисления индекса по алгебраическим торам, в которые может быть встроена группа XTR.Подобно системе открытых ключей LUC, XTR имеет свою собственную специализированную арифметику в Fp2. Однако было обнаружено, что сравнительно эффективно использовать реализацию в Fp6 с отображением элементов на их трассы, когда необходимо хранение или передача. Кроме того, реализация в Fp6 является более гибкой и может вместить больше приложений. В [5] также было исследовано использование гауссовых нормальных базисов для XTR, что показывает, что большее число простых чисел p пригодно для использования в системе. Полученные реализации достаточно эффективны по сравнению с исходной с оптимальными нормальными основаниями.Арифметика XTR была исследована и реализована в программном обеспечении. Из-за доступности эффективных методов возведения в степень в полном представлении Fp6 разница в эффективности между двумя реализациями минимальна, несмотря на гораздо более высокую стоимость умножения в более крупной области.3.3 Торическая криптографияКриптография на основе торов [14] была предложена в качестве общей основы для проектирования систем с открытым ключом на основе алгебраических торов. Концепция была взята из модификации систем открытых ключей на основе трассировки. Подобно криптографии на основе трассировки, цель криптографии на основе тора состоит в том, чтобы предоставить компактные представления систем с открытым ключом, основанные на проблеме дискретного логарифма, без ущерба для безопасности. Основные результаты из [14] об использовании алгебраических торов в криптографии представлены ниже.Определение 4.6. Пусть k поле, n> 0 целое число и L ≡ Fpn. n-й алгебраический тор Tn является множествомгде NL / F обозначает отображение нормы L относительно подполя F в L.Все элементы в Tn(k) имеют норму один относительно всех собственных подполей в L.Лемма 3.7. Пусть Tn (Fp) n-й алгебраический тор над простым полем Fp. Следующие свойства справедливы для тора Tn (k).1. Tn (Fp) ∼Gp, n,2. | Tn (Fp) | = Φn (p),3. Если h ∈Tn (Fp) - элемент простого порядка, не делящий n, то h не лежит в собственном подполе Fpn / Fp.посколькуΦn (p) ∤ pr - 1, r 0 алгебраический тор Tn рациональный.Рациональность Tn доказана, когда n - простое число или произведение двух простых чисел. Для общего n результаты неубедительны. Кроме того, для тех n, где Tn является рациональным, все еще необходимо построить рациональную параметризацию алгебраических торов Tn для использования в системе с открытым ключом. В [14] были показаны явные изоморфизмы для T2 и T6.Система открытого ключа, использующая T2, была показана в [14] как наименьший пример криптосистем на основе тора. Подобно LUC, элементы в системе на основе T2 могут быть встроены в квадратичное поле расширения Fpn и могут быть представлены элементами в Fp. Однако вместо использования карты трасс для получения компактного представления, как в LUC, система T2 использует бирациональный изоморфизм T2 (Fp) ∼ A (Fp). Рациональная параметризация T2 также содержится в рамках построения системы открытых ключей CEILIDH.CEILIDHСистема открытых ключей CEILIDH [8] - это криптосистема на основе тора, построенная на алгебраическом торе T6 (Fp) над простым полем Fp. Поскольку 6 = 2 • 3 - произведение двух простых чисел, T6 рационально. Бирациональный изоморфизм может быть построен между T6 (Fp) и A2 (Fp), так что элементы в CEILIDH могут быть представлены с использованием двух элементов в Fp. Первоначальное описание CEILIDH включало построение алгоритмов для выполнения арифметики T6 (Fp) через A2 (Fp). Однако было обнаружено, что это неэффективно по сравнению с другими криптосистемами. Следовательно, при построении CEILIDH арифметика в T6 (Fp) выполняется в циклотомической подгруппе Gp, 6 в Fp6 с отображением сжатия в A2 (Fp), когда требуется хранение или передача элементов CEILIDH. Явные бирациональные карты между торами T6 и A2, используемые в этой реализации CEILIDH, были получены из [14].Система открытых ключей CEILIDH реализована с использованием четырех представлений F1, F2, F3, A2 (Fp) алгебраического тора T6 (Fp) и отображений между соседними представлениями. Алгоритм Карацубы используется с умножением в Fp6 в F1 с использованием базы B9,1. Это то же представление, что и для XTR. F2, F3 используют алгоритм Карацубы для умножения и возведения в квадрат в поле множественного расширения F(p2)3, сB2,0 = {1, ζ3},B3 = {−ζ39–ζ69, ζ9 + ζ89, ζ39 + ζ79}в качестве базисов для квадратичного и кубического расширений соответственно. Для F1 приводятся экспериментальные результаты вычислительных затрат на умножение Карацубы и возведение в квадрат по различным базисам, которые можно использовать при его реализации. C (T) представляет собой сложность таблицы умножения оснований, W (M), W (N) - веса матриц в алгоритме Карацубы для умножения и возведения в квадрат соответственно и A (M), A (N) – стоимость умножения и возведения в квадрат через M, N с использованием алгоритма Карацубы соответственно. Видно, что сложности T, M, N не играют большой роли в определении стоимости алгоритмов. Это связано с тем, что степень оптимизации определяется фактическими структурами M, N, а не их сложностями. Аналогично низкая стоимость арифметики с различными основаниями показывает, что для реализации представления F1 доступно больше вариантов.Наконец, обратите внимание, что F4– это просто собственное представление тора в A3 (Fp), которое используется только для передачи и не требует арифметических процедур. 3.4.2. Системы на основе больших размерных торовЧтобы алгебраический тор Tn размерности n был пригоден для использования в системе открытых ключей, он должен быть рациональным. Это накладывает довольно большое ограничение на выбор n. Эта проблема была преодолена путем присоединения асимптотически малых структур к алгебраическим торам Tn для любого n, чтобы создать слегка модифицированные алгебраические многообразия, которые являются рациональными для реализации систем с открытым ключом. Было показано, что существуют бирациональные изоморфизмыTn × Ak∼AdВ частности, криптосистема с открытым ключом на основе алгебраического тора T30 была предложена в [12]. Хотя T30 не был показан рациональным, бирациональный изоморфизмT30 × A2∼ A10был найден в [12], улучшая предыдущую идею. Это позволяет элементу в T30 быть представленным с 8 элементами при условии, что к нему добавлены 2 дополнительных элемента из A2. В [12] изоморфизмT30 (Fp) × T6 (Fp) ∼ T6 (Fp5) был также представлен, что позволяет системе выполнять арифметику в T6 (Fp6) вместо T30 (Fp). Это сделано для того, чтобы эффективная арифметика T6 для CEILIDH могла быть перенесена в эту систему, с той лишь разницей, что арифметика выполняется по Fp5, а не по Fp. Следовательно, эффективная арифметика в Fp5 требуется в дополнение к таковой в Fp6. В предлагаемой реализации затраты на умножение в Fp5 были уменьшены до 18M + 40A по сравнению с ранее сообщенными 18M + 75A в [12]. Это, в свою очередь, приводит к снижению затрат на умножение и возведение в квадрат в T6 (Fp5).В дополнение к системе T30 криптосистема на основе тора на основе T210 была описана в [12]. Мы можем вывести арифметические затраты на такие криптосистемы, найдя подходящую конструкцию арифметики в Fp210. Одним из способов создания поля расширения являетсяFp210 ≡ F((p7)5)6. В дополнение к конструкции для T30 мы используем расширение степени семь с гауссовым нормальным базисом типа (7,4). Для этого нам потребуется, чтобы p ≡ l (mod 29), где l∈ {1,12,17,28}. То же самое квинтическое расширение, что и в T30, может снова использоваться для использования алгоритма быстрого возведения в квадрат в T6, как в системе на основе T30.Существует множество оснований для представления элементов в полях расширения с соответствующим выбором простых чисел. Некоторые из этих баз больше подходят для реализации арифметики поля расширения в системах с открытым ключом для эффективности. В этой главе представлены приложения эффективной арифметики полей расширений в системах с открытым ключом, основанные на задаче дискретного логарифма над полями расширений, а именно криптосистемами на основе трасс и торическими криптосистемами. Используя наше новое алгебраическое описание арифметики поля расширения, были разработаны базы, совместимые с каждой системой, и оптимизирована стоимость арифметики. В некоторых случаях были достигнуты улучшения по сравнению с ранее описанными затратами. Эти методы реализации арифметики полей расширений могут быть адаптированы к текущим и будущим криптосистемам на основе полей расширений.ЗаключениеСуществует множество оснований для представления элементов в полях расширения с соответствующим выбором простых чисел. Некоторые из этих баз больше подходят для реализации арифметики поля расширения в системах с открытым ключом для эффективности. В этой работе представлены приложения эффективной арифметики полей расширений в системах с открытым ключом, основанные на задаче дискретного логарифма над полями расширений, а именно криптосистемами на основе трасс и торическими криптосистемами. Используя новое алгебраическое описание арифметики поля расширения, разработаны базы, совместимые с каждой системой, и оптимизирована стоимость арифметики. В некоторых случаях были достигнуты улучшения по сравнению с ранее описанными затратами. Эти методы реализации арифметики полей расширений могут быть адаптированы к текущим и будущим криптосистемам на основе полей расширений.Список использованныхисточниковБаричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. – М.: Горячая линия. Телеком, 2001. – 120с.Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. и др. Кодирование информации (двоичные коды). / Под ред. Н.Т. Березюка. – Харьков: Вища школа, 1978. – 252 с.БерлекэмпЭ., Алгебраическая теория кодирования, Мир, Москва, 1971.БлейхутР., Теория и практика кодов, контролирующих ошибки, Мир, Москва, 1986.БолотовА, ГашковС., ФроловА., ЧасовскихА. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. — КомКнига, 2006. — С. 390 — 398. — 527 с. — ISBN 5-484-00443-8Брейсуэлл Р. Преобразование Хартли. / Пер. с английского А.И. Папкова. – М.: МирВоскресенский В. Е. Бирациональная геометрия алгебраических групп.МЦНМО, 2009ЗензинО.С,. ИвановМ.А. Стандарт криптографической защиты - AES. Конечные поля.. — КУДИЦ-Образ, 2002. — С. 41 - 78. — 176 с. — ISBN 5-93378-046-4.Ленг С. Алгебра -М:, Мир, 1967 Лидл Р. Г. Нидеррайтер. Конечные поля. В 2-х томах. - Москва, "Мир", 1998.Хэмминг, К. Коды с обнаружением и исправлением ошибок. — М.: Издательство иностранной литературы, 1956. — С. 7-23.Шеннон, К. Математическая теория связи // Работы по теории информации и кибернетике. — М.: Издательство иностранной литературы, 1963. — С. 243—332.Bose R. C., Ray-Chaudhuri D. K. On a class of error-correcting binary group codes // Inform. Control. — vol. 3. — mars 1960. — p. 68—79.RabinM. Probabilistic Algorithm for Testing Primality, J. Number Th. 12 (1980), 128—138RubinK., Torus- based cryptography. – CRIPTO 2003, volume 2729, pp 349 – 365. USA 2003.http://www.ksu.ru/f9/index.php?id=20