BARBULESCU, Razvan; POULALION, Adrien

Metadatos

Mostrar el registro completo del ítem

Licencia de uso del documento

BARBULESCU, Razvan
Lithe and fast algorithmic number theory [LFANT]
Analyse cryptographique et arithmétique [CANARI]

POULALION, Adrien
Alice & Bob
Corps Royal des Mines

Idioma

Communication dans un congrès

Este ítem está publicado en

Progress in cryptology -- AFRICACRYPT 2023Lecture notes in computer science (LNCS), Progress in cryptology -- AFRICACRYPT 2023Lecture notes in computer science (LNCS), AFRICACRYPT 2023, 2023-07-18, Soussa. 2023-07-21, vol. 14064, p. 229

Springer

Resumen en inglés

Unit group computations are a cryptographic primitive for which one has a fast quantum algorithm, but the required number of qubits is Õ(m 5). In this work we propose a modification of the algorithm for which the number of qubits is Õ(m 2) in the case of cyclotomic fields. Moreover, under a recent conjecture on the size of the class group of $ \mathbb{Q}(ζ_m + ζ _m^{−1})$, the quantum algorithms is much simpler because it is a hidden subgroup problem (HSP) algorithm rather than its error estimation counterpart: continuous hidden subgroup problem (CHSP). We also discuss the (minor) speed-up obtained when exploiting Galois automorphisms thanks to the Buchmann-Pohst algorithm over OK-lattices.< Leer menos

Palabras clave en inglés

Quantum algorithms

unit groups

Cyclotomic fields

lattices

Metadatos

Compartir este ítem

Licencia de uso del documento

The special case of cyclotomic fields in quantum algorithms for unit groups

Idioma

Este ítem está publicado en

Resumen en inglés

Palabras clave en inglés

URI

Orígen

Centros de investigación