Some subgroups of the burnside group.pdf Наиболее распространённые в настоящее время криптографические алгоритмы, такие, как RSA, Диффи - Хеллмана, на эллиптических кривых и др., зависят от структуры коммутативных групп и связаны со сложностью решения задачи факторизации целых чисел и дискретного логарифмирования. Однако в 1994 г. П. Шор представил квантовый алгоритм полиномиальной сложности, решающий эти проблемы [1]. Данный факт побудил исследователей к поиску альтернативных методов построения криптосистем. В последние два десятилетия были разработаны новые криптосистемы и протоколы обмена ключами, основанные на различных некоммутативных алгебраических системах (группы кос, полициклические группы, линейные группы и др.). Пусть B(m, п) = (x1,..., xm} - свободная бернсайдова группа периода п, в которой для любого элемента группы g выполняется тождество gn = 1. В работах [2-4] в качестве криптографических примитивов предложено использовать бернсайдовы группы периода n = 3. Для n > 3 вопрос пока не рассматривался. Заметим, что, помимо прикладного интереса, изучение бернсайдовых групп имеет большое значение и для алгебры, поскольку там до сих пор остаётся ряд нерешённых проблем. Например, неизвестно, конечна ли группа B(2, 5). Пусть B0(2, 5) = (x, y} -наибольшая конечная двупорождённая бернсайдова группа периода 5, порядок которой равен 534 [5]. Если группа B(2, 5) конечна, то B0(2, 5) = = B(2, 5). Рассмотрим подгруппы Hi группы B0(2, 5) следующего вида: Hi (ai ,bi) , где a0 = x, b0 = y, ai = ai-ibi-i и bi = bi-iai-i для i G N. Обозначим Ni и Ei - класс нильпотентности и энгелев индекс подгруппы Hi соответственно. В таблице представлены свойства групп Hi, полученные при помощи компьютерных вычислений. i ai, bi \\Hi\\ Ni Ei Hi абелева? 1 ХУ, yx 514 6 5 Нет 2 2 xy2x, yx2y 56 4 4 Нет 3 22 xy2xyx2y, 22 yx2 yxy2 x 53 2 2 Нет 4 2 2 2 2 2 xy2xyx2y2x2yxy2x, 2 2 2 2 2 yx2yxy2x2y2xyx2y 52 1 1 Да Заметим, что группа Hi уже изучена ранее [6]. Поскольку группа Н4 является абелевой, то Н5 - циклическая группа порядка 5, и серия подгрупп прерывается. В качестве примера далее представлено коммутаторное представление (power commutator presentation) подгруппы H2 = (a2,b2} = (xy2x,yx2y}. Для каждого элемента данной группы H2 существует уникальное коммутаторное представление вида ci1 ... c66, где ai G Z5, i = 1, 2,..., 6. Здесь c1 = a2 и c2 = b2 - порождающие элементы H2; c3.c4.c5.c6 - коммутаторы, которые вычисляются рекурсивно через c1 и c2: c5 = 1 (1 < i < 6), [C2,ci] = C3, [C3,Ci] = C4, [Сз,С2] = C5, [C4,Ci] = C6, [c4, c2] = 1, [c4, c3] = 1, [c5, ci] = 1, [c5, c2] = c46, [c5, c3] = 1, [c5, c4] = 1, [c6, ci] = 1, [c6, c2] = 1, [c6, c3] = 1, [c6, c4] = 1, [c6, c5] = 1. Для быстрого умножения элементов на основе алгоритма из [7] вычислены полиномы Холла группы H2. Пусть c^ ... ca6 и ce ... ce -два произвольных элемента из H2. Тогда ai- Yi € Z5, cai ca6 Si ce6 = cyi CY6 ci ... c6 ci ... c6 = ci ... c6 , где Yi = ai + ei, Y2 = a2 + в2, Y3 = аз + вз + a2 ei, Y4 = а4 + в4 + 2 а2 + а3в , а2 Y5 = а5 + в5 + 2 в1 + а3в2 + а2в1в2, a2 + ^^y ei +y2y а3 + a4 ei + 4а5в2 + 4 f 2 у ei в2 + + в + бМ + /М Y6 = a6 + e6 + I 2 ) аз + I з ) + 4( a2ei. Заслуживает внимания также тот факт, что элементы 2 2 2 2 2 b4 = yx17yxy17x17y17xyx17y порождают в B0(2, 5) абелеву подгруппу порядка 25. Длина каждого из этих элементов равна 16. При помощи компьютерных вычислений проведена проверка, которая показала, что никакие другие два групповых слова, длины которых меньше 16, не порождают нециклическую абелеву подгруппу в B0(2, 5).

Скачать электронную версию публикации