Efficient Euclidean division algorithms in some degree 8 number rings

The arithmetic of number rings is a difficult topic in computational number theory. In particular, one simple question is hard to answer: can one perform Euclidean division in a given number ring? In this talk, we will focus on a few cyclotomic rings, which are baby-sized versions of the lattices used in modern signature schemes such as Falcon. The rings in question were proven to be Euclidean domains by H.W. Lenstra in the 1970’s, but no algorithm had yet been presented to actually perform Euclidean division in them. We will explain how Lenstra’s proof of Euclideanity can be reformulated in terms of a closest vector problem (CVP) with respect to a root lattice, and describe how to solve this problem in the particular case at hand, yielding a particularly efficient Euclidean division algorithm.