Алгоритм вычисления элемента Штикельбергера для мнимых мультиквадра-тичных полей | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/3

Алгоритм вычисления элемента Штикельбергера для мнимых мультиквадра-тичных полей

Представлен алгоритм вычисления идеала Штикельбергера для мультиквадра-тичного поля K = Q(\\/di, Vd2,..., V^n), где d = 1 (mod 4), i = 1,..., n, и d попарно взаимно просты. Мы алгоритмизируем идеи, описанные в работе Р. Кучеры 1996 г., доказываем корректность полученных алгоритмов и анализируем их сложность. Для 2n = [K : Q] алгоритм работает за время O(2n). Полученный результат полезен для решения криптоаналитических задач поиска короткого вектора в идеалах мультиквадратичных полей.

An algorithm for computing the Stickelberger elements for imaginary multiquadratic fields.pdf Введение Получение идеала Штикельбергера в явном виде является важной алгоритмической задачей в вычислительной теории чисел, в теории групп классов и, с недавних пор, в криптоанализе. Для числового поля K идеал Штикельбергера I - идеал групповой алгебры Z[GK], где GK = Gal(K/Q) -группа Галуа поля K. Полезное свойство I заключается в том, что под действием элементов I на CIk - группу классов идеалов K - любой класс становится тривиальным (иначе говоря, Ja - главный идеал для любого а Е I и любого идеала J кольца целых Ok числового поля K). Для кругового поля K = Q((n) идеал Штикельбергера, рассматриваемый как решётка в Zn с помощью вложения Z[G#] ^ Zn, обладает «хорошим» базисом. Явный вид этого базиса описан, например, в [1]. Это свойство идеала Штикельбергера в сочетании с 1) «обнуляющим» действием элементов идеала на целые идеалы Z[Zn] и 2) существованием (относительно) быстрого алгоритма нахождения короткого вектора в главных идеалах Z[Zn] позволило получить алгоритм нахождения короткого вектора в идеалах кольца целых круговых полей [1]. В современном криптоанализе нахождение короткого вектора в решётках является основополагающей задачей. Именно приложение идеала Штикельбергера в криптоанализе является нашей главной мотивацией для его изучения. Ввиду большой группы Галуа интересными полями являются мультиквадратичные. Недавние работы по эффективному вычислению короткого вектора в мультиквадратичных полях [2] и по вычислению группы классов [3] подводят к вопросу нахождения коротких векторов в произвольных идеалах. Следуя примеру круговых полей, логично обратить внимание на структуру идеала Штикельбергера для мультиквадратичных расширений. В работе предлагается алгоритм вычисления идеала Штикельбергера для мульти-квадратичного поля K = Q(y/dl, \\fd2,..., л/dn), где d1 = d2 = ... = dn = 1 (mod 4) и d попарно взаимно просты. Алгоритм имеет сложность O(2n), а так как [K : Q] = 2n, то даже для криптографически значимых степеней он эффективен. В основе алгоритма лежит работа Р. Кучеры [4]. Доказательства всех утверждений статьи можно найти в полной версии работы1. 1. Предварительные сведения Исходя из условий, наложенных на di, справедливо вложение K ^ Q((d1-...-d„). Кроме того, K П Q((dl.....de) = Q(v^di, \\fd2,..., Vd), где £ ^ n, что доказано в лемме 1. Рассмотрим числовые поля Q С K С L и обозначим их соответствующие группы Галуа Gl = Gal(L/Q) и GK = Gal(K/Q); Q[GL] = (Eaiai : ai G Q,ai G GL} и Q[GK] = (E aiai : ai G Q,ai G GK} - группы, конечно порождённые элементами GL (соответственно элементами Gk) над Q. Важными понятиями при вычислении элементов Штикельбергера являются отображения res и cor. Определим эти отображения, согласно [4], для расширения L/K: resl/k : Q[Gl] ^ Q[Gk], resl/^( Е aaa) = E aa(а\\к), vvecL J аеоь cor l/k : Q[Gk ] ^ Q[Gl] со^/к( E aa a) = E aa\\K a, каеОк аеОк где a\\K означает сужение автоморфизма a G GL на поле K; aa, aa|K -коэффициенты, соответствующие автоморфизмам a, а\\к. Дробную часть числа обозначим (•), т.е. 0 < (•) < 1; наибольший общий делитель элементов a,b G Z - через (a,b); символ Лежандра этих же элементов- (Oj. Для произвольного множества A его мощность обозначим #A. Дадим классические определения элемента и идеала Штикельбергера, согласно [5, с. 189]. Определение 1. Для любых n G N и a G Z и кругового поля Q(Zn) определим где 0 < a ^ n и aa G GQiCn) = Gal(Q((„)/Q). Определение 2. Для любых n G N и a G Z определим ^n(a) = (COrK/KnQ(Cn) ◦ reSQ(Cn)/KnQ(Cn^ (^n(a)) - элемент Штикельбергера, где K и Q(Zn) - соответственно числовое и круговое поля. Определение 3. Идеалом Штикельбергера поля K называется идеал вида I = К(a)\\a,n G Z,n ^ 1}П Z[Gk]. Теперь дадим определение квадратичным гауссовым суммам, а также покажем, как они взаимосвязаны с автоморфизмами круговых полей. Определение 4. Пусть m,k G Z, k > 0. Квадратичная гауссова сумма определя-k-i 2 ется как g(m, k) = Е e2mmb /k. b=о Следующая теорема позволяет выражать квадратные корни, рассматриваемые как элементы мультиквадратичного поля, через квадратичные гауссовы суммы. Представлена на страницах авторов https://crypto-kantiana.com/. Теорема 1 [6, 1.5.2, с. 26]. Пусть (m, k) = 1, k > 0 и k нечётное. Тогда /m\\ И m /k, k = 1 (mod 4), g(m, k) = (!^)g(1,k)= M m \\ ^ , , Ц-jiVk, k = 3 (mod 4). Если -k = 1 (mod 4), то k = 3 (mod 4). Тогда \\f-k = g(1,k) по теореме 1. Рассмотрим отображение reSQ(£n)/KnQ(cn). Прокомментируем, как происходит сужение автоморфизмов поля Q(Zn) на поле K П Q(Zn) и что есть пересечение K П Q(Zn). Ответим на первый вопрос, определив сужение кругового поля Q(Zn) на некоторое числовое поле. Рассмотрим общий случай, когда n = pq, где p,q > 0 - взаимно простые. Тогда автоморфизм aa поля Q((pq) можно связать с действием автоморфизмов полей Q(ZP) и Q(Zq) на элементы у/-_p и у/-q следующим образом: Va((pq) = g(a,pq) = ^ g(1,P^ -p^J g(1, q) = aaq (/=p)aap(/=q). Здесь индекс aq в случае aaq (у/-p) рассматривается по модулю p, индекс ap в случае oav(yf-q) -по модулю q. Более детально все вычисления представлены в п. 2. Ответ на второй вопрос даёт следующая Лемма 1. Пусть K = Q(y/d1, \\fd2,..., \\fdn) -мультиквадратичное поле, где d1 = = d2 = ... = dn = 1 (mod 4) и все di попарно взаимно просты для i = 1,... , n; Q((dv...de) - круговое поле, где Zdv...de -корень степени d1 • ... • dg из единицы и £ ^ n. Тогда K П Q((dr..,d£) = Q (/dl, /d2, ..., /dg). Для упрощения дальнейших вычислений дадим альтернативное определение идеалу Штикельбергера; его эквивалентность исходному определению, обеспечивающая корректность работы алгоритма, представлена в полной версии статьи на https: //crypto-kantiana.com/. Пусть f - кондуктор поля K, тогда KПQ(Zn) = KПQ(C(/,n)) для n Е N. Определение кондуктора числового поля можно посмотреть в [7]. Определение 5. Идеалом Штикельбергера поля K с кондуктором f называется идеал вида I = I' П Z [GK], где I' = {а • ^П(-1): n|f, а Е GK}u{2NK 2. Алгоритм Рассмотрим алгоритм вычисления идеала Штикельбергера для мнимых мульти-квадратичных полей в соответствии с описанной в п. 1 теорией. Вычисление действия отображения res не тривиально в общем случае, поэтому рассмотрим его более детально. Применим квадратичные гауссовы суммы для вычисления reSQ(Cdl.....dn )/KnQ(Zdi ...dn )Odi • ... • dn (-1), где -1 - > а = \\ dl • ... • d„ Od! •...•dn (- 1)= E Ь-- / aa (a,di •... •dn) Здесь aa Е GQ(zd . dn) действуют лишь на элемент yjd1 • ... • dn. По формуле (1) каждый такой автоморфизм сводится к произведению автоморфизмов полей Q(Zd1), ^а1. Введём обозначение a dn). Рассмотрим каждое слагаемое di ■ ... ■ dn П = a П dj, тогда j=i (d"^-^ ) = aa(Vd1 ■ ... ■ dn) mod di (C(d1)) ■ ... ■ a-mod dn (C(dn)). a_ d1 ■ ... ■ dn n mod nn mod dn 1d , mod d1 - квадратичный вычет по модулю d1, то заменяем Если ni mod di (Z (d1)) на id1, где id1 : >/d1 ^ л/d!; в противном случае - на a1, где a_1_ --г-j- mod di ni mod di a1 : \\/d7 ^ - Аналогично рассуждаем для остальных множителей. Полученные композиции автоморфизмов переобозначим следующим образом: id1 ■ id 2 ■ ... ■ idn = id : -v/d1 + ... + \\/dn ^ \\/di + + ... + л/dn, тт : \\/di + ... + \\/dn-1 + \\J~dn ^ - - ... - \\fd~n. a1 ■... ■ an- 1 ■ a n ' m Очевидно, что общее количество получившихся композиций автоморфизмов равно 2n. Поскольку первый автоморфизм обозначен id, то m = 2n - 1. Процедура вычисления res представлена в алгоритме 1. Алгоритм 1. Вычисление res(en(-1)) Вход: K = 0(л/

Ключевые слова

мультиквадратичные поля, идеал Штикельбергера, элемент Штикельбергера, задача поиска короткого вектора, multiquadratic number field, Stickelberger ideal, Stickelberger element, the shortest vector problem

Авторы

ФИООрганизацияДополнительноE-mail
Олефиренко Денис ОлеговичБалтийский федеральный университет им. И. Кантааспирантdenis_cooler_1@mail.ru
Киршанова Елена АлексеевнаБалтийский федеральный университет им. И.КантаPh. D., доцентelenakirshanova@gmail.com
Малыгина Екатерина СергеевнаБалтийский федеральный университет им. И.Кантакандидат физико-математических наук, доцентemalygina@kantiana.ru
Новоселов Семен АлександровичБалтийский федеральный университет им. И.Кантаассистентsnovoselov@kantiana.ru
Всего: 4

Ссылки

Cramer R., Ducas L., and Wesolowski B. Short Stickelberger class relations and application to ideal-SVP // Advances in Cryptology - Eucrocrypt 2017. Springer, 2017. P. 324-348.
Bauch J., Bernstein D. J., de Valence H., et al. Short generators without quantum computers: The case of multiquadratics // Advances in Cryptology - EUROCRYPT 2017. Springer, 2017. P. 27-59.
Biasse J.-F. and Vredendaal C. Fast multiquadratic S-unit computation and application to the calculation of class groups // Open Book Series. 2019. V. 2. P. 103-118.
Kucera R. On the Stickelberger ideal and circular units of a compositum of quadratic fields // J. Number Theory. 1996. V. 56. No. 1. P. 139-166.
Sinnott W. On the Stickelberger ideal and the circular units of an Abelian field // Invent. Math. 1980. V. 62. P. 181-234.
Berndt B.C., Evans R. J., and Williams K.S. Topics in Commutative Ring Theory. N.Y.: Wiley, 1998.
Cohen H. and Stevenhagen P. Computational Class Field Theory. 2008. https://arxiv.org/ pdf/0802.3843.pdf
 Алгоритм вычисления элемента Штикельбергера для мнимых мультиквадра-тичных полей | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/3

Алгоритм вычисления элемента Штикельбергера для мнимых мультиквадра-тичных полей | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/3